Question

利用輾轉相除法求7 252與5 328的最大公約數，并用basic語言寫出計算機程序.

     

Answer 1

分析：輾轉相除法的主要步驟是：（1）用小的一個數除大的一個數，得第一個余數；（2）用第一個余數除小的一個數，得第二個余數；（3）用第二個余數除第一個余數，得第三個余數；（4）逐次用后一個余數去除前一個余數，直到余數為0為止.那么最后一個除數就是所求的最大公約數.

    解：根據上述步驟得：

    7 252=5 328×1+1 924

    5 328=1 924×2+1 480

    1 924=1 480×1+444

    1 480=444×3+148

    444=148×3+0

    最后得到的除數148，即7 252與5 328的最大公約數為148.

    要寫出程序，先作出程序框圖：

    程序：

    Input “m,n=”;m,n

    r=m MOD n

    While r＜＞0

    m=n

    n=r

    r=m MOD n

    Wend

    Print “最大公約數”；n

    End