(共11张PPT)
第二节
《算法及其描述》
??
编制计算机程序解决问题的全过程
分析问题
设计算法
编写程序
调试运行
检测结果
编程重要的是逻辑思路,确定解决问题的详细方法和步骤,即设计算法。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则,是能够被机械执行的动作或者指令的有穷集合。
例如:若要求解方程6x+5y+4z=50的正整数解的个数t,则解决问题的步骤可以描述为:
(1)t=0;(2)x=1;(3)y=1;(4)z=1;
(5)如果满足式子,则解的个数t加1,并输出这个解;
(6)z=z+1,如果z<=12则转向步骤5,否则转向步骤7;
(7)y=y+1,如果y<=10则转向步骤4,否则转向步骤8;
(8)x=x+1,如果x<=8则转向步骤3,否则转向步骤9结束程序;
算法的特征
数据输入:一个算法有零个或多个输入;
确定性:算法执行的每一步必须有确切的定义,不可含混不清;
有穷性:一个算法在执行有穷步之后必须结束;
数据输出:一个算法有一个或多个输出,即最后的结果
可行性:算法中执行的任何计算步骤都可以被分解成基本的
可执行的操作步骤,即每个基本步骤都可以在有限时间内完成。
算法的描述
(1)用自然语言描述算法:比较容易理解,越详细越好,但如果算法中含有比较多的分支或者循环操作等时,使用自然语言比较难将其清晰表示出来;同时由于自然语言的歧义性会导致算法执行的不确定性。
(2)用流程图描述算法:用程序框图来描述,使流程清晰、简洁。
用辗转相除法求两数的最大公约数
(1)用m除以n,令所得的余数为r;
(2)若r=0,则输出n,算法结束,否则继续(3);
(3)令m=n,n=r,并返回步骤(1)。
开始
输入m和n
r=m
MOD
n
r=0
输出n
结束
m=n
n=r
否
是
算法的描述
(3)用伪代码描述算法:用介于自然语言和计算机语言之间的文字和符号来描述算法,易于理解,便于向计算机程序设计语言过渡。
t=0;
for
x
in
range(1,9):
for
y
in
range(1,11):
for
z
in
range(1,13):
if(x
6+y
5+z
4==50)
t=t+1;
输出解的个数以及三个整数解x,y,z;
程序的三种基本结构
前面的算法描述中我们用到了顺序结构、选择结构、循环结构这三种基本控制结构。任何复杂的算法都可以使用这三种基本控制结构组合来表示。
语句1
语句2
顺序结构表示程序中各个步骤按照出现的先后顺序依次执行。
程序的三种基本结构
选择结构表示程序的处理步骤出现了分支,需要按照某一个特定的条件选择其中一个分支执行,有单选择,双选择,多选择。
条件
语句1
语句2
Y
N
程序的三种基本结构
循环结构表示反复执行某些操作直到判断条件为假或者为真时才结束循环。
条件
条件
语句组
Y
N
Y
N
语句组
项目规划与探究
项目主题
项目实施与成果
运行《汉诺塔2.exe》文件体验游戏
“递归分解”菜单,思考并完成“游戏破解”中最优策略功能的算法设计及其描述。