HDU-1014魔鬼在细节中

此题原本觉得很水,刷的时候一遍又一遍的WA快让我抓狂了..先看下网上的几段代码:

求最大公约数的函数(证明从略--实际上我也不知道囧)

1.递归

    int gcd(int a,int b){if(a==0){return b;}else{return gcd(b % a,a);}}

2.考虑到大小不一致的情况封装函数:

int mcd(int a, int b) 
{ 
if( a <= 0 || b <= 0 ) 
return -1; 
int max,min; 
max = a > b ? a : b; 
min = a + b - max; 
int temp; 
//辗转相除 
while( min ) 
{ temp = min; 
min = max % min; 
max = temp; 
} 
return max; } 

int get_comm_div(int m,int n)
{
int tmp;
while(m%n)
{
tmp=m%n;
m=n;
n=tmp;
}
return tmp;
}

对比一下AC的代码和自己的:

AC:

#include
int main()
{int a,b;int gcd(int a,int b);while(scanf("%d%d",&a,&b)!=EOF){if(gcd(a,b)!=1)printf("%10d%10d    Bad Choice\n\n",a,b);elseprintf("%10d%10d    Good Choice\n\n",a,b);}
}
int gcd(int a,int b)
{int t;while(b>0){t=a%b;a=b;b=t;}return (a);
}

自己的:

#include 
/*
Author:Unibrighter
Version 2012-8-16 17:09:13
Problem ID:HDU-1014
Tip:Transform this problem into another,which requires to get the Greatest Common Divice(GCD)
*/
//Remember to review the Format methods of IO
int main()
{//freopen(".\\1014in.txt","r",stdin);int STEP,MOD,GCD;while(scanf("%d %d",&STEP,&MOD)!=EOF){GCD=0;//refresh the value of GCDprintf("%10d%10d    ",STEP,MOD);//Show the input Staticswhile(STEP%MOD){GCD=STEP%MOD;STEP=MOD;MOD=GCD;}//printf("MOD:%d ;STEP:%d ;GCD:%d   ",MOD,STEP,GCD);if(GCD==1||(STEP==MOD&&STEP==1))//如果这里是GCD==1,就会WAprintf("Good Choice\n\n");elseprintf("Bad Choice\n\n");}return 0;
}

天人 0:16:15 
大大..帮偶看看这两个循环有什么区别好米>.<...


研究了一下午了,就因为这一个循环而不能AC.
前提:(1<=a,b<=100000)


例子：
5 3


5和3的最小公约数肯定是1。
把它们当作要求的最大公约数的倍数。
当它们互相求余求到对方掉裤子变成1的时候，出来的数就是要求的最大公约数。
（仅以“倍数”进行说明）因此在其中一方为1的时候，必然出现整除，t为0时，b必为1。b实际的值就为所求的最大公约数。
1、以b>0为判断条件，等同于b为0时退出循环。则此前b=0，有t=0，所以最大公约数落在a上（或再上一次的b，可惜已死）。
2、以a%b为判断条件，等同于当b为1时退出循环，则此前b=1，t=1，所以最大公约数落在b或者t。
总体上，方法1比方法2运算多一次。/这就是重点
当a=b=1时，方法2不进去循环内，因此t无值，参数需要修改为b。


int t,a,b;
while(b>0)
{
t=a%b;
a=b;
b=t;
}
return (a);


2. int t,a,b;
   while(a%b)
   {
    t=a%b;    
    a=b;
    b=t;
    }
    return t;//参数改为b才正确


我用了很多组测试数据,除了a==b==1的情况已经考虑进去了以外,其他的所有情况都是一样的啊..没有觉得有区别啊 啊啊啊啊..

以上问题解决,感谢技术宅纯技术研究所群里的朋友,尤其是EricHo和天人,xushine等等.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！