The greatest common divisor gcd(最大公約数)

2600 ワード
アルゴリズム gcd
文章の一部には大神を参考にして共に努力するところがある.
最大公約数のアルゴリズムと言えば、一番熟知しているのは転々とした割り算で、もう一つはユークリッドアルゴリズムです. algorithm)最大公数を求める時、転々相除法は以下の性質を利用して二つの正の整数を確定します. a. 和 b の最大共通因子の値:
1. 若し r はい、 a. ÷ b の余り、 gcd(a,b) = gcd(b,r)
2. a. その倍数の最大共通因子は aです
もう一つの書き方は:
1. a. ÷ b、令rは所得剰余(0≦r＜b)であり、もし r = 0,アルゴリズム終了;b 答えです
2. セット a←b、b←r、そして第一歩に戻る.
第一の書き方は再帰的に実現することです.第二の方法は、転々とした過程をより明確に見ることができます.実現コードは以下の通りです.
int gcd(int m,int n)   //   
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//  ：  n=gcd(a,b);
int gcd(int m,int n)   //   
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//  ：  n=gcd(a,b);
今日初めて他の最大公約数アルゴリズムを理解しました.もっと相減損法(等値アルゴリズム)は、個人的にも転々相減法として理解できると思います.
ここで百科を借りてその原理を説明します.「九章算術」は中国古代の数学専門書で、その中の「更相減損術」は2つの数の最大公約数を求められます.すなわち「半者半之、半可可可可以者半之、副置分母、子の数は少なく少なく、更に相減損して、それ等も求められます.」は現代語に訳して次のようになります.  第1ステップ:正の整数を任意に与え、それらが偶数であるかどうかを判断する.もし2で約簡するならば.第二ステップを実行しない場合.第二ステップ:大きな数でより小さい数を減らし、続いて所得の差をより小さい数と比較し、大きな数で小数を減らす.この操作は、得られた減数と差が等しくなるまでループします.第一歩の中で約束したいくつかの2と第二歩の中ぐらいの数の積は求められた最大公約数です.その中で「等数」というのは、最大公約数です.「等数」を求める方法は「更相減損」法です.
コードは以下の通りです
int gcd(int m,int n)   //      
{
    while(m!=n)     //    
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
}
実現コードは以下の通りです.私は小水に属していますので、簡単なものは忘れやすいです.コードにはいくつかの変数交換方式が付加されています.
#include 
#include 
using namespace std;

int gcd(int m,int n)   //   
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}

/*
int gcd(int m,int n)   //      
{
    int p;
    while(n)
    {
      p=m%n;
      m=n;
      n=p;
    }
    return m;
}

int gcd(int m,int n)   //      
{
    while(m!=n)
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
} 
 */

void swap(int &m,int &n)   //   ，     (    )
{
     int temp;
     temp=m;
     m=n;
     n=temp;     
 } 

/*void swap(int *m,int *n)  //  ，     
{
     int temp;
     temp=*m;
     *m=*n;
     *n=temp;
 } 
   ：swap(&m,&n); 
 
 int swap(int &m,int &n)    //      ，   (         )
 {
     m=m+n;
     n=m-n;
     m=m-n; 
 } 
   ：swap(m,n);
  
 int swap(int &m,int &n)
 {
     m=m^n;
     n=n^m;
     m=m^n;
 } 
   ：swap(m,n);
 */
 
int main()
{
     int a,b;
     
     while(1)
     { 
     printf("please enter the two positive integers: ");
     scanf("%d%d",&a,&b);
     if(a
167プログラミングして全配列アルゴリズムを実現してください.
微信紅包アルゴリズムコード実現