求最大公约数递归算法

求最大公约数递归算法#includestdio.hintgcd(intm,intn){intg;g=m%n;if(0==g){returnn;}else{returngcd(n,g);}}intmain(){intm,n;scanf(%d,%d，&m,&n);printf(gcd=%d,gcd(m,n));return0;}求最大公约数辗转相除法（1）#includestdio.hintgcd(intm,intn){intr,t;//若mn,交换m，nif(mn){t=m;m=n;n=t;}r=n;n=m%n;m=r;//如果n==0,m为最大公约数，否则递归if(n==0)returnm;elsereturngcd(m,n);//递归是要return的，此处漏了}intmain(){inta;intb;scanf(%d%d,&a,&b);intresult=gcd(a,b);printf(%d\n,result);getch();return0;}（2）#includestdio.hintgcd(intm,intn){intr,t;if(mn){t=m;m=n;n=t;}r=n;n=m%n;m=r;if(n==0)returnm;elsegcd(m,n);}intmain(){inta;intb;scanf(%d%d,&a,&b);intresult=gcd(a,b);printf(%d\n,result);getchar();return0;}intfun2(intx,inty,intz){returny;}intfun3(intx,inty,intz){returnz;}求最小公倍数递归算法（1）privateintgetNum(Int32[]num){if(num.Count()1){intint1=num[0];Int32[]num1=newInt32[num.Length-1];for(inti=1;inum.Length;i++){num1[i-1]=num[i];}num1[0]=int1*num1[0]/LCM(int1,num1[0]);returngetNum(num1);}else{returnnum[0];}}//最大公约数privateintLCM(intm,intn){if(m%n==0||n%m==0){if(mn){returnm;}else{returnn;}}else{if(mn){returnLCM(m,n%m);}else{returnLCM(m%n,n);}}}（2）staticvoidMain(string[]args){intm=12;intn=20;Console.WriteLine(最大公约数：{0},LCM(m,n));//两个正整数的最小公倍数=两个数的乘积÷两个数的最大公约数Console.WriteLine(最小公倍数：{0},m*n/LCM(m,n));}staticintLCM(intm,intn){if(m%n==0||n%m==0){if(mn){returnm;}else{returnn;}}else{if(mn){returnLCM(m,n%m);}else{returnLCM(m%n,n);}}｝辗转相除法求最小公倍数（1）main（）｛printf(inputmandn:);scanf(%d,%d,&m,&n);//赋值m，nif(nm){//把大的数放在在n中inttemp=n;n=m;m=temp;}intp=n*m;while(m!=0){辗转相除法intr=n%m;n=m;m=r;}printf(最大公约数为：%d+n);printf(最小公倍数为：%d+p/n);（2）#includestdio.hmain(){inta,b,c,d;scanf(%d%d,&a,&b);/*假设，输入0ab,不再判断*/d=a*b;while(a!=0){c=b%a;b=a;a=c;}d/=b;fprintf(最小公倍数为%d\n,d);}（3）intmaxcomdivisor(inta,intb){while(a%b!=0){intc=a%b;a=b;b=c;}returnb;}intmincomdivor(inta,intb){intd=maxcomdivisor(a,b);d=a*b/d;returnd;}voidmain(){intmaxcomdivisor(int,int);intmincomdivor(int,int);inta,b;printf(请输入两个正整数：);scanf(%d,%d,&a,&b);printf(%d与%d的最大公约数是%d，最小公倍数是%d。\n,a,b,maxcomdivisor(a,b),mincomdivor(a,b));