|
首先我们来了解以下几个概念 一、递归，就是在运行的过程中调用自己。 1. 子问题须与原始问题为同样的事，且更为简单； 2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。 经典的递归例子如：汉诺塔问题、斐波那契数列（之前用循环实现过，有兴趣可以在本节后修改一下用递归来计算） 二、更相减损法 我们这个例子选择的是用更相减损法求最大公约数，当然还有一种方法（辗转相除法，在此不再展开讲述，有兴趣的可以自己实现） 更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。 三、scratch新建功能模块 Scratch2.0“更多模块”中允许用户“新建功能模块”,我们新建的功能模块类似于一般程序设计语言中的过程或函数，通过自定义功能模块可以使我们的程序更简洁，修改更方便。 实现步骤： 1、新建必要的变量（m:第一个数；n:第二个数；k:两数相减差值；min：两个数中较小的） 2、新建功能模块（如图所示，点开选项，可以添加数字参数和文本标签） 3、我们让用户输入两个数并分别存入变量m、n，然后直接调用求最大公约数的模块传入参数m、n 4、实现最大公约数模块，根据更相减损法定义，如果两个数相等那么最大公约数就是自身，否则取两数差值的绝对值k，然后再把差值k和较小的一个数min作为参数开始递归调用求最大公约数的模块，直至差数和较小的数相等，然后让角色回答最大公约数是多少，结束程序。 |
|
|
