首先我们来了解以下几个概念

  一、递归,就是在运行的过程中调用自己。

    1. 子问题须与原始问题为同样的事,且更为简单;

    2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

    经典的递归例子如:汉诺塔问题、斐波那契数列(之前用循环实现过,有兴趣可以在本节后修改一下用递归来计算)

  二、更相减损法

    我们这个例子选择的是用更相减损法求最大公约数,当然还有一种方法(辗转相除法,在此不再展开讲述,有兴趣的可以自己实现)

    更相减损法:也叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,就是对于给定的两个数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,再用较大的数减去较小的数,反复执行此步骤直到差数和较小的数相等,此时相等的两数便为原来两个数的最大公约数。

  三、scratch新建功能模块

    Scratch2.0“更多模块”中允许用户“新建功能模块”,我们新建的功能模块类似于一般程序设计语言中的过程或函数,通过自定义功能模块可以使我们的程序更简洁,修改更方便。

   实现步骤:

  1、新建必要的变量(m:第一个数;n:第二个数;k:两数相减差值;min:两个数中较小的)

  scratch递归算法实例-求两数的最大公约数

  2、新建功能模块(如图所示,点开选项,可以添加数字参数和文本标签)

  scratch递归算法实例-求两数的最大公约数

  3、我们让用户输入两个数并分别存入变量m、n,然后直接调用求最大公约数的模块传入参数m、n

  scratch递归算法实例-求两数的最大公约数

  4、实现最大公约数模块,根据更相减损法定义,如果两个数相等那么最大公约数就是自身,否则取两数差值的绝对值k,然后再把差值k和较小的一个数min作为参数开始递归调用求最大公约数的模块,直至差数和较小的数相等,然后让角色回答最大公约数是多少,结束程序。

  

本站内容未经许可,禁止任何网站及个人进行转载。

   口袋儿题库-青少儿编程自测题库