星期三, 1月 18, 2006

[.Net]最大公因數/輾轉相除法

在某論壇看到討論最大公因數的討論串,裡面有提到輾轉相除法.
老實說,當我看到最大公因數,我只想到暴力法.
從 1...n 開始 iterate, 能整除,表示是因數,把這些數字記起來,於是我們得到兩個集合.這兩個集合的交集,表示是共通因數,最大者則為最大公因數.

完全忘記有輾轉相除法這玩意兒,一時興起,port 到 c# 試試看.

using System;
using System.Collections;

public class MyClass
{
    public static int GCD( int a, int b )
    {
        if( a % b == 0 )
            return b;
        return GCD( b, a%b );
    }
    
    public static void Main()
    {
        int num1=1230, num2=460, num3=10;
        
        int result1 = GCD( num1, num2 );
        int result2 = GCD( result1, num3 );
        
        Console.WriteLine( "The GCD of {0} and {1} is {2}", num1, num2, result1 );
        Console.WriteLine( "The GCD of {0} and {1} is {2}", result1, num3, result2 );
        
        RL();

    }
    
    #region Helper methods
    private static void RL()
    {
        Console.ReadLine();    
    }
    #endregion
}

沒有留言:

您或許對這些文章有興趣

Related Posts Plugin for WordPress, Blogger...