题目描述
给出长方形的长和宽,每次从长方形里撕去最大的正方形,输出最后能得到多少正方形。
输入格式
一行,两个整数 n,m
。
输出格式
一个整数,表示最后能得到多少正方形。
数据范围
1≤n,m≤109
样例
输入样例:
3 4
输出样例:
4
算法1
每次撕去以$width$为边长的正方形,其实就是不断执行$length-width$,执行次数为$length/width$;
然后$length$和$width$的值变为$width$和$length%width$.
注意
- 取余运算%后不可为0,否则报
Floating point exception
错误
——>解决方法:增加if判断,第二个参数为0时,return 0
TIPS
⭐核心代码
1. 可使用return a/b + (b, a % b)
来跳过a,b大小判断
#include <iostream>
#include <algorithm>
using namespace std;
int num = 0;
int n,m; //输入长和宽
int square_mum(int n, int m){
if(!m) return 0; //当n==m时,第二个参数为0,此时返回0即可
return n/m + square_mum(m, n % m); //n/m表示撕去多少次以m为边长的正方形,之后m为length,n%m变成width
//若m大于n,则是撕去0次
}
int main(){
cin >> n >> m;
printf("%d", square_mum(n,m));
}