我的GCD算法有什么问题？

-4

这是我在计算两个输入数字的GCD尝试：我的GCD算法有什么问题？

int rep; 
do{ 
    system ("cls"); 
    int a, b, gcd=2, e, d; 
    cin >> a >> b; 
    if(a % b != 0 || b % a != 0){ 
     do{ 
      gcd = gcd + 1; 
      d = a % gcd; 
      e = b % gcd;   
     } while(d==0 && e==0); 
     cout << gcd-1; 
    }else if(a == 1 || b == 1){ 
     gcd=1; 
     cout << gcd; 
    }else if(a >= b){ 
     gcd = a; 
     cout << gcd; 
    }else if(b >= a){ 
     gcd = b; 
     cout << gcd; 
    } 
    cin >> rep; 
} while(rep == 1);

如果我输入8和24，它给了我2的答案。任何人都可以在我的代码中发现问题吗？

来源

2015-09-21 Satwik Singh

：一切 –

问题是该算法在第一次放弃测试GCD失败时放弃。在大多数情况下，找到最大的意味着要经过一些不起作用的值。在这种情况下，最多8次意味着越过3次，5次和7次。

8％24 == 8.所以do循环至少运行一次。 gcd变为3并进行测试，但不会均匀分配为8，因此while条件的计算结果为false。然后3 - 1（2）流式传输到cout。不过这不是正确的GCD。

你可以修改你的算法，从2个输入中较小的一个开始，向下工作，直到成功（8这里），然后失败（7这里）。

来源

2015-09-21 17:28:34 donjuedo

这里GCD算法的肉只有3行，其余的是致力于防止愚蠢。

#include <stdio.h> 

unsigned GCD(unsigned x, unsigned y) { 
    unsigned z; 
    if (x < y) { 
     z = x;     // swap 
     x = y; 
     y = z; 
    } 
    if (y == 0) 
     return 0; 
    while (z = x % y) {   // perform the GCD with implicit 0 test 
     x = y; 
     y = z; 
    } 
    return y; 
} 

int main(void) 
{ 
    printf("GCD of %u, %u = %u\n", 1, 0, GCD(1, 0)); // billed as C 
    printf("GCD of %u, %u = %u\n", 0, 1, GCD(0, 1)); 
    printf("GCD of %u, %u = %u\n", 1, 1, GCD(1, 1)); 
    printf("GCD of %u, %u = %u\n", 8, 24, GCD(8, 24)); 
    return 0; 
}

程序输出：

用一个词

GCD of 1, 0 = 0 
GCD of 0, 1 = 0 
GCD of 1, 1 = 1 
GCD of 8, 24 = 8

来源

2015-09-21 17:37:30

我的GCD算法有什么问题？

回答

相关问题