递归--练习3--noi7592求最大公约数问题
一、心得
两个低级错误:
1. ll setMax(ll &m,ll &n)中无引用,结果只传值,没传地址
2. return f(n,m%n);这句话忘记写return了
//保证结果能够一层层的返回
二、题目
7592:求最大公约数问题
总时间限制:
1000ms 内存限制:
65536kB
描述
给定两个正整数,求它们的最大公约数。
输入
输入一行,包含两个正整数(<1,000,000,000)。
输出
输出一个正整数,即这两个正整数的最大公约数。
样例输入
6 9
样例输出
3
提示
求最大公约数可以使用辗转相除法:
假设a > b > 0,那么a和b的最大公约数等于b和a%b的最大公约数,然后把b和a%b作为新一轮的输入。
由于这个过程会一直递减,直到a%b等于0的时候,b的值就是所要求的最大公约数。
比如:
9和6的最大公约数等于6和9%6=3的最大公约数。
由于6%3==0,所以最大公约数为3。
三、AC代码
1 /*
2 noi7592求最大公约数问题
3 递推表达式:
4 f(m,n)=f(n,m%n)
5 边界条件
6 n==0时,m就是最大公约数
7 */
8 /*
9 两个低级错误:
10 1. ll setMax(ll &m,ll &n)中无引用,结果只传值,没传地址
11 2. return f(n,m%n);这句话忘记返回了
12 */
13 #include <iostream>
14 #include <cstdio>
15 #define ll long long
16 using namespace std;
17 //必须保证m>n
18 ll f(ll m,ll n){
19 if(0==n) return m;
20 else{
21 return f(n,m%n);
22 }
23 }
24 //必须保证m>n
25 ll setMax(ll &m,ll &n){
26 if(n>m){
27 ll temp=n;
28 n=m;
29 m=temp;
30 }
31 }
32 int main(){
33 //freopen("in.txt","r",stdin);
34 ll m,n;
35 cin>>m>>n;
36 setMax(m,n);
37 ll ans=f(m,n);
38 cout<<ans<<endl;
39 return 0;
40 }