《Raptor程学设计案例教程》清华大学出版社

P18-6 计算复活节的日期 运用raptor

算法：本题算法在题目中已经很明确，是一个顺序结构和选择结构的程序，按照7个步骤实现就可以了

P18-7  计算上下五千年共有多少个闰年 运用raptor

闰年的计算算法是：输入年，能被4整除但不能被100整除,或能被400整除.关键是前5千年怎么计算的问题,前5千年可以输入负数年份,然后取绝对值进行计算

这个题的循环次数是-2986年到2014年.

P19-10 蚂蚁爬格的问题 运用raptor

算法：1、定义天数d的初值为1，b为步数值为0

      2、根据天数计算蚂蚁走的步数：

         3的倍数后退7步

         5的倍数后退3步

         7的倍数后退5步

         都不是，b=(d mod 3)+ (d mod 5)+ (d mod 7)

      3、天数增加1 ，d=d=1

      4、判断是否100天，不到100天，跳转到2，否则跳转到5

      5、输出蚂蚁的步数

P47-6 输入2个数，求最大公约数和最小公倍数 运用raptor

最大公约数算法：

辗转相除法

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

可以写成右边的格式。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

更相减损法

更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

例1．用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

这个过程可以简单的写为：

（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.

这里的程序是辗转相除法，更相相减法大家可以自己编程试试。

最小公倍数算法：定理：两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。可见求出了最大公约数，最小公倍数就很好求了