资源简介

(共38张PPT)
（1）把羊带到右岸；
（2）空船返回左岸，
把狼带到右岸；
（3）把羊带回左岸；
（4）把卷心菜带到右岸；
（5）空船返回左岸，
把羊带到右岸。
第三章 算法基础
一、算 法
1.算法的概念
算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。
1.算法的概念
通俗地说，算法就是计算机求解某一问题的方法，是能被执行的动作或指令的有穷集合。
2.人工解决问题 VS 计算机解决问题
例1：圆周率的计算
历史人物 研究方法/时间 圆周率位数（范围）
阿基米德（古希腊） 内外接多边形（96边形） 3.141851
祖冲之（中国） 割圆术（公元480年） 3.1415926~3.1415927
鲁道夫（德国） 1596年 1610年 20位小数值
35位小数值
梅钦（英国） 无穷级数（1706年） 突破100位
Jurij Vega 梅钦类公式（1789年） 140位（137位正确）
弗格森、伦奇 1948年 808位
2.人工解决问题 VS 计算机解决问题
例1：圆周率的计算
时间节点 花费时间 圆周率位数
1950年 70小时 2037位
1955年 13分钟 3089位
1973年 100万位
1989年 10.1亿位
2010年 5万亿位
2011年 一年（自组装计算机） 10万亿位
2.人工解决问题 VS 计算机解决问题
例2：韩信点兵
西汉大将韩信，善于带兵，神机妙算，能征善战。一次阅兵时，韩信要求士兵排成3路纵队，此时末尾多出2人，改排成5路纵队，末尾多出3人，再排成7路纵队，末尾余下2人。这时，领兵的部下报告说，这队士兵一共有2395人，韩信立刻摇头说：不对，实际实际只有（ ）人，部下迟疑地回去，又重新清点人数，果真是那么多人，部下们因此对韩信十分佩服。
人数范围x：2300~2400
从2300开始，逐个数去试试，如果这个数能同时被3、5、7整除后的余数分别为2、3、2，则这个数就是正确的人数。
例2：韩信点兵
例2：韩信点兵
①总人数x=2300；
②判断x是否在2300~2400之间，满足则执行下一步，否则结束；
③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；
④x在原来的基础上加1，回到第②步；
⑤输出x。
思考1：计算机解决问题的过程是怎样的？
例2：韩信点兵
①总人数x=2300；
②判断x是否在2300~2400之间，满足则执行下一步，否则结束；
③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；
④x在原来的基础上加1，回到第②步；
⑤输出x。
3.算法的特征
（1）有穷性；
（2）确定性：每个步骤必须有确切的定义，不能出现模棱两可的情况；
（3）数据输入：算法可以有零个或多个输入；
（4）数据输出：算法必须有一个或多个输出；
（5）可行性：任何步骤都可执行，能在有限时间内完成。
4.算法的描述
（1）用自然语言描述算法
易掌控
当算法较复杂时，用自然语言很难清晰表示
自然语言具有歧义性，容易导致算法执行的不确定性
4.算法的描述
（2）用流程图描述算法
使算法的流程描述得清晰、简洁
流程图的基本图形及其功能
起始框：表示算法的开始和结束
处理框：表示完成某种操作
判断框：表示根据一个条件成立与否，决定执行两种不同操作的其中一个
输入、输出框：表示数据的输入输出
流程线：用箭头表示程序执行的流向
朋友的意思
程序猿的理解
例2：韩信点兵
①总人数x=2300；
②判断x是否在2300~2400之间，满足则执行下一步，否则结束；
③判断x是否满足x÷3······2并且x÷5······3并且x÷7······2，满足则执行第⑤步，不满足则执行第④步；
④x在原来的基础上加1，回到第②步；
⑤输出x。
4.算法的描述
（3）用伪代码描述算法
伪代码是介于自然语言和计算机语言之间的文字和符号。是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。
它没有任何编程语言的语法，因此无法由计算机编译或解释。
4.算法的描述
（3）用伪代码描述算法
“韩信点兵”问题：
if(x>=2300 and x<=2400):
if (x%3==2 and x%5==3 and x%7==2):
{输出对应的x的值}
4.算法的描述
（3）用伪代码描述算法
不用图形符号，每条指令占一行
书写方便，格式紧凑
易于理解
便于向计算机程序设计语言过渡
5.常用算法
枚举法：也称“穷举法”。将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。
解析法：用解析的方法，找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式计算实现问题求解。一般使用公式进行计算的计算机程序都是用的解析法。
递归法：通过重复将问题分解为同类的子问题。
分治法：将一个规模较大的问题分解为若干个规模较小的子问题，通过解决子问题就可得到原问题的解。
《张邱建算经》中有一个“百鸡问题”：
“今有鸡翁一,值钱伍;鸡母一,值钱三;鸡雏三,值钱一。凡百钱买鸡百只,问鸡翁、母、雏各几何？”
张邱建：北魏时期数学家，“百鸡问题”是中古时期关于不定方程正整数解的典型问题，张邱建对此有精湛和独到的见解。著有《张邱建算经》3卷。
6.算法的优化
分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：
x+y+z=100
5x+3y+z/3=100
10000次
x+y+z==100 and 5*x+3*y+z/3==100
分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：
x+y+z=100
5x+3y+z/3=100
X的范围：0Y的范围：0660次
x+y+z==100 and 5*x+3*y+z/3==100
分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：
x+y+z=100
5x+3y+z/3=100
x+y=100-z
5x+3y=100-z/3
x=4*z/3－100
y=200－7*z/3
33次
for z in range(3,100,3):
x=4/3*z-100
y=200-7/3*z
if x>0 and y>0:
print(int(x),int(y),int(z))
分析：设可以买公鸡x只，母鸡y只，小鸡z只，根据题意可得出：
x+y+z=100
5x+3y+z/3=100
x+y=100-z
5x+3y=100-z/3
003次
for z in range(78,85,3):
x=4/3*z-100
y=200-7/3*z
if x>0 and y>0:
print(int(x),int(y),int(z))
75二、计算机程序与程序设计语言
1.计算机程序
计算机程序是指计算机可以识别运行的指令集合。
二、计算机程序与程序设计语言
2.算法与计算机程序的关系
灵魂
代码实现
算法与程序相互依附，算法要在计算机上执行，必须将算法的步骤用编程语言的语法描述出来，编译通过后，方可在计算机上执行。
二、计算机程序与程序设计语言
3.计算机程序设计语言
2023年顶级编程语言交互排行榜
Dim x , y , z as integer
For x=1 to 100 Step 1
For y=1 to 100 Step 1
Z=100-x-y
If 5*x+3*y+z/3=100 Then
Print x , y , z
End if
Next y
Next x
VB
for x in range(1,101):
for y in range(1,101):
z=100-x-y
if x+y+z==100 and 5*x+3*y+z/3==100:
print(x,y,z)
python
3.计算机程序设计语言
（1）机器语言
是由“0”和“1”这样的二进制代码指令组来表示。每一条机器指令包含两个主要部分：操作（指出计算机应做什么）和被操作的对象（指出处理的数据或它的地址），计算机能直接识别和执行。
3.计算机程序设计语言
（1）机器语言
3.计算机程序设计语言
（2）汇编语言
使用了一种类似英文缩略词且带有助记性符号的语言，来替代一个特定的指令的二进制串，每条指令都和一条机器指令相对应。需要一个专门的语言翻译器，负责将程序中的每条语句都翻译成用二进制数表示的机器语言。
3.计算机程序设计语言
（2）汇编语言
3.计算机程序设计语言
（3）高级语言
接近于数学语言或人的自然语言，并且不再过度地倚赖某种特定的机器或环境，必须经过翻译器将其翻译成机器语言。
3.计算机程序设计语言
（2）高级语言
3.计算机程序设计语言
语言类型 是否翻译（编译） 优势 不足
机器语言 否 能被计算机接受和执行，运算效率最高。 程序难以理解，程序设计任务繁重，移植性差。
汇编语言 是 针对计算机特定硬件而编制的汇编语言程序，比机器语言易于理解，效率仍十分高。 不能被计算机直接运行，移植性不好。
高级语言 是 接近于数学语言或人的自然语言，易于理解，移植性好。 不能被计算机直接运行。
“计算机天生就是用来解决以前没有过的问题的。”
—— 比尔盖茨（bill gates）

展开更多......

收起↑