地盘划分
【例】将一个给定的矩形划分为一个个正方形,其规则是先从矩形中划分出一个尽可能大的正方形,接下来,在剩下的矩形中再划分出一个尽可能大的一个正方形,以此类推。例如,宽*长为3*4的矩形,最少可划分为4个正方形,也就是说。取走一个3*3的正方形后,将问题规模变成3*1,然后变为2*1,最后变为1*1。规模每缩小一次,正方形个数加一,是计算出正方形的个数。
【输入格式】
输入两个整数,表示矩形的长和宽。
【输出格式】
输出一个整数,表示划分的正方形的个数。
【输入样例】
3 4
【输出样例】
4
【普通】
#include <iostream> using namespace std; int main(){ int a,b,n=0,t_a; cin>>a>>b; for(int i=0;i<100;i++){ if(a==b){ n++; break; }else{ t_a=a; a=max(a,b)-min(a,b); b=min(t_a,b); n++; } } cout<<n; return 0; }
【递归】
#include <iostream> using namespace std; int m(int a,int b){ if(a==b){ return 1; }else{ int t_a=a; a=max(a,b)-min(a,b); b=min(t_a,b); return m(a,b)+1; } } int main(){ int a,b; cin>>a>>b; cout<<m(a,b); return 0; }
标签:递归,int,地盘,个数,正方形,划分,矩形 From: https://www.cnblogs.com/wangyueshuo/p/17808909.html