局网站建设进入前十名,网络开发公司是干什么的,网站目录改版,四川工程造价信息网题干#xff1a;
描述 对一个给定的矩形#xff0c;将其划分成尽可能少的正方形#xff0c;输出正方形的最少个数。例如#xff0c;如下图所示的情况#xff0c;则输入为3和4#xff0c;输出为4。
输入 输入两个整数中间用空格分开。
输出 输出最少分割成的正方形的个…题干
描述 对一个给定的矩形将其划分成尽可能少的正方形输出正方形的最少个数。例如如下图所示的情况则输入为3和4输出为4。
输入 输入两个整数中间用空格分开。
输出 输出最少分割成的正方形的个数。
输入样例 1
3 4
输出样例 1
4
解题报告 简单递归。 这题如果是t组数据的话这个f函数就可以写记忆化了。。。但是这个题就没必要了因为状态转移之间没有重叠子问题所以不需要dp。
AC代码
#includebits/stdc.husing namespace std;
int f(int x,int y) {if(x y) return 1;if(x y) {return f(x-y,y) 1;}else return f(y-x,x) 1;
}
int main()
{int n,m;while(cinnm) {cout f(n,m)endl;}return 0;}
