算法描述与设计

第一章如何用计算机解决问题1.1计算机解决问题的过程1.2算法描述与设计1.3初试身手，体验编程游戏规则：用没有刻度的3毫升量杯和5毫升量杯，如何量出一毫升的水？①人是如何解决问题的？首先观察分析问题收集必要的信息根据已有的知识、经验进行判断、推理尝试按一定的方法和步骤

解决问题1.1计算机解决问题的过程1.1计算机解决问题的过程我国汉代有位大将军叫韩信，他在点兵时让士兵分别从1~3、1~5、1~7报数，然后报告各次报数的余数，这样，他就能推算出总共有多少士兵。

“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”“韩信点兵问题”韩信是我国西汉初著名的军事家。韩信点兵，多多益善，不仅如此，还能经常以少胜多，以弱胜强。在与楚军决战时韩信指挥诸侯联军，在垓下十面埋伏，击败楚军，楚霸王项羽因此自杀。②计算机解决问题的过程算法1：列举法；算法2：最小公倍数法；算法3：列方程式法；开始N被3、5、7整除余数为2、3、2N=N+1结束NYN=1输出N值②计算机解决问题的过程1.1计算机解决问题的过程用列举法，利用存储量大、运算速度快、精确度高，可以按人们设定的程序重复执行等特点。②计算机解决问题的过程1.1计算机解决问题的过程自然语言是不能被计算机执行的。自然语言计算机程序程序设计——思想程序设计语言——编写工具机器语言汇编语言高级语言计算机010101110001011100101110……②计算机解决问题的过程1.1计算机解决问题的过程1.2算法描述与设计①什么是算法算法就是解决问题的方法和步骤。算法就程序设计的“灵魂”。算法+数据结构=程序；算法独立于任何具体的程序设计语言；#include<stdio.h>main(){intn=1;while(n<1100){if(n%3==2&&n%5==3&&n%7==2){printf("%d\n",n);break;}elsen++;}}C语言JAVA语言DimnasintegerN=1Doif(nmod3=2)and(nmod5=3)and(nmod7=2)thenPrintnExitdoEndifN=n+1LoopVB语言1.2算法描述与设计②算法的特征有穷性；确定性；输入；输出；可行性；

算法要有一个清晰的起始步，表示处理问题的起点，且每一个步骤只能有一个确定的后继步骤(1算法的确定性)，从而组成一个步骤的有限序列(2算法的有穷性)；要有一个终止步(序列的终止)表示问题得到解决或不能得到解决；每条规则必须是确定的、可行的(3算法的可行性)、不能存在二义性。算法总是对数据进行加工处理，因此，算法的执行过程中通常要有数据4输入(0个或多个)和数据5输出（至少一个）的步骤。如：请输入您的密码：判断：密码是否为aaa；若是，退出，否则继续输入；练习①s=1②将s的值增加1③重复步骤②解答：该算法的步骤②将被重复执行无穷次，不符合①有穷性第1题① L=10② 输出L/自然数解答：自然数没有具体指明是哪个数，不符合算法的②确定性第2题① R=2② S=3.14*R*R③ 输出面积S说明：该算法中在执行时已包含计算所需的初始数据，不必另外提供数据，因此没有输入，即有0个输入。第3题① 输入圆的半径R② S=3.14*R*R③ 输出面积S说明：该算法中计算面积所需的初始数据半径R待定，需要在算法执行时从键盘多个输入。第4题① 输入圆的半径R② S=3.14*R*R③ C=2*3.14*R④ 输出面积S，周长C说明：通过前两个例子可以知道，算法可能有1个或多个输出。第5题① x=-2② 计算x的平方根解答：x是负数，没有平方根，该算法不可行，不符合算法的可行性。第6题1.2算法描述与设计②描述算法1、将N的初始值赋为12、如果N<100并且N被3、5、7整除后余数为2、3、2，则输出N的值，转入第4步；3、将N的值加1,转到第2步；4、结束程序自然语言自然语言优点通俗易懂缺点缺乏直观性简洁性，容易产生歧义如：“这个人连老张也不认识”。意思1：这个人不认识老张；

意思2：老张不认识这个人；韩信点兵问题1.2算法描述与设计②描述算法流程图流程图是通过箭头相互连接的几何图形来表达的方法。=程序框图ANSI规定的一些常用流程图符号。起止框输入输出框判断框处理框连接点流程线开始N被3、5、7整除余数为2、3、2N=N+1结束NYN=1输出N值1.2算法描述与设计②描述算法流程图韩信点兵问题流程图优点形象、直观、更容易理解缺点1.2算法描述与设计②描述算法伪代码是介于自然语言和计算机程序之间的一种算法描述。伪代码优点书写自由，专业缺点N=1DOifN除以3余2且N除以5余3且N除以7余2then输出N退出程序endifN=n+1loop1、将N的初始值赋为12、如果N<100并且N被3、5、7整除后余数为2、3、2，则输出N的值，转入第4步；3、将N的值加1,转到第2步；4、结束程序DimnasintegerN=1Doif(nmod3=2)and(nmod5=3)and(nmod7=2)thenPrintnExitdoEndifN=n+1LoopN=1DOifN除以3余2且N除以5余3且N除以7余2then输出N退出程序endifN=n+1loop自然语言流程图伪代码程序语言1.2算法描述与设计②描述算法三种描述算法的比较自然语言优点通俗易懂缺点冗长，繁锁，缺乏直观性简洁性，容易产生歧义流程图优点形象、直观、更容易理解缺点需要一定数学知识伪代码优点简洁、易懂，修改起来比较容易，易转为程序语言代码缺点没有流程图直观，出现错误不便排查第一章如何用计算机解决问题1、什么是算法？2、算法的特征：53、算法的描述方法？3小结练习：说出下面流程图的各框名称开始框输入框处理框判断框处理框处理框处理框输出框结束框如果两个数有最大公约数A，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是A的倍数。

所以当最后两个数刚好能整除时，较小的数就是最大公约数。第一章如何用计算机解决问题1、

算法是解决问题的（

）A．程序代码

B．方法与步骤

C．计算公式

D．最终结果2、利用可视化程序设计语言进行信息的编程加工的一般顺序是（

）

A、编写代码、设计算法、设计界面、调试运行

B、设计算法、设计界面、编写代码、调试运行

C、设计算法、编写代码、设计界面、调试运行

D、设计算法、编写代码、调试运行、设计界面3、下面关于算法的说法错误的是（

）A．算法必须有输出

B．算法就是程序

C．算法不一定有输入

D．算法必须在有限步执行后能结束4、以下不属于算法基本特征的是（

）A．可执行性

B．确定性

C．有穷性

D．无限性5、流程图中表示判断框的是（

）。A．矩形框B．菱形框

C．圆形框D．椭圆形框第一章如何用计算机解决问题6、下列哪一个不是用于程序设计的（）A.BASIC

B.C语言C.WORD

D.Pasical7、程序设计语言的发展阶段不包括（）A.机器语言B.自然语言C.汇编语言D.高级语言8、下面说法正确的是（）A.算法+数据结构=程序B.算法就是程序

C.数据结构就是程序

D.算法包括数据结构9、下列不属于描述算法方式的是（）A、自然语言

B、伪代码

C、流程图

D、机器语言10、流程图是描述（）的常用方法A、程序B、算法

C、数据结构

D、计算规则11、下列关于算法描述语言，错误的是（）A、用流程图描述算法形象、直观B、自然语言描述的算法很容易转化为程序设计语言C、用伪代码编写的算法简洁易懂、容易修改D、自然语言描述的算法通俗易懂，但缺乏直观性和简洁性填空题1、算法就是解决问题的___________和_________。2、算法描述可以有多种表达方法，一般用_______、_______和______