完美的正方形分割：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++)
...{
for(height=width; height<=width+MARGIN; height++)
...{
sum = height*width;
for(i=1; i<=MAXBASE; i++)
...{
result[0] = i;
search(i+1,1, sum-square[i]);
}
}
t = clock();
printf("%d %10d %10d %10d %10d ", width, count, t, count-count2, t-t2);
count2 = count;
t2 = t;
}
}
void search( int n, int index, int sum)
... {
int i;
for(i=n;sum >=square[i]*(RANK-index); i++)
...{
if(index == RANK-1 )
...{
if(sum == square[i])
...{
result[index] = i;
check();
break;
}
}
else
...{
result[index] = i;
search(i+1, index+1, sum-square[i]);
}
}
}
// 判斷能否拼成指定長方形
void check()
... {
count++;
int i, tmp;
for(i=0; i<RANK-1; i++)
flag[i] = RANK; //未使用
//第一個放置最大的
flag[RANK-1] = 0;
tmp = result[RANK-1];
for(i=0; i<tmp; i++)
high[i] = tmp;
//放置第二個正方形，遞歸搜尋
searchrect(1, tmp);
}
bool searchrect( int n, int left)
... {
int i, j;
int pos, w, h; //最低處起始位置，高度，寬度
int tmp;
//對第一行優化處理
if(left != 0)
...{
for(i=RANK-2; i>=0; i--) //從大到小放置（[RANK-1]已被使用）
...{
if(flag[i] < n)//是否已使用
continue;
if(result[i] > width-left) //放不下，下一個
continue;
flag[i] = n;
tmp = result[i];
for(j=0; j<tmp; j++)
high[j+left] = tmp;
if(tmp == width-left) //相等，搜尋第二行
...{
if(searchrect(n+1, 0)) //成功
...{
flag[i] = RANK; //恢複标記
return true;
}
}
else //繼續第一行
...{
if(searchrect(n+1, left+tmp)) //成功
...{
flag[i] = RANK; //恢複标記
return true;
}
}
flag[i] = RANK; //恢複标記
}
return false;
//assert(!"第一行排列出錯");
}//是否第一行
//非第一行
//擷取插入位置和大小
h = height+1;
bool exist = false;
for(i=0; i<width; i++)
...{
if(exist && high[i] == h)
...{
w++;
}
else if(high[i] < h)
...{
h = high[i];
pos = i;
w = 1;
exist = true;
}
else //防止最底的位置存在兩塊(不連續)
...{
exist = false;
}
}
//周遊
for(i=RANK-2; i>=0; i--) //從大到小放置（[RANK-1]已被使用）
...{
if(flag[i] < n)//是否已使用
continue;
if(n == RANK-1) //完美長方形
...{
if(w == result[i] && height == h+result[i])
...{
for(j=0; j<RANK-1; j++)
...{
for(int k=0; k<RANK; k++)
if(flag[k]==j)
printf("%d, ", result[k]);
}
printf("%d ", result[i]);
return true;
}
else
continue;
}
if(w < result[i]) //放不下，下一個
continue;
tmp = result[i];
if(height < h+tmp) //高越界
continue;
flag[i] = n;
for(j=0; j<tmp; j++)
high[j+pos] += tmp ;
if(searchrect(n+1, 0)) //成功
...{
flag[i] = RANK; //恢複标記
for(j=0; j<tmp; j++)
high[j+pos] -= tmp ;
return true;
}
else //不成功，恢複标記後轉下一個
...{
flag[i] = RANK;
for(j=0; j<tmp; j++)
high[j+pos] -= tmp ;
}
}//逐個判斷
return false;
}
10階完美分割輸出：
20 10 15 10 15
21 32 15 22 0
22 73 15 41 0
23 128 15 55 0
24 225 31 97 16
25 443 46 218 15
26 775 62 332 16
27 1225 93 450 31
28 1963 156 738 63
29 3106 250 1143 94
30 4817 359 1711 109
31 7182 546 2365 187
32 10608 765 3426 219
33 15306 1140 4698 375
34 22150 1609 6844 469
35 31782 2296 9632 687
36 42902 3015 11120 719
37 59456 4296 16554 1281
38 81354 5859 21898 1563
39 108661 7968 27307 2109
40 144732 10375 36071 2407
41 192230 14218 47498 3843
42 251482 18562 59252 4344
43 327179 24734 75697 6172
44 419013 31546 91834 6812
45 536701 41125 117688 9579
46 684991 52875 148290 11750
47 865802 68468 180811 15593
48 1075802 84421 210000 15953
49 1349101 108109 273299 23688
50 1683193 135531 334092 27422
51 2067328 169343 384135 33812
52 2529166 207343 461838 38000
53 3100325 258562 571159 51219
54 3760772 315031 660447 56469
30, 25, 8, 17, 27, 3, 11, 2, 15, 13
暴力窮舉第一個需要300多秒
而9階的第二個不到300秒，第一個隻用0.3秒(修改const RANK = 9)
11階還不知道多少時間，暫時也想不出怎麼優化，也許隻能從數學上想辦法了
那個本世紀三十年代末的德國數學家太猛了