C语言/数据结构欧几里得算法题解：长方形切割最大正方形——贪心划分计数

问题描述小明是城市规划局的一名实习生最近他接到了一个有趣的任务将一个长方形园区划分成若干个小正方形区域每个区域用于不同的功能如花园、游乐场、停车场等。园区的长和宽都是整数小明发现每次划分时他需要从园区中切出一个尽可能大的正方形然后对剩余部分重复此过程直到整个园区都被划分为正方形。现在给定园区的长度L和宽度W均为正整数请你帮助小明计算按照上述贪心策略每次切出最大可能的正方形最终会得到多少个正方形区域要求模拟贪心策略的过程每次从当前矩形中切出最大的可能正方形边长为当前矩形的最小边长然后对剩余部分递归处理直到所有部分都变成正方形。算法应高效处理较大的输入范围。测试样例样例1输入L 5, W 3输出4解释第一步切出 3x3 的正方形1个剩余 2x3 的矩形第二步切出 2x2 的正方形1个剩余 2x1 的矩形第三步切出 1x1 的正方形1个剩余 1x1 的矩形第四步切出 1x1 的正方形1个。总共 4 个正方形。样例2输入L 4, W 6输出3解释第一步切出 4x4 的正方形1个剩余 4x2 的矩形第二步切出 2x2 的正方形1个剩余 2x2 的矩形第三步切出 2x2 的正方形1个。总共 3 个正方形。样例3输入L 1, W 1输出1解释本身就是一个正方形不需要划分。约束条件1 ≤ L, W ≤ 1000输入保证 L 和 W 都是正整数贪心策略每次从当前矩形中切出最大的可能正方形边长为当前矩形的最小边长然后对剩余部分递归处理程序代码#include stdio.hint countSquares(int L, int W) {int count 0;while (L 0 W 0) {if (L W) {count 1;break;}if (L W) {// 交换保证 L Wint temp L;L W;W temp;}// L W切出 W x W 的正方形count L / W;L L % W;}return count;}int main() {printf(%d\n, countSquares(5, 3)); // 4printf(%d\n, countSquares(4, 6)); // 3printf(%d\n, countSquares(1, 1)); // 1return 0;}#include stdio.h int countSquares(int L, int W) { int count 0; while (L 0 W 0) { if (L W) { count 1; break; } if (L W) { // 交换保证 L W int temp L; L W; W temp; } // L W切出 W x W 的正方形 count L / W; L L % W; } return count; } int main() { printf(%d\n, countSquares(5, 3)); // 4 printf(%d\n, countSquares(4, 6)); // 3 printf(%d\n, countSquares(1, 1)); // 1 return 0; }运行结果