第二部分算法与程序设计(选修)主题1算法与程序设计1.1算法1.1.1计算机解决问题的过程知识点1：人是如何解决问题的【知识链接】本考点要求学生达到“了解”水平。
解决问题的过程可以总结为：观察、分析问题，收集必要的信息，尝试按照一定的方法和步骤解决问题。
一般来说，同一个问题可以有多种解决方法，但不同的方法有优劣之分。
评价一种方法的优劣要与具体情况相结合。
要理解本考点的内容除了用教科书中“韩信点兵”的例子外，还可以举出其他一些例子，例如：最小公倍数问题、班级活动的设计等。
【技能扫描】培养将生活中的实例整理成条理化步骤的好习惯，提高自己的逻辑思维和语言叙述能力。
体会逻辑关联词“如果……那么……”、“或者”、“并且”、“否则”的含义，能把这些逻辑关联词翻译成数学“语言”。
【典型题析】1. 分析“这个人谁都不认识”的含义，体会同一种叙述在不同语境中可以表达不同的意思。
分析：第一种解释是在场的所有人都不认识这个人(这个人是被认识的对象)；第二种解释是这个人不认识在场的所有人。
2．张三有一杯咖啡，李四有一杯牛奶，在不交换杯子的前提下如何交换两人的饮料。
分析：设张三的杯子为X，李四的杯子为Y，找一个空杯子T。
将X杯中的咖啡倒入T杯中，将Y杯中的牛奶倒入X杯中，再将T杯中的咖啡倒入Y杯中即可。
可以写成X→T，Y→X，T→Y。
【模拟练习】1．把从早晨起床到学校的过程整理成算法(解决问题的方法和步骤)并表述出来。
2．一个侦探逮捕了5个嫌疑犯b因为这5个人供出的作案地点各有出入，进一步审讯后，他们分别提出了如下的申明。
A：5个人当中有1个人说了谎。
B：5个人当中有2个人说了谎。
C：5个人当中有3个人说了谎。
D：5个人当中有4个人说了谎。
E：5个人全说了谎。
然而只能释放说真话的人，请问该释放谁呢?3．小明有一盒刘德华的歌曲磁带，小云有一盒梁咏琪的歌曲磁带，在不交换磁带的基础上，怎样将两盒磁带上的歌曲对录到对方的磁带上。
参考答案：1．略2．提示：假如E说的是真的，即五个人都说了谎，则A、B、C、D、E都说了谎，自相矛盾，排除；假如D说的是真的，即有四个人说了谎，则A、B、C、它都说了谎，刚好是四个人说了谎，正确；假如C说的是真的，即有三个人说了谎，则A、B、D、E都说了谎，四个人说了谎，故C为假；假如B说的是真的，即有二个人说了谎，则A、C、D、E都说了谎，B为假；假如A说的是真的，即只有一个人说了谎，则B、C、D、E都说了谎，矛盾，故也为假。
故只能放D。
3．提示：典型题析2中交换两种饮料和本题中的磁带对录问题，都与计算机算法中将要解决的“交换两个变量的值”的问题类似，理解这种解决问题的方法，才能写出解决问题的步骤。
知识点2：计算机解决问题的过程【知识链接】本考点要求学生达到“了解”水平。
计算机程序(Computer Program)是指示计算机如何去解决问题或完成任务的一组可执行的指令。
程序设计(Program Design)是寻求解决问题的方法，并将其实现步骤编写成计算机可以执行的程序的过程。
程序设计语言(Program Language)泛指一切用于书写计算机程序的语言。
注意：程序设计语言和计算机语言(Computer Language)是两个不同的概念，程序设计语言是一种重要的计算机语言。
计算机解决问题和人解决问题有着本质的区别：计算机解决问题要经历分析问题、确定算法、编程求解等基本过程。
计算机解决问题的流程如下：开始结束编写程序日寸，首先要对问题进行详细的分析，明确已知条件下的初始状态及要达到的目标，找出求解问题的方法和过程，并抽取出一个数学模型，形成算法；然后将这个数学模型连同它要处理的数据，用计算机能识别的方式描述出来，使之成为计算机能处理的对象；最后用程序设计语言设计出具体的问题求解过程，形成计算机程序。
IBM公司的“深蓝”能够战胜国际象棋大师卡斯帕罗夫，原因是人们将国际顶尖象棋大师在过去100年问开局和终局的数十亿范例存入计算机数据库，针对卡斯帕罗夫每一步的对弈，计算机都从数据库中查找能够取胜的应对步骤。
所以不是“深蓝”战胜了卡斯帕罗夫，而是缜密的计算机程序战胜了卡斯帕罗夫。
【技能扫描】利用类比的方法体会计算机解决问题和人解决问题的异同，锻炼类比、推理的能力。
【典型题析】与人解决问题相比，计算机解决问题的优势有哪些?劣势是什么?分析：计算机具有存储量大、运算速度快、精确度高、可重复执行命令等优点，这些优势是人无法比拟的，但计算机也有自身的劣势，那就是它无法完成随意性强、无逻辑性的随机问题，计算机只是一个高级工具。
到目前为止，还没有一台真正具有人类智能的计算机。
【模拟练习】1．IBM公司的“深蓝”能够战胜国际象棋大师卡斯帕罗夫是因为()。
A．计算机具有很高的智商B．计算机具有很快的运算速度C．计算机事先装载了很多棋局D．计算机能根据装载的棋局，经过程序判断作出对弈选择2．利用计算机解决问题的过程描述中，以下说法正确的是()A．编写程序→调试程序→分析问题→设计算法B．分析问题→编写程序→调试程序→设计算法C．分析问题→设计算法→编写程序→调试程序D．分析问题→设计算法→调试程序→编写程序3．名词解释：计算机程序程序设计程序设计语言参考答案：1. D 2. C 3. 略1.1.2算法的描述方法知识点1：算法【知识链接】本考点要求学生达到“了解"水平。
算法在计算机程序设计中占有重要地位，是程序设计的“灵魂”。
世界著名计算机科学家尼克劳斯·沃斯(N ．Wirth)指出：算法+数据结构(Data Structure)=程序。
算法具有以下特征。
(1)有穷性：一个算法必须保证执行有限步之后结束。
(2)确切性：算法的每一个步骤必须有确切的定义。
(3)输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身确定了初始条件。
(4)输出：一个算法至少有一个输出，用以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。
(5)可行性：原则上算法能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
已知最早的算法是考古学家发掘出来的大约在3500~5000年以前的写在黏土板上的。
当时为了做数学用表，巴比伦人需要解代数方程，他们的做法是写出求解的“算法”。
这些算法基本上都是对实际数目的计算。
在算法的最后还附有一个短语，这个短语可以粗略地翻译为“这是一个过程”。
这也是最早出现的程序设计语言的标记。
【技能扫描】通过数学例子，运用类比的方法，加强对算法概念的理解，借鉴数学家解决问题的技巧，尝试运用算法解决问题。
【典型题析】1. 数学中求1+2+3+…+100的和s 。
高斯用凑数法：1+100，2+99，…，50+51，然后求和。
写出高斯求解问题的算法。
分析：用凑数法求1+2+3+…+100的和时，每一组数的和都相等(和为101)，而且共有50组数。
考虑算法的通用性，类似这种求和的算法可描述为：输入最大项数n ；列式s=(1+n)×n/2；输出s 的值。
【模拟练习】1. 写出求解1-2+3-4+…+99-100的和s 的算法。
2. 水仙花数是指一个三位数，它的各位数的立方和正好等于该数本身，如：153=333351++，写出求解水仙花数问题的算法。
参考答案：1. 提示：循环使用求和公式：s=s+k*i ，k 为每一项的符号：k=1)-i *(2(-1)。
2. 提示：首先用循环的方法找到所有的三位数，每找到一个数(用x 来表示这个数)就分解当前这个三位数，百位上的数字a=Int(x/100)，十位上的数字b=Int((x-a*100)/10)，个位上的数字c=x-a*100-b*1，再判断x=333c b a ++是否成立，若判断结果为真，则x 为水仙花数。
知识点2：如何描述算法【知识链接】本考点要求学生达到“了解”水平。
算法的描述方法有自然语言、流程图、伪代码三种形式。
自然语言描述算法的优点是“描述”接近自然语言，通俗易懂，符合人们的表达习惯，容易接受。
缺点是缺乏直观性和简洁性，在算法表述中容易产生歧义。
流程图是算法的图形化表示，其描述算法形象、直观、容易理解。
目前常用的流程图是由美国国家标准化协会(American National Standard Institute，简称ANSI)制定的一系列流程图符号组成(见教科书中的流程图符号)的。
伪代码(Pseudo code)是介于自然语言和计算机程序设计语言之间的一种算法描述。
伪代码一般用逻辑关键词连接自然语言或表达式的形式来表述算法。
因为算法具有多样性，到底用什么算法描述一个问题，要具体问题具体分析。
【技能扫描】因势利导，培养用算法描述问题的能力，训练正确解决问题的方法，并把数学课中的问题用算法描述出来，达到学科相融的目的。
【典型题析】1．将求闰年问题的算法用自然语言、流程图、伪代码三种方法描述。
分析：用自然语言描述闰年问题：Step1：输入年份→yStep2：如果y能被400整除，则输出“是闰年”，结束程序；否则转到Step3Step3：如果y能被4整除但不能被100整除，则输出“是闰年”，结束程序；否则转到Step4 Step4：输出不是“闰年”，结束程序。
用流程图描述闰年问题：用伪代码描述闰年问题：输入年份→yIf y能被400整除Then输出“是闰年”ElseIf y能被4整除And y不能被100整除Then输出“是闰年”Else输出“不是闰年”End IfEnd If2．下面关于算法的说法错误的是()。
A．算法必须有输出B．算法必须在计算机上用某种语言实现．C．算法不一定有输入D．算法必须在有限步执行后能结束分析：算法就是解决某一特定类型问题的有限运算序列。
一个算法必须在执行有限步之后能结束；算法中的每一步必须有确切定义；一个算法有0个或多个输入，也必然有一个或多个输出。
算法不等同于程序。
一个程序，譬如一个操作系统，只要不关机，它就不会结束。
算法的设计可以避开具体的计算机和程序设计语言，也可以借助程序设计语言中提供的数据类型及运算在具体的层次上实现。
参考答案：B【模拟练习】1．恺撒密码编写的信息如下：Krz duh brx? 你能用自然语言描述翻译密码的算法吗?小知识：公元前60年(两千多年前)，古罗马统帅“朱利叶斯·恺撒”(Caesar)，用当时发明的“恺撒密码”书写军事文书，用于战时通信。
后来他成了古罗马帝王，就是“恺撒”大帝。
恺撤加密法，就是字母替换加密，即把消息中每一个字母换成其后的第三个字母。
例如：原文：abcdefghijklmnopqrstuvwxyz或者ABCDEFGHIJKLMNOPQRSTUVWXYZ密文：defghijklmnopqrstuvwxyzabc或者DEFGHIJKLMNOPQRSTUVWXYZABC2．下面说法正确的是()。