完美的正方形分割：http://learning.sohu.com/20060329/n242511178.shtml
问题出处：http://topic.csdn.net/u/20071206/17/20f9fb73-7a11-4fab-92a4-f7a61a056c3f.html
解决办法：
先穷举出可能的正方形组合1 ，然后检测能不能拼成指定长方形2
程序用递归实现
1可能的组合：各正方形面积和与某个长方形面积相等，进行第一轮筛选
2就像用计算机玩只有大小不一的正方形的俄罗斯方块一样，搜索有没有解
c源代码：
#include <stdio.h>#include <math.h>#include <time.h>#include <assert.h>const MAXWIDTH = 200; //最大宽度const MAXBASE = 3; //最小正方形最大尺寸const RANK = 10; //阶数const MARGIN = 10; //长宽最大差值(0表示正方形)int square[MAXWIDTH]; //NUM个数的平方，优化效果微小int result[RANK]; //可能的排列结果【0, rank-1】,从小到大int width, height; //宽、高int count = 0; //穷举记数int flag[RANK]; //代表被使用的顺序号(索引);值[0,rank-1],rank表示未使用,>rank做标记用于输出结果,例:flag[RANK-1]=0，表示最大的正方形放第一个int high[MAXWIDTH]; //已被填放的高度表,比如9×10的长方形放置一个5×5，则数据为:[5 5 5 5 5 0 0 0 0 0] //注意：这两个数组用于递归，每个递归使用退出后需要还原原值void perfectrect();void check();void search(int n, int index, int sum); //枚举正方形组合bool searchrect(int n, int left); //判断能否填充int main(int argc, char * argv[])
...{
int i; //预处理 for(i=1; i<=MAXWIDTH; i++)
...{
square[i] = i * i;
} perfectrect(); printf("Complete! "); return 0;
}
void
perfectrect()
...
{
int sum; int i; static count2 = count; time_t t; time_t t2 = 0; for(width=20; width<MAXWIDTH; width++)
