Linux Cワンストップ学習練習問題回答5.3.1最大公約数

1142 ワード

1、再帰関数を作成して2つの正の整数abの最大公約数(GCD,Greatest Common Divisor)を求め、Euclidアルゴリズムを使用する.
  • abで割ると、最大公約数はbです.
  • それ以外の場合、最大公約数はbおよびa%bの最大公約数に等しい.

  • Euclidアルゴリズムは証明しやすいので、読者自身がなぜこのように計算すれば最大公約数を算出できるのかを証明してください.最後に、正の整数だけでなく、すべての整数に適用するようにプログラムを変更します.
    #include<stdio.h>
    /*GCD of a and b*/
    
    int gcd (int a,int b)
    {
        if (a<0)
    	{a=-a;}
        if (b<0)
    	{b=-b;}
    
    
    /*    if ( a < b )
        {  int c = a ;
    	a = b ;
    	b = c ;     
        }*/
        int c = a % b ;
        if (c!=0)
        {
    	a = b;
    	b = c;
    	int result=gcd ( a,b );
    	return result;
        }
        else
    	{
    	int result = b;
    	return result;
    	}
    }
    
    int main()
    {
        int a,b;
    
        printf("please enter a and b:");
        scanf("%d%d",&a,&b);
        if ( a*b==0 )
    		{
    		printf("ERROR!!!
    The number you put can't be 0!
    "); return 0; } int result=gcd(a,b); printf("The GCD of %d and %d is %d
    ",a,b,result); return 0; }

    転載はソースアドレスを明記してください.http://blog.csdn.net/whorus1/article/list/2あ、ありがとう!