第二章 程序的灵魂 —算法
算法 +数据结构 =程序
算法 (Algorithm)
main()
{ int a,b,c;
scanf(“%d,%d”,&a,&b);
c=a;
a=b;
b=c;
printf(“a=%d,b=%d”,a,b);
…
}
示例程序一,
示例程序二,
int max(int x,int y)
{ int z;
if (x>y) z=x;
else z=y;
return z;
}
算法的定义
算法 =操作 +控制结构
算法是指程序的中心思想 ;
算法不是指数值计算 ;
算法是程序的灵魂 ;
2.2 简单算法举例
S1,使 p=1
S2,使 I=2
S3,使 p*I,乘积仍放在变量 p中,p*I -> p
S4,使 I的值加 1,即 I+1 -> I
S5,如果 I不大于 10,返回重新执行 S3及其后
的步骤 S4和 S5;否则计算结束
S6,输出乘积的值 p
求 1*2*3*4*5*… *10
例 2.4
求 1-1/2+1/3-1/4+… +1/99-1/100
S1,sign=1
S2,sum=1
S3,deno=2
S4,sign=(-1)*sign
S5,term=sign*(1/deno)
S6,sum=sum+term
S7,deno=deno+1
S8,if deno<=100 返回 S4;否则输出 sum并结束
? 有穷性,解题算法是一有穷动作序列
? 确定性,每个步骤应当是确定的,没有歧义
? 有零个或多个输入
? 有一个或多个输出
? 有效性
2.3 算法的特性
2.4 算法的表达方式
1,自然语言表示算法 ;
2,流程图表示 ;
3,伪代码方式 ;
用流程图表示算法
1、流程图 (p20)
用一些图框表示各种类型的操作，用线表示这
些操作的执行顺序。（图框举例如下图）
处理框 判断框 输入输出框
基本程序结构
※ 顺序结构（顺序执行）
※ 选择结构（比较判断）
※ 循环结构或称重复结构（反复执行）
传统的流程图的弊端?
处理 2
处理 1
处理 1 处理 2
处理
判断
Y N
判断
顺序结构 选择结构 循环结构
三种控制结构流程图
? 用 N-S图描述算法
美国 I.Nassi and B.Shneiderman提出的
一种无流线的流程图
A
B
C
P
T F
A B
P
A
用伪代码表示算法
用自然语言和计算机语言之间的文字和符号来描述算法。
伪代码,
begin
1 => t
2=> i
while I<=10
{ t*I=>t
I+1=>I
}
print t
end
C语言,
void main()
{ int I=2,t=1;
while (I<=10)
{ t=t*I;
I=I+1;
}
printf(“%d\n”,t);
}
伪代码,
begin
1 => sum
2=> deno
1=> sign
while deno<=10
{ (-1)*sign=> sign
sign*1/deno=>term
sum+term=>sum
deno+1=>deno
}
print sum
end
C语言,
void main()
{ int sign=1;
float deno=2.0,sum=1.0,term;
while (deno<=100)
{ sign=-sign;
term=sign/deno;
sum=sum+deno;
deno=deno+1;
}
printf(“%f\n”,f);
}
用伪代码表示算法
2.5 结构化程序设计方法
1,自顶向下 ;
2,逐步细化 ;
3,模块化设计 ;
4,结构化编码 ;
本章结束
THE END