发布时间 : 星期日 文章服务类第1章算法与程序框图更新完毕开始阅读ea6785447ed5360cba1aa8114431b90d6c8589ad
随堂练习
1.仔细阅读下面的算法： 第一步 n=1，S=1；
第二步 n=n+1，S=S×n； 第三步 n=n+1，S=S×n； 第四步 输出n，S。
问：最后输出的n，S的值各为多少？ 2. 在例1 中，我们设计了一个算法，求出1+2+3+?+10的值，现在引入了变量并赋值，我们能不能将这个算法表述得更简洁、清楚一些，试一试。
想一想，前面我们学习了一些算法，你认为算法有哪些主要的特征？
新知
一般来说，一个有效的算法应该具有下面几个特征：
1. 有穷性 也就是说算法必须能在执行有限个步骤之后终止 ，即算法的步骤不能是无限的。
2. 可行性 算法的每一个步骤都是可执行的操作，即每一个步骤都可以在有限时间内完成。（也称为有效性）
3. 确切性 算法的每一步骤必须有确切的定义，不能存在歧义。
4. 输入项 一个算法有0个、一个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件。
5. 输出项 一个算法必须有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
例5 设计一个算法，从输入的5个数中找出最大值。 分析 这个算法的思路很简单，如果将每一个数看成是一颗豆子，可以将找最大值的算法形象地称为“捡最大的豆子”：首先将第一颗豆子放入口袋中， 从第二颗豆子开始比较，如果正在比较的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子，直到最后一颗豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。
解：算法为：
第一步 输入5个数a1，a2，a3，a4，a5； 第二步 M=a1
第三步 比较M，a2，如果M 第四步 比较M，a3，如果M 第五步 比较M，a4，如果M a4中的最大数） 第六步 比较M，a5，如果M a4，a5中的最大数） 第七步 输出M。 M即所求的最大值 上述算法中，第3、4、5、6步都要与上一步中得到的最大值M进行比较，得到新的最大值，并将它也记为M，M在整个过程中可以取不同的值，所以M是一个变量。 数学应用 小明有9枚一元的硬币，其中有一枚是假币，比真币略轻，你能用天平（不用砝码，天平的左右两个托盘都可以放物）将假币找出来吗？写出解决这个问题的算法。 分析 可以先取2枚，分别放在天平的左右两个托盘中，如果不平衡，则可以找出假币，如果平衡，则这2枚硬币都是真的，再依次与剩下的硬币一一比较，就能找出假币。 解：算法为： 第一步 从9枚硬币中任取2枚，分别放在天平的左右两个托盘中，如果天平的左右两边不平衡，则较轻的一边放的就是假币；如果天平的左右两边平衡，则这2枚硬币都是真的，就进行下一步； 第二步 取出左边托盘中的硬币，然后依次将剩下的硬币一一放在左边托盘进行称量，直到天平的左右两边不平衡，则较轻的一边放的就是假币。 想一想，用这种算法找出假币，最少要称几次，最多要称几次？还有没有其它解决这个问题的算法，使得称量的次数少一些呢？ 实际上，我们也可以用下面的算法： 第一步 将9枚硬币平均分成3组，每组3枚； 第二步 将其中的2组分别放在天平的左右两个托盘中，如果天平的左右两边不平衡，则假币就在较轻的那一组中；如果天平的左右两边平衡，则这2组中的硬币都是真的，假币就在第3组中； 第三步 从含有假币的那一组的3枚硬币中任取2枚，分别放在天平的左右两个托盘中，如果天平的左右两边不平衡，则较轻的一边放的就是假币；如果天平的左右两边平衡，则余下的那一枚就是假币。 很显然，这种算法只要称量2次就可以解决问题，一般会比前一种算法的称量次数要少得多。 一般来说，解决一个问题的算法可能不止一种，这些算法有优有劣，从这些算法中找出好的算法，也是算法理论的一个重要课题。 随堂练习 1.试写出求解一元一次方程3x?1??2x?4的一个算法。 2.现有一只能装3kg的水的水桶和一只能装5kg的水的水桶，请你设计一个算法，从水塘里取出4kg的水。 习题 1. 设计一个算法，将任意输入的3个数按从小到大的顺序输出。 2. 写出两个分数相加的算法。 3. 设计一个算法，从输入的4个数中找出最小值。 4. 你知道什么是素数吗？请你设计一个算法，判断6499是否为素数。 5. 写出一个算法，计算两个正整数的最大公约数。 6. 你知道什么样的年份是闰年吗？请设计一个算法，判断某个年份是否为闰年。 第二节 命题逻辑与条件判断 在设计算法解决实际问题的过程中，我们常常要对某些条件进行判断，这就需要我们学习一些命题逻辑的知识。 新知 能够判断真假的陈述句叫做命题。我们把正确的命题称为真命题，并记它的值为“真”，错误的命题称为假命题，并记它的值为“假”，一个命题的值只有两种：“真”（有时也记为1）和“假”（有时也记为0），一个命题非真即假，不可能既真又假，也不可能不真不假。 例如： （1）2+3=5. （2）雪是黑的. 都能够判断真假,所以它们都是命题，其中（1）是真命题，它的值为“真”，（2）是假命题，它的值为“假”。 只有能够判断真假的陈述句才是命题，一切没有判断内容的句子，无所谓真假的句子，如感叹句，疑问句，祈使句等都不能成为命题。 命题可以分成两种类型：第一种类型是只用一个简单的陈述句表达的命题，它不能分解为更简单的陈述句，这样的命题称为简单命题，也称为原子命题；第二种类型是由联结词将简单命题合法联结后所构成的命题，称为复合命题。常用的联结词有：??且??；??或??；如果??，那么??等。 例1 下列句子中，哪些是命题，哪些不是命题，如果是命题，指出它是真命题还是假命题，是简单命题还是复合命题。 （1） 2>5。 （2） x+y=1。 （3） 如果一个三角形的两个底角相等，那么这个三角形是等腰三角形。 （4） 你吃过中饭了吗？ （5） 火星上有生物。 （6） 禁止吸烟！ （7） 我正在说谎。 （8） 平行四边形的两组对边平行且相等。 （9） 今天天气真好啊！ （10） 在同一平面内的两条直线，或者平行，或者垂直。 分析 （1）、（3）、（5）、（8）、（10）是能够判断真假的陈述句，所以它们都是命题。其中（3）、（8）是真命题，（1）、（10）是假命题，（5）尽管到目前为止还无法确定真假，但就其本身而言是有真假的，之所以无法确定真假，是因为人类的认知水平还不够，所以我们认为（5）本身是个命题。（1）、（5）不能分解为更简单的陈述句，所以它们是简单命题，而（3）、（8）、（10）是由联结词将简单命题联结后所构成的，所以它们是复合命题。 （2）尽管也是陈述句，但是无法判断真假，（2）和（5）还有所不同，（5）就其本身而言是有真假的，但（2）本身就是没有真假的，因为不知x，y代表什么数。 （4）、（6）、（9）不是陈述句，都无所谓真假，所以都不是命题。 （7）是悖论，也不是命题。 解 （1）、（3）、（5）、（8）、（10）是命题，其中（3）、（8）是真命题，（1）、（10）是假命题，（5）到目前为止还无法确定真假，（1）、（5）是简单命题，而（3）、（8）、（10）是复合命题。 （2）、（4）、（6）、（7）、（9）都不是命题。 我们常用小写字母p,q,r,?等来表示命题，如