程序的灵魂算法

第2章程序的灵魂－－算法算法的概念简单算法举例算法的特征怎样表示一个算法结构化程序设计方法数据结构＋算法＝

程序程序＝算法＋数据结构＋程序设计方法＋语言工具和环境目标理解算法的作用以及特性用自然语言表示算法用流程图表示算法用c语言表示算法什么是程序

程序一词来自生活，通常指完成某些事务的一种既定方式和过程在日常生活中，可以将程序看成对一系列动作的执行过程的描述2.1算法的概念一个程序应包括：对数据的描述：在程序中要指定数据的类型和数据的组织形式，即数据结构（datastructure）。对操作的描述：即操作步骤，也就是算法（algorithm）。返回2.1算法的概念一、算法的概念广义地讲：算法是为完成一项任务所应当遵照的一步一步的规则的、精确的、无歧义的描述，它的总步数是有限的。狭义地讲：算法是解决一个问题采取的方法和步骤的描述二、算法的描述1.日常自然语言2.伪代码（自然语言与程序设计语言相结合）3.流程图(传统流程图、N—S流程图）4.程序设计语言三、简单的算法举例[例2.1]交换两个变量的值算法：⑴a=>t⑵b=>a⑶t=>bNikiklausWirth提出的公式：数据结构+算法=程序再进一步：程序=算法+数据结构+程序设计方法+语言工具和环境

2.1算法的概念做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。计算机算法：计算机能够执行的算法。计算机算法可分为两大类：数值运算算法：求解数值；非数值运算算法：事务管理领域。算法计算长方形的面积问题：1.接收用户输入的长方形长度和宽度两个值；2.判断长度和宽度的值是否大于零；3.如果大于零，将长度和宽度两个值相乘得到面积，否则显示输入错误；4.显示面积。算法：解决问题的具体方法和步骤八皇后问题问题定义：八皇后问题是一个著名而古老的问题。该问题要求在8×8的国际象

棋棋盘上放置8个皇后，使得它们不能相互攻击，即任意两个皇后不能处于同

一行、同一列或者同一斜线上。问有多少种放置的方案？QQQQQQQQQijQijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1Qijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3QQijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5QQijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2QQijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2(5)j=5i=4，8

i=4Q(6)j=6i无法选取

回退一步Qijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2Q(6)j=6i无法选取

回退一步(5)j=5i=4，8

i=8Qijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5Q(4)j=4i=2，7，8

i=2(5)j=5i=4，8

i=4Q(6)j=6i无法选取

回退一步(5)j=5i=4，8

i=8(6)j=6i无法选取

回退一步(4)j=4i=2，7，8

i=7依次类推Qijj:行号i:列号每行一个皇后,即每个j值对应一个i值。

试探法(1)j=1i=1(2)j=2i=3，4……，8

i=3Q(3)j=3i=5，6，7，8

i=5QQ(4)j=4i=2，7，8

i=7依次类推如何表示一具体方案如何表示一具体方案？intqueen[8];queen[j]j=0,1,2……,7;表示第j+1行皇后放在第queen[j]+1列上,即（queen[i]+1,j+1)放置一个皇后。QQQQQQQQ皇后放置问题QQQQQQQQ如何表示（queen[i]+1,j+1)放置一个皇后以后，与该皇后同列、两个对角线不能再放置皇后？intb[8],c[15],d[15];b[j]j=0,1,2……,7;表示第j+1列上已有皇后如果第i+1行、第j+1列上放置一个皇后，则b[j]=1第j+1列上已有皇后c[i+j]主对角线上已有皇后d[i-j+7]从对角线已有皇后算法描述初始化棋盘为第1个皇后选择合适位置第2步定义成一个递归函数try voidtry(inti);该函数作用是放置第i+1个（i=0,1……，7）皇后(第i+1行皇后放置）：for(j=0;j<8;j++) /*每个皇后都有8种可能位置*/

{2-1

如果不存在位置冲突，则

{2-2

位置（i+1,j+1）上放置皇后

2-3

如果第8个皇后还没有放置好，则 继续放置下一个皇后/*try(i+1)调用*/

否则 输出当前解

}

2-4

释放位置（i+1,j+1）}#include<stdio.h>intqueen[8],b[8],c[15],d[15];int

queennum=0;/*当前解的序号*//*找到一个解后，输出当前解*/voidprint(){intk;

queennum++;

printf("%d:",queennum);for(k=0;k<8;k++)

printf("\t%d",queen[k]);

printf("\n");}程序源代码voidtry(inti){ intj; /*每个皇后都有8种可能位置*/ for(j=0;j<8;j++) {if((b[j]==0)&&(c[i+j]==0)&&(d[i-j+7]==0))

/*判断位置是否冲突*/ {queen[i]=j;/*摆放皇后*/

b[j]=1;/*宣布占领第j+1行*/

c[i+j]=1;/*占领两个对角线*/d[i-j+7]=1;if(i<7) try(i+1);/*8个皇后没有摆完，递归摆放下一皇后*/else print();/*完成任务，打印结果*/

b[j]=0;/*回溯*/

c[i+j]=0;d[i-j+7]=0;} }}intmain(){ intk; /*数据初始化*/ for(k=0;k<15;k++) { if(k<8)b[k]=0;

c[k]=0;

d[k]=0; } try(0); /*从第1个皇后开始放置*/ return0;}主函数一、算法(最短路径问题)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2求从A到E的最短路径一、算法(最短路径问题)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0一、算法(最短路径问题)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0一、算法(最短路径问题)：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1

（C1，D1）D1

（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E一、算法(资源分配问题)4万元资金，如何分配给A、B、C三个项目，使总效益最大4万元2万元1万元0万元4万元2万元1万元0万元4万元2万元1万元0万元4万元

x1 A项目 x2 B项目 x3 C项目 x43万元3万元3万元0f2.2简单算法举例[例2.2]求1×2×3×4×5。最原始方法：步骤1：先求1×2，得到结果2。步骤2：将步骤1得到的乘积2乘以3，得到结果6。步骤3：将6再乘以4，得24。步骤4：将24再乘以5，得120。这样的算法虽然正确，但太繁。返回改进的算法：S1:使t=1S2:使i=2S3:使t×i,乘积仍然放在在变量t中，可表示为t×i→tS4:使i的值+1，即i+1→iS5:如果i≤5,返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。如果计算100！只需将S5:若i≤5改成i≤100即可。

如果该求1×3×5×7×9×11，算法也只需做很少的改动：S1:1→tS2:3→iS3:t×i→tS4:i+2→tS5:若i≤11,返回S3，否则，结束。该算法不仅正确，而且是计算机较好的算法，因为计算机是高速运算的自动机器，实现循环轻而易举。[例2.3]有50个学生，要求将他们之中成绩在80分以上者打印出来。

如果，n表示学生学号，ni表示第i个学生学号；g表示学生成绩，gi表示第i个学生成绩，则算法可表示如下：S1:1→iS2:如果gi≥80，则打印ni和gi，否则不打印S3:i+1→iS4:若i≤50,返回S2，否则，结束。[例2.4]判定2000—2500年中的每一年是否闰年，将结果输出。闰年的条件：

能被4整除，但不能被100整除的年份；

能被100整除，又能被400整除的年份；设y为被检测的年份，则算法可表示如下：S1:2000→yS2:若y不能被4整除，则输出y“不是闰年”，然后转到S6S3:若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6S4:若y能被100整除，又能被400整除，输出y“是闰年”否则输出y“不是闰年”，然后转到S6S5:输出y“不是闰年”。S6:y+1→yS7:当y≤2500时,返回S2继续执行，否则，结束。[例2.5]求算法可表示如下：S1:sigh=1S2:sum=1S3:deno=2S4:sigh=(-1)×sighS5:term=sigh×(1/deno)S6:term=sum+termS7:deno=deno+1S8:若deno≤100，返回S4；否则，结束。[例2.6]对一个大于或等于3的正整数，判断它是不是一个素数。算法可表示如下：S1:输入n的值S2:i=2S3:n被i除，得余数rS4:如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5:i+1→iS6:如果i≤n-1，返回S3；否则打印n“是素数”；然后算法结束。S1:输入n的值S2:i=2S3:n被i除，得余数rS4:如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5:i+1→iS6:如果i≤，返回S3；否则打印n“是素数”;然后算法结束。改进算法可表示如下：2.3

算法的特性有穷性：一个算法应包含有限的操作步骤而不能是无限的。确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的。有零个或多个输入。有一个或多个输出。有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。返回2.4

怎样表示一个算法一、用自然语言表示算法二、传统流程图处理框起止框I/O框判断框流程线连接点1、传统流程图中的基本符号返回2、三种基本结构的表示（1）顺序结构条件语句1语句2YN语句1语句2（2）选择结构条件语句条件语句（3）循环结构a)当型循环b)直到循环YNYN三种基本结构的特点：（1）只有一个入口（2）只有一个出口（3）不存在死语句（4）不存在死循环例：画出从10个数中选出最大的数的流程图由以上三种基本结构组成的算法结构,可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和跳转。N<10Max=AN=1A>=MaxMax=A输入A开始再输入给AN=N+1打印Max结束YNNY四、N—S流程图将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框三种基本结构的N—S图表示：语句A语句B语句A语句B条件YN1、顺序结构2、选择结构语句组（3）循环结构a)当型循环b)直到循环当条件成立语句组直到当条件成立例：画出从10个数中选出最大的数的N—S流程图输入A当N<=10Max=AN=N+1打印Max输入AN—S流程图传统流程图N<10Max=AN=1A>=MaxMax=A输入A开始再输入给AN=N+1打印Max结束YNNYA>=MaxYNN-S图比文字描述直观、形象、易于理解；比流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个接纳结构按顺序组成的。N-S图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分方便。五、用计算机语言表示算法#include

<stdio.h>

main(){intmax,n,a;n=1;

scanf(“%d”,&a);max=a;

while(n<=10){scanf(“%d”,&a);if(max<a)max=a;n++;}

printf(“Max=%d\n”,max);}[例2.7]将例2.1求5!的算用流程图表示。[例2.8]将例2.2的算用流程图表示。

[例2.9]将例2.3判定闰年的算用流程图表示。

用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。 流程图对流程线的使用没有限制，使得流程图变得毫无规律，如同一碗面条(abowlofspaghetti)。[练习]用N-S图表示有50个学生，要求将他们之中成绩在80分以上者打印出来。2.4.5

用伪代码表示算法 伪代码使用介于自然语言和计算机语言之间的文字和符号来描述算法。[例2.10]打印2000----2500年中的每一年是否是闰年。BEGIN（算法开始）

2000=>ywhiley<=2500{ify被4整除

ify不被100整除printy;”是闰年”

elseify被400整除printy;”是闰年”

elseprinty;”非闰年”

endif

endifelseprinty;”非闰年”

endif

y+1=>y}END（算法结束）伪代码书写格式比较自由，可以随手写下去，容易表达出设计者的思想。用伪代码写的算法容易修改，容易写出结构化的算法。但是，用伪代码写算法不如流程图直观，可能出现逻辑上的错误。2.4.6

用计算机语言表示算法我们的任务是用计算机解题，就是用计算机实现算法；用计算机语言表示算法必须严格遵循所用语言的语法规则。[例2.11]求1×2×3×4×5用C语言表示。main(){

int

i,t; t=1; i=2;

wh