算法与程序设计.

Presentation on theme: "算法与程序设计."— Presentation transcript:

1 算法与程序设计

2 编制计算机程序解决问题的过程：

3 【练习】 一位同学想编程解决“韩信点兵”的问题，他制定的如下工作过程中，最恰当的是（ ） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案

4 算 法 概念: 算法就是解决问题的方法和步骤 特征： 描述：自然语言、流程图、伪代码 （1）输入（有零个或多个输入）
概念: 算法就是解决问题的方法和步骤 特征： 描述：自然语言、流程图、伪代码 （1）输入（有零个或多个输入） （2）确定性（ 每一步有确切含义，不能有歧义） （3）有穷性（步骤是有限的） （4）输出（有一个或多个输出） （5）能行性 （运算和操作能够精确进行）

5 算法描述：求两个正整数的最大公约数。 自然语言 伪代码 流程图

6 A、算法不可以用自然语言描述 B、算法只能用框图来描述 C、一个算法必须保证它的执行步骤是有限的
【练习】 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、算法的框图表示法有0个或多个输入，但只能有一个输出

7 算 法 算法——解析法 种类：解析法、穷举法、查找、排序、递归 小结：用解析法解决问题的关键就是找到求解问题的解析表达式。
解析法是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。 种类：解析法、穷举法、查找、排序、递归 举例：【出租车计费】 某城市的出租车计费标准为起步价10元（3公里内），此外，在3公里到10公里之间每公里2.1元，超过10公里部分每公里3元，输入行车距离x，输出车费y。 编写数学表达式：设车程数为X公里，车费为Y元，则 Y= (x<=3) 10+2.1*(x-3) (3<x<=10) 10+2.1*7+3*(x-10) (x>10) VB代码： Privat sub command1_click() Dim x,y as single X=val(inputbox("请输入行车距离")) If x<=3 then Y=10 Elseif x>3 and x<=10 then Y=10+2.1*(x-3) Else Y=10+2.1*7+3*(x-10) End if Print y End sub 小结：用解析法解决问题的关键就是找到求解问题的解析表达式。

8 算法——穷举法 穷举法穷举法也叫枚举法或列举法。 在研究对象是由有限个元素构成的集合时，把所有对象一一列举出来，再对其一一进行研究。带入实际，一个个检验是否符合，穷举完所有对象问题将最终得以解决。这种方法一般在计算机中运用，因为计算机计算速度快，可以很快验证答案是否正确。 举例：【百钱买百鸡】 用100元钱买100只鸡，公鸡每只5元，母鸡每只3元，小鸡3只1元，要求每种都买，问能买公鸡、母鸡、小鸡各买几只？ VB代码： Privat sub command1_click() Dim x,y ,z as integer For x=1 to 20 step 1 For y=1 to 33 step 1 z=100-x-y If 5*x+3*y+z/3=100 then Print x,y,z Next y Next x End sub 小结：穷举法的基本思路是把问题涉及的可能情况一一罗列出来，并且根据题目的条件和实际背景逐个作出判断，从中挑选出符合条件的解答。

9 算法——查找法 查找法就是在一组对象中搜索某一目标，确定对象中有没有这一目标元素，若有，则标出它的位置；若没有，则给出没有的信息。
查找的方法一般有两种：顺序查找与对半查找。 顺序查找：就是从头到尾一个一个地往下寻找。 对半查找，也叫二分查找，折半查找，是对有序的数才能用，一次减少一半的方法。 【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

10 【练习】 1、穷举法适用的范围是（） A、一切问题 B、解的个数极多的问题 C、解的个数有限且可一一列举 D、不适合设计算法 2、使用枚举法解决问题，在列举问题可能解的过程中，＿＿＿＿。 A．不能遗漏，但可以重复 B．不能遗漏，也不应重复 C．可以遗漏，但不应重复 D．可以遗漏，也可以重复 3、采用盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些合乎要求的结果，这种方法叫做＿＿＿＿。 A．递推法 B．枚举法 C．选择法 D．解析法 4.以下算法中，需通过多重循环一一列举出解决问题所有可能解，并在逐一列举的过程中，检验每个可能的解是否是问题的真正解的是（ ）。而需要从实际问题中归纳出反映事物内在联系的数学公式，就此设计出合适的算法的是（ ）。 A.解析法穷举法 B.递归法解析法 C.穷举法解析法 D.穷举法递归法

11 算法——排序法 排序：就是把一组数据整理为顺序的算法。排序可以从大到小，也可以从小到大，把从小到大称为顺序，而从大到小称为逆序。
排序的算法分为三种：选择排序、插入排序、冒泡排序。 选择排序：先输入要排序的数据，每次从中挑出一个最小数，排好顺序，直到所有数都排完为止。 插入排序：每输入一个数就排好顺序，这样当数输入完毕，顺序已经排好了。 冒泡排序：先输入要排序的数据，从最后一个数开始，每相邻两个比较，小数放前面，直到所有数都排好顺序。 视频

12 算法——递归法 1、递归：递归算法是一种直接或者间接地调用自身的算法。递归算法是数值层层调用实现的，函数先由上向下调用，当达到最底层后，再将函数值层层向上返回。(递下去，收回来，简称：递归) 2、必须有个结束条件（有个该收回来的条件） 3、可读性强 4、计算机资源耗费大，所以效率比较底（常驻内存的数据比较多） 5、用递归能够解决的问题：    N！、 求 ……N 、“猴子吃桃”问题、斐波那契数列、哥德巴赫猜想、汉诺塔问题 觖决方法

13 【练习】 选择算法，解决问题： 我们在用计算机解决问题时，常采用的算法有解析法、穷举法、递归法、冒泡排序法、选择排序法等，分析下列问题应采用哪种算法解决？ 1、在学校举行的运动会中，要对运动员成绩进行公布，现在要求编写一个程序自动完成成绩编排，请问最好采取哪种算法解决？ 答案：_____________________________ 2、已知：f(1)=1,f(2)=1,当n>=3时，F(n)=f(n-1)+f(n-2)，编程求f(100)的值。请问最好采取哪种算法解决？ 3、一个数除以5余1，除以6余5，除以7余4，除以11余10，求符合这些条件的最小的数是多少？请问最好采取哪种算法解决？

14 程序 常用函数 变量、常量 运算符 基本数据类型 程序设计语言 基本结构 Abs() Sqr() Int() 转换函数 数学函数 日期函数
字符串函数 交互函数 运算符 变量、常量 程序 基本数据类型 命名规则 1.以英文字母开头 2.中间可以包括有字母、数字、下划线 3.不能使用关键字 逻辑运算符 算术运算符 字符串运算符 关系运算符 基本结构 程序设计语言 数据类型 关键字 整型 Integer 长整型 Long 单精度型 Single ”” 双精度型 Double 字符串型 String 布尔型 Boolean 日期型 Date # # and、or not +、－、*、/、\、mod、^ +、& 顺序结构 选择结构 循环结构 机器语言 汇编语言 高级语言 <、>、<>、>=、<=、＝

15 翻译程序有两种类型：编译程序（整段翻译）和解释程序（一句一句翻译）
BASIC、VB、Pascal、C、C++、Java 程序设计语言 机 器 语 言 汇编 语 言 高级语 言 翻译程序有两种类型：编译程序（整段翻译）和解释程序（一句一句翻译）

16 【练习】 1.Visual Basic 是一种高级程序设计语言，它是一种面向( )的语言。 (P22) A、事件 B、过程 C、对象 D、属性 . 2.程序设计语言可以分为三大类，它们是机器语言、汇编语言和( )。 A、低级语言 B、自然语言 C、伪代码 D、高级语言 3.高级语言的翻译程序只有编译程序一种类型。( ) 4.下列哪一个不是用于程序设计的软件（） A、BASIC B、C语言 C、word D、Pascal

17 程 序 基本要素：常量、变量、运算符、函数、表达式、语句

18 基本数据类型 数据类型 类型说明符 示 例 整型数 Integer 245、-99都是整形数 长整型数 Long 32768是一个长整形数
示 例 整型数 Integer 245、-99都是整形数 长整型数 Long 32768是一个长整形数 单精度实型数 Single E+9表示 ×109 双精度实型数 Double D+12表示 ×1012 日期型 Date(Time) # # #06/30/ :25:18 AM# 字符型 String “yaiyuan”、”中国”、“123654” 逻辑型（布尔型） Boolean 取值只有True或False两种 备注：整型 Integer ～32767 长整型 Long ～ 单精度型 Single 负数： E38～ E-45 正数： E-45～ E38 双精度型 Double 负数： E308～   正数： E-324～ E308 注意：判断字符型数据的根本标志是看有没有” ”括起来，判断日期型数据的根本标志是看有没有# #括起来。

19 【练习】 1.为了便于数据的表示与处理，VB提供哪几种基本数据类型（多选） A、数值型 B、日期型 C、字符串型 D、布尔型
A、Boolean B、Date C、String D、Integer 3.不同的数据类型能表示的数值范围不同，超出了允许的数值范围，就会产生错误。（）

20 程序基本元素——常量 在程序执行过程中，其值不能改变的量称为常量。 常量可以直接用一个数来表示，称为常数（或称为直接常量），也可以用一个符号
来表示，称为符号常量。 常量的定义格式如下： Const <常量名> [As 数据类型]=<数值> 如： Const PI As Single =3.1416 表示定义 PI为符号常量，代表单精度型数值3.1416。

21 程序基本元素——变量 在程序执行过程中，其值可以改变的量称为变量。变量就是命名的内存单元位置。 1）变量的命名规则 2）变量定义语句
（ 1）变量名首字符必须是字母或汉字； （ 2）变量名只能由字母、数字、汉字和下划线组成； （ 3）变量名不能使用VB中的关键字（保留字）； （ 4）变量名长度不超过255； （ 5）不区分大小写 2）变量定义语句 Dim <变量名> As <类型> [, <变量名> As <类型>]… 如：dim x as integer,y as integer

22 程序基本元素——变量 数组是有限个类型相同的变量用同一个名字命名，然后用编号区分它们的变量 的集合。 在VB中定义数组的格式为：
Dim 数组名（下标） as 数据类型 下面举例说明定长数组的定义： ①Dim a(1 to 3) As Integer ②Dim b(7) As String ③Dim c(2,3) As Integer 其中，例①定义了一个具有三个元素的整型数组，其下标从1到3。 例②缺省了下界，它定义了一个具有八个元素的整型数组，其下标从0到7。 例③定义了一个二维数组，可存放12个元素。

23 【练习】 1.语句dim d(6to15) as integer执行后，数组d有几个元素？（） A、6 B、15 C、10 D、9
2. 数组是一组不同类型的变量的集合，集合中的每个元素都是独立的变量，它们能够通 过下标被引用。（） 3. VB中数组a(3,5)包含的元素个数为15个。 ( )

24 【练习】 1.在Visual Basic中变量命名必须遵守的规则是 （多选） A、不能使用VB的关键字作为变量的名字
2.在VB环境下，如果希望使用变量X来存放数据123.45，应该将该变量X声明为下列哪种类 型（）。 A、Integer B、Single C、String D、Boolean 3.在VB环境下使用变量前，一般应先声明变量及其类型，变量声明的关键字是 A、Const B、Print C、Dim D、Sub 4.在VB环境中，下列变量名合法的是（ ） A、shu_ B、print C、a3 D、2nl 5.按变量名的命名规则，下面字符中不能用于构成变量名的是（ ） A.字母 B.数字 C.下划线 D.空格 6.在程序中用到某一整型变量的数据范围为-32768~40000，则该变量类型应声明为（ ） A.Integer B. Byte C．Long D. Double 7.在程序执行的过程中，常量的值始终保持不变，变量的值随时改变。（） 8.下列选项中不是字符串常量的是（） A、“abv B、“你好” C、“2006” D、1235

25 程序基本元素——运算符、表达式 表达式是由变量、常量、运算符、函数、和圆括号等按一定的规则组合而成的。 1.算术运算符
 2、字符串运算符：+和&，它们的作用是将两个字符串连接起来。 3、关系运算符：=、<>（不等于）、>、<、>=、<= 4、逻辑运算符：not（非） and（与） or（或） 5、运算符的执行顺序：算术运算符>字符串连接运算符>关系运算符>逻辑运算符。 逻辑运算符的执行顺序：not> and> or 运算符 含义 ^ 指数 / 除 Mod 求余 * 乘法 \ 整除 + 加 - 减

26 【练习】 1. 下列运算符中属于关系运算符的是（） A、Not B、<> C、/ D、<= 2.将数学式子b2-4ac写成VB表达式，下列书写正确的是（）。 A、b*b-4ac B、b2-4*a*c C、b*b-4*a*c D、b*b-4a*c 3..在VisualBasic中，表达式2+15\2*4的值是（） A、32 B、30 C、3 D、4 4..VB环境下，根据表达式的运算符来确定表达式的类型的。下列属于VB表达式的有（） A、算术表达式 B、字符表达式 C、关系表达式 D、逻辑表达式 5.将数学表达式x>y>z表示为VB表达式，下列正确的是（） A、x>y and >z B、x>y>z C、x>y and y>z D、x>y and <Z<label> 6. 在VB中运算优先级别从低到高的顺序为：算术运算、关系运算、逻辑运算。（） 7.逻辑表达式(23>3) And (23 Mod 5=3)的运算结果为True。 8.表达式25 MOD (2 ^ 3 - 3) 的值是1。

27 程序基本元素——函数 转换函数 算术函数 字符函数 日期与时间函数 Date()函数返回系统的当前日期。 Time()函数返回系统的当前时间

28 【练习】 1.下列函数中属于数学函数的是（多选） A、Right() B、Cos() C、Abs() D、Sqr() 2.在VB环境中，函数Sqr(9)返回的值是( )。 A、 B、 C、 D、16 3.VB环境中，函数Int(5.6)返回的值是（ ）。 A、 B、 C、 D、11 4.如果x= -121，则运行语句x=Abs (x) 后，x的值是（ ）。 A、 B、 C、 D、121 5.如下VB表达式的运算结果是（）。Abs(-5)*4\3 A、 B、 C、 D、出错

29 程序基本结构 VB中用于实现顺序结构程序设计的语句有： 1）顺序结构 赋值语句：变量=表达式
输入数据的函数：inputbox(提示信息，标题，默认值，位置) 其中，提示信息不能省略，该函数返回值是字符串类型。 输出数据的方法：print 输出内容 行语句： If <条件> Then <语句1> Else <语句2> 块语句：If <条件> Then <语句1> Else <语句2> End If If 语句 2）选择结构 case语句 3）循环结构

30 For 循环变量=初值 To 终值 [Step 步长] 语句组 Next 循环变量 3）循环结构
If 语句 2）选择结构 Select Case <条件表达式> Case <值1> <语句1> Case <值2> <语句2> ……　　　　　　　　　　　　　　　　 Case Else <语句n> End Select case语句 For…Next 语句 For 循环变量=初值 To 终值 [Step 步长] 语句组 Next 循环变量 3）循环结构 (1) Do While <条件表达式> 语句 Loop （2） Do Until <条件> 语句 Loop Do…Loop 语句 【练习】见考题

31 【练习】 1、编程求值1+2+3+……+10000的和，该题设计最合适使用的控制结构为（） A、顺序结构 B、分支结构 C、循环结构 D、选择结构 2.针对语句 If i=1 then j=1，下列说法正确的是 （ ） A 、i=1和j=1均为赋值语句 B 、i=1为赋值语句，j=1为关系表达式 C 、i=1为关系表达式，j=1为赋值语句 D 、均为关系表达式 3.VB中，执行下列语句块将输出结果( )。a=12 b=13 print a;"+";b;"=";a+b A、a+b= B、a+13= C、 = D、13+b=25 4.从键盘输入圆的半径R，输出圆的周长L和面积S。 Dim R As Single, L As Single , S As Single _____=InputBox("输入半径R ")       L=2*3.14*R S=3.14*R*R Print "圆的周长L= ";L Print "圆的面积S= ";S

32 调试 调试运行 目的 编辑错误（语法错误） 编译错误 运行错误 逻辑错误 发现错误和修改错误 错误的类型

33 【练习】 1.在用计算机解决问题的过程中，“调试程序”的目的是查找和改正程序中存在的错误。（ ）