(
课件网) 05 循环分支运用 程序设计基础 学习目标 循环分支综合运用 0 1 穷举法应用 0 2 如果两个数都能够被一个数整除，则这个数就是两个数的公约数。 如，8 和 4 都可以被2整除，2就是 8 和 4的公约数。 公约数中最大的称为最大公约数。 如 8 和 4 都可以被2或4整除，2和4都是8 和 4的公约数。其中4最大，4就是8 和 4的最大公约数。 最大公约数 5-1 编程求204和85的最大公约数，有两种办法可以解决这个问题 应用穷举法。穷举法也叫枚举法或列举法。这种方法的主要思想是：在要解决的问题是由有限种情况组成时，把所有的情况一一列举出来，再对其一一进行判断和解决。 依次判断从1到85之间的数字，是否能够同时整除204和85 答案应该是17 最大公约数 5-2 最大公约数 5-3 应用辗转相减法。 辗转相减法的原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。 例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。 最大公约数 5-4 你认为两种算法，哪一种比较好？为什么？ 最大公约数 5-5 如果两个数都可以整除一个数，则这个数就是那两个数的公倍数。 如 6和8都可以整除48，48就是6和8的公倍数。公倍数中最小的称为最小公倍数。如 48、24都是6和8的公倍数，24是公倍数中最小的，是6和8的最小公倍数。 编程求204和85的最小公倍数。（答案应该是1020） 一种办法是穷举法，自己尝试编程序 最小公倍数 3-1 也可以借助最大公约数求最小公倍数，步骤： 一、利用辗除法或其它方法求得最大公约数； 二、 最小公倍数等于两数之积除以最大公约数。 举例：12和8的最大公约数为4 12×8/4=24 两数的最小公倍数是24 最小公倍数 3-2 你认为两种算法，哪一种比较好？为什么？ 最小公倍数 3-3 素数，又叫质数，是除了1和它本身之外再不能被其他数整除的自然数。 由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。 求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。 求素数 5-1 利用素数定义，编程求50个素数 试着改进算法，提高效率 求素数 5-2 求素数 5-3 改进建议： 第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不必再用其他的数去除。 第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。 第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。 求素数 4-3 求素数 4-4 循环分支综合运用 最大公约数 最小公倍数 求素数 穷举法应用 总结 ... ...
