程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C說話 擴大歐幾裡得算法代碼

C說話 擴大歐幾裡得算法代碼

編輯:關於C++

C說話 擴大歐幾裡得算法代碼。本站提示廣大學習愛好者:(C說話 擴大歐幾裡得算法代碼)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話 擴大歐幾裡得算法代碼正文


給定兩個正整數m和n,我們盤算它們的最年夜公因子d和兩個整數a和b,使得a*m+b*n=d

算法流程
  E1.置a'=b=1;a=b'=0;c=m,d=n;

  E2.盤算d和r,使得c=q*d+r;

  E3.若r==0;則加入,以後已有a*m+b*n=d;

  E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;前往E2.

證實

  關於已有的m和n,假定m>n;假如刨除變量a,b,a',b';算法與歐幾裡得算法完整一樣,為盤算最年夜條約數的算法.

  終究請求的為a*m+b*n=d=GCD(m,n);假如改式子成立由歐幾裡得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);

  由於GCD(m,n)=GCD(n,m%n);

  所以a*m+b*n=a'*n+b'*(m%n)

        =a'*n+b'*(m-(m/n)*n)

        =a'*n+b'*m-b'*(m/n)*n

        =b'*m+(a'-b'*(m/n))*n

  所以a=b';b=a'-b'*(m/n);

  可以推出依據a‘、b'可以盤算a、b。

代碼完成

void EGCD(int m,int n)
{
    int a,a1,b,b1,c,d,q,r,t;
    a1=b=1,a=b1=0,c=m,d=n;
    while(1)
    {
        q=c/d,r=c%d;
        if(r==0)
        {
            printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
            return;
        }
        c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
    }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved