给定两个整数,求出他们的最大公约数。
my code:
#include <stdio.h>
int main(){
int a,b,t,x,target;
int max(int a,int b){
int c;
c = (a > b ? a : b);
return c;
}
int min (int a,int b){
int c;
c = (a < b ? a : b);
return c;
}
scanf("%d%d",&a,&b);
t = min (a,b);
x = max (a,b);
target = t;
while (x % target){
target --;
}
while(t % target){
target--;
}
printf("%d",target);
return 0;
}
优解(辗转相除法):
#include <stdio.h>
int main(){
int a,b,t;
scanf("%d %d",&a,&b);
while (b != 0){
t = a%b; a = b ; b = t ;
printf("a = %d,b = %d,t = %d\n",a,b,t);
}
printf("gcd = %d\n",a);
return 0;
}
分析:我的代码在解决一些比较特殊的数字的时候仍然有问题,而且过于直白,没有对程序的深入思考,效率很低。
总结:在写代码时,先写直白的,写完后再思考是否对问题的情况理解透彻,如在这里,简单的调换数值,就可以使代码优化,可是我却没有想到,这是值得反思的。同时对最大公约数的理解也影响着解题思路。
领悟:既然时最大公约数,那么其不同整数倍势必为给定两数,因此,在第一轮判断中,得到较小的数不能被较大的数整除时,就可以直接利用余数,将余数再进行整除判断,因为余数是不能整除的部分,可以用较小的数对其再取余,同时不断地换成较小的数对其进行取余是利用了之前可以被整除的数,将其分解成更小的数来组成他的值,这样当余数为零时,两个数就可以都由不同个数的最终答案来组成,这样就是最大公约数,即将目标不断细化,直到满足要求。举个例子:68 32 68 / 32 = 2 。。。。。。4,那么我们就找,32里面有几个4,是不是整数个,假定满足要求为k个4,则68就可以这样写,68 = 4k + 4,那么,两边就都满足由一定数目的4组成,如果不满足,我们就继续找,直到较大值可以由一定数目的目标值构成,最坏的情况为只能由1构成。示例:67 34 67 / 34 = 1.。。。。。。。33,34里有1个33,而33可以由33个1构成,则67 = {(1 * 34)+ 33 } =(1 * 33 + 1)+ 33 = (1 * 33 + 1) + 33 *1 = 1 * { (33 + 1) + 33}.即一定数目的1可以构成33和34,而67就可以由一定数目的1构成,因为67可以由一个34和一个33构成,所以肯定可以由一定数目的1构成。这就是辗转相除法