您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

c语言实现更相減損法求最大公約數

发布时间：2021-04-29 21:59:00编辑：雪饮阅读（）

 更相减损法来求取最大公约数这种方式在以前数学解题中我们一般用的比较少，而我们用的最多的还是分解因式。

那么更相减损法是来自于九章算术的。今天就利用这个算法实现c语言中求取最大公约数。
先看看这个更相减损法到底是怎样的一个算法吧。

“可半者半之”
通常认为，算法描述中的第一步“可半者半之”是指分子分母皆为偶数的时候，首先用2约简。因为更相减损术原先是专用来约分，所以并不用考虑最后计算结果时，要把第一步中约掉的若干个2再乘回去。加入这一步的原因可能是，分母、分子皆为偶数是在分数加减运算的结果中比较容易遇到的一种情况，用这种方法有可能减少数字的位数，简化计算。
当然，省略这个以2约简的步骤，也能得到正确的答案。
 
那么今天这里我们就不使用这个可半者半之了，只使用正常的流程来实现。
#include <stdio.h>
int main()
{
    int n1, n2;
   
    printf("输入两个数，以空格分隔: ");
    scanf("%d %d",&n1,&n2);
 
    while(n1!=n2)
    {
              /*
              每次進行大的減去小的，每次的結果和上次的比較小的數再次進行大的減去小的，直到某個結果和上次的比較小的數相同的時候
              */
        if(n1 > n2){
                     printf("\n %d-%d=%d \n",n1,n2,n1-n2);
                     n1=n1-n2;
              }
           
        else{
                     printf("\n %d-%d=%d \n",n2,n1,n2-n1);
                     /*
                     當然這裏也可以n1=n2-n1，以爲循環條件只判斷n1!=n2,
                     而沒有限制必須是操作數n1怎麽樣或者操作數n2怎麽樣,
                     更相减损法也只關心每次大數減去相對比較小的數（或者結果與上次的比較小的數進行比較然後再次執行這兩個數中的比較小的數）
                     */
                     n2=n2-n1;
                    
              }
           
    }
       //得到最大公約數時左右操作數一致了，所以這裏輸出n1或者n2都可以
    printf("\n 求得最大公約數GCD = %d \n",n1);
 
    return 0;
}