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

• 楼主

  葛小英

  话题：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

  
  

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

• 52楼

  王燊柯

  话题：0

  精华：0

  积分：

   a=180

    b=54

    r=18

    a=54

    b=18

    r=0

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

  
  

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

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

  
  

  
  

  2022-04-15 11:56:30 举报

  还能输入140字
• 53楼

  宋科霖

  话题：0

  精华：0

  积分：

  
  

  a=380

    b=85

    r=34

    a=85

    b=34

    r=17

    a=34

    b=17

    r=0

  或者用表格来表示

  a	b	r
  204	85	34
  85	34	17
  34	17	0

  
  

  2022-04-15 11:56:43 举报

  还能输入140字
• 54楼

  韩红

  话题：0

  精华：0

  积分：

  a=180

    b=54

    r=18

    a=54

    b=18

    r=0

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

  
  

  
  
  

  
  

  2022-04-15 11:56:45 举报

  还能输入140字
• 55楼

  林锐

  话题：0

  精华：0

  积分：

  a=180

    b=54

    r=18

    a=54

    b=18

    r=0

    a=

    b=

    r=

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

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

  2022-04-15 11:57:44 举报

  还能输入140字
• 56楼

  张子豪

  话题：0

  精华：0

  积分：

      

    a=180                                                                              b=54                                                                              r=?

    a=180

    b=54

    r=18

    a=54

    b=18

    r=0

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

  
  

  
  

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

  
  

  2022-04-15 11:59:02 举报

  还能输入140字
• 57楼

  李诗颖

  话题：0

  精华：0

  积分：

   a=180

    b=54

    r=18

    a=54

    b=18

    r=0

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

  
  

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

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

  
  

  2022-04-15 12:00:52 举报

  还能输入140字
• 58楼

  廖籽睿

  话题：0

  精华：0

  积分：

  a=180

    b=54

    r=18

    a=54

    b=18

    r=0

    a=18

    b=0

    r=0

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0
  18	0	0

  
  

  
  

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

  
  

  
  

  2022-04-15 12:01:11 举报

  还能输入140字
• 59楼

  吴祖愉

  话题：0

  精华：0

  积分：

    a=180

    b=54

    r=？

    a=180

    b=54

    r=18

    a=54

    b=18

    r=0

  或者用表格来表示

  a	b	r
  180	54	18
  54	18	0

   

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

  
  

  
  

  2022-04-15 12:01:21 举报

  还能输入140字
• 60楼

  李沁颖

  话题：0

  精华：0

  积分：

  a	b	r
  380	75	5
  75	5	0

  
  

  2022-04-15 14:38:59 举报

  还能输入140字
• 61楼

  陈诗怡

  话题：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:40:21 举报

  还能输入140字