矩形切割问题——C语言（超级详细）、蓝桥杯

问题描述：

小明有一些矩形的材料，他要从这些矩形材料中切割出一些正方形。 当他面对一块矩形材料时，他总是从中间切割一刀，切出一块最大的正方 形，剩下一块矩形，然后再切割剩下的矩形材料，直到全部切为正方形为止。 例如，对于一块两边分别为 5 和 3 的材料（记为 5×3），小明会依次切出 3×3、2×2、1×1、1×1 共 4 个正方形。 现在小明有一块矩形的材料，两边长分别是 2019 和 324。请问小明最终会 切出多少个正方形？

解题思路：

首先要读懂题意，由题目就可以知道切割所得的正方形的边长，最大长度只能为矩形的宽，因此只需要用矩形的长（a）除矩形的宽（b），商就可以表示该矩形的最多可以切割出与矩形宽（b）相等的边长的正方形，余数则表示矩形，在切割之后矩形的长（a）还剩余的长度，这个时候就需要一个转换思想：就需要将矩形剩余的长度与上一次切割所得的正方形边长（即除数）作比较，其中较长的边就看作是矩形的长度，较短的边就看作是下一次所切割得到的正方形的边长，然后用较长的边除以较短的边所得的商就是正方形的个数，再用除数与余数进行比较，然后再循环往复就可以，直到不能再切割出正方形就结束。再将正方形的个数进行累加就可以得到：矩形所切割得到的全部正方形个数。

代码如下：

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int a,b,sum=0;//a表示较长的边，b表示较短的边，sun表示所得正方形的总数 int s=0;//表示边长为某值时的正方形的个数 printf("请分别输入矩形的长和宽: ") ; scanf("%d %d",&a,&b); int y=a%b;//y表示较长的边除以较短的边的余数 while(y!=0)// { if(a<b)//将a,b两个边长进行排序，方便找出较短的边作为正方形的边长 { int t; t=a; a=b; b=t; } s=a/b;//表示有长度为b的正方形个数有s个 sum=sum+s;//计算正方形总个数 y=a%b;//表示矩形边长还剩余y的长度 b=y;// 将剩余的长度赋值给b（就可以运用计算正方形个数的公式再计算正方形个数） a=(a-b)/s;// 计算上一次正方的边长（即除数） } printf("正方形的个数有:%d个 ",sum); return 0; }

运行结果及其代码：