完美的正方形分割

科技前沿 • 2025-02-28 12:47 • 阅读 42

大家好，我是讯享网，很高兴认识大家。

完美的正方形分割：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++)

完美的正方形分割

相关推荐