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

• 楼主

  葛小英

  话题：104

  精华：1

  积分：1899

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

  （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

  
  

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

• 2楼

  陈柏亮

  话题：0

  精华：0

  积分：0

  欧几里得 希腊文:Ευκλειδης ，约公元前330年-公元前275年 ，古希腊数学家，被称为 几何之父 。

  2022-04-12 13:59:33 举报

  还能输入140字
• 3楼

  陈柏亮

  话题：0

  精华：0

  积分：0

  欧几里得 希腊文:Ευκλειδης ，约公元前330年-公元前275年 ，古希腊数学家，被称为 几何之父 。

  2022-04-12 13:59:33 举报

  还能输入140字
• 4楼

  陈铭涛

  话题：0

  精华：0

  积分：

  五  短除法

  2022-04-13 10:07:29 举报

  还能输入140字
• 5楼

  陈铭涛

  话题：0

  精华：0

  积分：

  质因数分解法

  2022-04-13 10:07:58 举报

  还能输入140字
• 6楼

  陈思琪

  话题：0

  精华：0

  积分：

  

  2022-04-13 10:25:32 举报

  还能输入140字
• 7楼

  周致棕

  话题：0

  精华：0

  积分：

  

  2022-04-13 10:27:55 举报

  还能输入140字
• 8楼

  陈俞霖

  话题：0

  精华：0

  积分：

  

  2022-04-13 10:28:20 举报

  还能输入140字
• 9楼

  张智轩

  话题：0

  精华：0

  积分：

  

  2022-04-13 10:36:05 举报

  还能输入140字
• 10楼

  宋子晗

  话题：0

  精华：0

  积分：

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

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

    a=204

    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-13 16:15:33 举报

  还能输入140字
• 11楼

  唐梓轩

  话题：0

  精华：0

  积分：

  
  

    a=204

    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-13 16:23:59 举报

  还能输入140字