分治基础 划分地块

给定一个大小为a × b的地块，现将其划分为多个边长尽可能大的、等大的正方形，求正方形的边长？

输入： 640 400 输出： 80

数据范围：输入数据均为int类型，且a,b>0。 · · · 思路 本质上是求最大公约数，详见欧几里得算法。 采用分治，将大问题化解为小问题。

程序代码

#include <iostream> #include <algorithm> using namespace std; int dividedLength(int a, int b) { int width = min(a, b); int length = max(a, b)%width; if (!length) return width; //终止条件 return dividedLength(length,width); } int main() { cout << dividedLength(25, 25) << endl; return 0; }