第一章 如何用计算机解决 问题
第二节 算法描述与设计
一、算法是“灵魂”




1.算法存在于人们生活中，如：上街购物、 顾客付款、营业员找银等。 2.“韩信点兵问题”有不同的求解过程， 就有不同的算法。 有N个人，除以3，5，7，分别余2，3，2， 求N。 3.算法——解决问题的方法和步骤。 算法是尼克劳斯.沃斯（N.Writh）提出的， 他指出：算法+数据结构=程序。 （即算法不能单独构成程序，它必须和数 据结构合二为一）
5.算法的特征
练习： 水仙花数问题，如153=1^3+5^3+3^3， 分析它应满足什么条件才能使用此方法？

第一章 如何用计算机解决问题 第二节 算法描述与设计 为了能更好地理解什么是算法，我 们利用日常生活中的“打电话”和 “寄信”的例子来讨论。 方法：先由同学来口述过程。
“打电话” 的过程。
说出下面流程图的各框名称
开始框 输入框 处理框
判断框
处理框 处理框 处理框 输出框 结束框
小结 ： 什么是算法？ 解决问题的方法和步骤就是 算法
小结 ：
算法描述的方法有三种。
用自然语言来描述
用流程图来描述
用伪代码描述算法


使用伪代码描述算法没有严格的语法限制， 书写格式也比较自由，只要把意思表达清 楚就可以了，它更侧重于对算法本身的描 述。 在伪代码描述中，表示关键词的语句一般 用英文单词，其他语句可以用英文语句， 也可以用汉语语句。
伪代码的优缺点： 用伪代码描述的算法简洁、易懂， 修改起来也比较容易，并且很容 易转化为程序语言代码。 缺点是不是很直观。
3、用伪代码描述算法。
例如，给定一个四位数的年份，判断它是否为闰年。如果用伪代码来描述算法， 可以表示如下： 算法分析：我们知道，如果2月是28天，则这一年是平年；如果是29天，则这 一年是闰年。判断闰年的条件是：如果该年份能被4整除但不能被100整除， 或者能被400整除，则该年为闰年。 算法描述： 输入年份→y IF y能被4整除 THEN IF y 不能被100整除 THEN 输出“是闰年” ELSE IF y 能被400整除 THEN 输出“是闰年” ELSE 输出“不是闰年” END IF END IF ELSE 输出“不是闰年” END IF
自然语言的优点：通俗易懂。
缺点：容易产生歧义。
例如：
“这个人连老张也不认识”。
意思之一：这个人不认识老张。
意思之二：老张不认识这个人。
2、用流程图来描述。
什么是流程图？（也称 程序框图）它是算法的 一种图形化表示方法。
认识流程图符
流程图的优缺点
与自然语言相比，用流程图描述 算法形象、直观，更容易理解。
1、用自然语言来描述。 2、用流程图来描述。 3、用伪代码描述算法。
1、用自然语言来描述。
什么是自然语言。
人们日常生活中使用的语言
算法描述：
以“韩信点兵问题” 为例：
算法分析：
以“韩信点兵问题” 为例：
考虑：


凯撒密码的原理是将“明文”中的每个字母用 另外一个字母替换，这样就形成“密文”。已 知凯撒密码的计算公式为F(a)=(a+k) Mod n， k=3，n=26，如果将英文字母进行加密，其 对应关系如下所示： 明文：A B C D E F …… X Y Z 密文：D E F G H I …… A B C 现给出待加密字符串为“PROGRAM”，请同学 们设计算法,然后用自然语言将它描述出来。



我们曾在必须修课中提过一点算法，如：冒泡排序法。 例：计算1+2+3+……+100=？ 分析：这个算法有限制范围，可以在有限时间内完成， 这是算法的第一个特征：有穷性。计算此算法可以用纸笔、 算盘、运算器 和计算机来完成，且计算过程是多样的，但结果是唯一 的。这就是算法的可行性、确定性。 计算方法： ⑴把这100个数按顺序相加。 ⑵用凑数法：1+99=100，2+98=100， 3+97=100，……，49+51，最后只剩下50和100。 ⑶令S=0，使1≤n≤100，先执行S=S+n ⑴，再执行 n=n+1 ⑵ n=1，S=0时，S=1 n=2，S=1时，S=3 n=3，S=3时，S=6 n=4，S=6时，S=10 n=5，S=10时，S=15 n=6，S=15时，S=21 …… 算法的另外一个特征：输入、输出。
拿
忙音 拨 号 通了
起
听 筒
把听筒 放下
等会儿 再拨
通话
把听筒放下
结束
无人接听
把听封、 信纸、 笔、 邮票
开 信 封
写 信
贴 邮 票
把 信 投 入 到 邮 箱
第一章 如何用计算机解决问题
算法的概念：
解决问题的 方法和步骤 就是算法。
算法可以用多种方法来描述
4.算法的发现


世界上最早的算法 已知最早的算法是写在考古学家发掘出来的粘 土板上的，这些粘土板的年代大约是在公元前3000 年～公元前1500年，也就是大约3500～5000年以前。 考古学家是在美索布达米亚（伊拉克）靠近古代城 市巴比伦的地方发现的，那地方离现在的巴格达不 远。巴比伦人发明了六十进制系统，我们现在关于 时、分、秒的记法和关于角度的记法就是从他们那 里学来的。 为了做数学用表，巴比伦人需要解代数方程， 他们的做法是写个求解的“算法”。在算法中，基 本上都是对实际数目的计算。在算法的最后还写上 一句短语，这个短语可以粗略地翻译为“这是一个 过程”。这也是最早出现的程序设计语言的记号。