/ / / / / /

上一篇 下一篇 同標題 發表文章 文章列表

作者  weihan (天天天藍) 站內  CPP_project
標題  一堆數的 gcd
時間  Sun May 22 19:50:59 2005

這是看來的題目  我覺得很有趣  就試解一下

求 n 個數的 gcd ?

方法是兩兩求 gcd 然後遞迴至一個數為止



int  gcd ( int a , int b ) {
     if ( a >= b ) {
          return ( a % b == 0 ? b : gcd(b,a%b) ) ;
     } else {
          return ( b % a == 0 ? a : gcd(a,b%a) ) ;
     }
}

int main() {

    int i , j , m ;
    const int S = 9 ;
    int  no[S] = { 72 , 84 , 96 , 84 , 54 , 48 , 126 , 222 , 36 } ;
    int  gcds[S] ;

    for ( i = 0 ; i < S ; ++i ) gcds[i] = no[i] ;

    bool  even_no ;
    even_no = ( S % 2 == 0 ? true : false ) ;

    for ( i = S/2 ; i != 0 ; i /= 2 ) {
        for ( j = 0 ; j < i ; ++j ) {
            m = 2*j ;
            gcds[j] = gcd( gcds[m] , gcds[m+1] ) ;
        }
        if ( !even_no ) gcds[j] = gcds[2*j] ;
        even_no = ( (j+1) % 2 == 0 ? true : false ) ;
    }

    cout << gcds[0] << endl;

    system("pause") ;
    return 0 ;
}

--
===================================================================
*               人生的意義 : 盡責任  負責任                      *
*               人生的目的 : 受報  還願  行善                *
*               人生的價值 : 奉獻  付出                        *
================================================== 聖嚴法師  語 ===
--
發信站 [中央數學  織夢天堂 bbs.math.ncu.edu.tw]
   •FROM [220-134-25-64.HINET-IP.hinet.net]

上一篇 下一篇 同標題 發表文章 文章列表