只看楼主 举报 欧几里得辗转相除法求两个数的最大公约数

• 楼主

  葛小英

  话题：105

  精华：1

  积分：1914

  【算法设计思想】——欧几里得辗转相除法     

  （1）计算出a÷b的余数r；

  （2）若r=0，则b即为a，b的最大公约数
  （3）若r≠0，则把前面的除数b作为新的被除数a，把余数r作为新的除数b，继续运算，直到余数为0，此时的除数即为a，b的最大公约数；
     
  

     【算法】
     

  S1  输入两个正整数a，b

  S2  r =a÷b ；

  S3  如果r=0，那么转S6，否则转S4；

  S4  a← b

  S5  b← r，转S2；

  S6  输出b

  
  

   【项目活动】

  1.请同学们认真阅读欧几里得辗转相除法的设计思想，并理解算法描述

    试用辗转相除法的原理，写出204，85两个数的辗转相除过程

    a=204

    b=85

    r=?

    a=

    b=

    r=

    a=

    b=

    r=

  
  

  从而得出204与85的最大公约数是      。

  
  

  a	b	r
  204	85

  
  

  阅读：3266 回复：84 2022-04-11 10:48:49 举报

• 82楼

  钟宇文

  话题：0

  精华：0

  积分：

  a=380

    b=75

    r=

    a=

    b=

    r=

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  380	75	5
  75	5	0

  
  

  
  

  
  

  2022-04-15 14:53:41 举报

  还能输入140字
• 83楼

  黄佳玲

  话题：0

  精华：0

  积分：

  a=380

    b=75

    r=5

    a=75

    b=5

    r=0

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  380	75	5
  75	5	0\

  
  

  从而得出380与75的最大公约数是 5    。

  从而得出180与54的最大公约数是  18   。

  
  

  
  

  2022-04-15 14:54:39 举报

  还能输入140字
• 84楼

  李淑清

  话题：0

  精华：0

  积分：

   a=380

    b=75

    r=?

    a=

    b=

    r=

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  380	75	5
  75	5	0

  
  

  从而得出380与75的最大公约数是 5    。

  
  

  2022-04-15 14:56:21 举报

  还能输入140字