Question

利用輾轉(zhuǎn)相除法求7 252與5 328的最大公約數(shù)，并用basic語言寫出計(jì)算機(jī)程序.

     

Answer 1

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

    解：根據(jù)上述步驟得：

    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

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

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

    程序：

    Input “m,n=”;m,n

    r=m MOD n

    While r＜＞0

    m=n

    n=r

    r=m MOD n

    Wend

    Print “最大公約數(shù)”；n

    End