算法与程序设计.ppt

《算法与程序设计.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章如何用计算机解决问题1.1计算机解决问题的过程1.2算法描述与设计1.3初试身手，体验编程游戏规则：点击Play开始游戏，把人和鬼都送到对岸，船上必须有一个人或鬼船才可以行驶，每次只能运送两个人或鬼，任何一边鬼都不能比人多，否则鬼吃人，游戏结束。①人是如何解决问题的？首先观察分析问题收集必要的信息根据已有的知识、经验进行判断、推理尝试按一定的方法和步骤解决问题1.1计算机解决问题的过程1.1计算机解决问题的过程我国汉代有位大将军叫韩信，他在点兵时让士兵分别从1~3、1~5、1~7报数，然后报告各次报数的余数，这样，他就能推算出总共有多少士兵。“今有物不知其数，三三数之余二，五五数之

2、余三，七七数之余二，问物几何？”“韩信点兵问题”韩信是我国西汉初著名的军事家。韩信点兵，多多益善，不仅如此，还能经常以少胜多，以弱胜强。在与楚军决战时韩信指挥诸侯联军，在垓下十面埋伏，击败楚军，楚霸王项羽因此自杀。②计算机解决问题的过程算法1：列举法；算法2：最小公倍数法；算法3：列方程式法；1.1计算机解决问题的过程②计算机解决问题的过程活动：实例韩信点兵趣解“鬼谷算”、“隔墙算”、“秦王暗点兵”在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?”明代，数学家程大位把这个问题的算法编成了四句歌诀：三人同行七十稀，五树梅花廿一枝；七子团圆正半月，

3、除百零五便得知。讨论：学生交流用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。《孙子算经》中解决此问题的算法是：70×2＋21×3＋15×2＝233，233－105－105＝23，所以这些物品最少有23个。韩信带1500名兵士打仗，战死四五百人，站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：10491.1计算机解决问题的过程“韩信点兵问题”韩信是我国西汉初著名的军事家。韩信点兵，多多益善，不仅如此，还能经常以少胜多，以弱胜强。在与楚军决战时

4、韩信指挥诸侯联军，在垓下十面埋伏，击败楚军，楚霸王项羽因此自杀。②计算机解决问题的过程问题分析解决被3整除余2被5整除余3被7整除余25、8、11、14、17、20、23、268、13、18、23、28、33、389、16、23、30、37、4423算法：列举法；开始N被3、5、7整除余数为2、3、2N=N+1结束NYN=1输出N值②计算机解决问题的过程1.1计算机解决问题的过程用列举法，利用存储量大、运算速度快、精确度高，可以按人们设定的程序重复执行等特点。②计算机解决问题的过程1.1计算机解决问题的过程自然语言是不能被计算机执行的。自然语言计算机程序程序设计——思想程序设计语言——编写工

5、具机器语言汇编语言高级语言计算机010101110001011100101110……②计算机解决问题的过程1.1计算机解决问题的过程1.2算法描述与设计算法1：列举法；算法2：最小公倍数法；算法3：列方程式法；首先观察分析问题思考设计算法解决问题分析问题设计算法编写程序调试运行解决问题开始③人机“问题解决”对比1.1计算机解决问题的过程1.2算法描述与设计①什么是算法算法就是解决问题的方法和步骤。算法就程序设计的“灵魂”。算法+数据结构=程序；算法独立于任何具体的程序设计语言；“韩信点兵问题”VB语言编程VC语言编程C语言编程1.2算法描述与设计②算法的特征有穷性；确定性；输入；输出；可行性

6、；算法要有一个清晰的起始步，表示处理问题的起点，且每一个步骤只能有一个确定的后继步骤(1算法的确定性)，从而组成一个步骤的有限序列(2算法的有穷性)；要有一个终止步(序列的终止)表示问题得到解决或不能得到解决；每条规则必须是确定的、可行的(3算法的可行性)、不能存在二义性。算法总是对数据进行加工处理，因此，算法的执行过程中通常要有数据4输入(0个或多个)和数据5输出（至少一个）的步骤。如：请输入您的密码：判断：密码是否为aaa；若是，退出，否则继续输入；1.2算法描述与设计②描述算法1、将N的初始值赋为12、如果N<100并且N被3、5、7整除后余数为2、3、2，则输出N的值，转入第4步；3

7、、将N的值加1,转到第2步；4、结束程序自然语言自然语言优点通俗易懂缺点缺乏直观性简洁性，容易产生歧义如：“张先生对李先生说他的孩子考上了大学”。请问是张先生的孩子考上大学，还是李先生的孩子考上大学呢？韩信点兵问题1.2算法描述与设计②描述算法流程图流程图是通过箭头相互连接的几何图形来表达的方法。=程序框图ANSI规定的一些常用流程图符号。起止框输入输出框判断框处理框连接点流程线开始N被3、5、7整除余数为2