第二章程序的灵魂——算法一、算法的概念二、简单算法举例三、算法的特征四、算法的表示五、结构化程序设计方法
（3）循环结构：如图三（当循环）、图四（直到循环）。在图三中，当条件P成立时反复执行A操作，直到条件P不成立为止；在图四中，一开始
就重复执行A操作，直到条件P成立时为止。A当P成立时图三：当循环结构直到P成立时A图四、直到循环流程
图适宜于表示一个算法，但在设计算法过程中使用不是很理想（尤其是当算法比较复杂，需要反复修改时）。为了设计算法时方便，常用一种称为伪
代码（pseudocode）的工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上
而下地写下来，每一行（或几行）表示一个基本操作。它不用图形符号，因此书写方便，格式紧凑，也比较好懂，便于向计算机语言过渡。
用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。3、用伪代码表示算法
C程序设计数学系计算机系列课程课件之一本章要点2.1算法的概念2.2简单算法举例2.3算法的特征
2.4算法的表示2.5结构化程序设计方法为解决一个问题而采取的方法和步骤，称为“算法”。对同一个
问题，可以有不同的解题方法和步骤。一般说，希望采用方法简单，运算步骤少的方法。因此，为了有效地进行解题，不仅需要保证算法正确，还要
考虑算法的质量，选择合适的算法。对数据的描述数据结构(数据的类型和数据的组织形式)(2)对操作的描述
算法(解决一个问题的方法和步骤)程序=算法+数据结构+程序设计方法+语言工具和环境计算机算法可分为两大类：
数值运算算法和非数值运算算法。例EX2_1求1×2×3×4×5可以用最原始的方法进行：步骤1：先求1×
2，得到结果2；步骤2：将步骤1得到的乘积2再乘以3，得到结果6；步骤3：将6再乘以4，得24；步骤
4：将24再乘以5，得120，这就是最后的结果。虽然算法是正确的，但太繁琐。应当找到一种通用的表示方法。假设
有两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数
，i为乘数。用循环算法来求结果，可以将算法改写如下：S1：使p=1； S2：使i=2；S3：使p×i，乘积
仍放在变量p中，可以表示为p×i=>p；S4：使i的值加1，即i+1=>i；S5：如果i不大于5
，返回重新执行步骤3及步骤4和步骤5；否则，算法结束。最后得到p的值就是5!的值。开始1=>p2=>ii<
=5FTp×i=>pi+1=>i输出p结束循环i<=5
p×i=>pi+1=>i输出p2=>i1=>p流程图表示N-S图表示#includema
in(){ intp,i; p=1; i=2; while(i<=5) { p=p
i; i++; } printf(“%d”,p);}计算机语言表示显然这个算法比较
比较简练，如将题目改为求1×3×5×7×9×11，则算法只需作很少改动：S1：1=>p； S2：3=>i；S
3：p×i=>p； S4：i+2=>i；S5：若i≤11，返回S3；否则，结束。程序如下：main() { i
nti,p=1; for(i=1;i<=11;i+=2) p=pi; printf
(“p=%d\n”,p); }例EX2_2判定2000年－2500年中那些年份是闰年，并将结果输
出。闰年的条件是：能被4整除，但不能被100整除的年份是闰年；能被400整除的年份是闰年。不符合以上两个条件的年份都不
是闰年。算法一如下：设y为被判断的年份，解题步骤为：S1：2000=>y;S2：若y不能被4整除，则
不输出y的值，并转向S6；S3；若y不能被100整除，则输出y的值，并转向S6；S4：若y能被400整除，则输
出y的值，并转向S6；S5：否则不输出y的值，S6：y+1=>y;S7：当y≤2500时，转S2继
续执行，若y>2500，算法结束。程序如下：直到y>2500y+1=>y打印yTy%400==0F
打印yTy%100!==0FT
y%4==0F2000=>yN-S图表示直到y>2500y+1=>
y打印y换行Tk%10==0Fk+1=kT
leap==1F0=>leap1
=>leapTy%400==0F1=>leap0=>leapTy%
100!=0FT
y%4==0F2000=>y,0=>leap,0
=>kN-S图表示（进一步细化）几点说明：1）在细化的过程中增加了变量leap和k，leap是一个标志，当leap=1时，标
志那个年份为闰年，当leap==0时，那个年份就不是闰年；k是一个计数器，当k==10时，希望打印机能自动换行。2）运算符%为求
余（求模）运算符。y%4==0，即y对4求余，其值等于零，是一个判断条件，以下y%100!=0、y%400==0都是解决问题所提出
的条件。从框图中可以看出当y%4==0并且y%100!=0时，这个年份是闰年，因此将1赋予leap，而当y%4==0且y%100=
=0时，这个年份就不是闰年，因此将0赋予leap，也就是说leap只有两个值，非0即1，起到了标志的作用。3）k是一个计数器，每
输出一个值，自动加1，超过10后，让计算机自动换行，使每行输出10个数据。main(){ inty,leap,k=
0; for(y=2000;y<=2500;y++) { if(y%4
==0) { if(y%100==0) { if(y%
400==0)leap=1; elseleap=0;}
elseleap=1;} elseleap=0; if(leap==1) {
k++; if(k%10==0)printf(“\n”);
elseprintf(“%5d”,y);} } printf(“\n”
);}ABC算法二：采用集合的方法进行处理：设有集合A为能被4整除的数，B为能被100整除的数，C为能
被400整除的数，则闰年可以表示为以下的集合运算表达式：右上图红色部分表示的是闰年，即集合运算的结果。下面给出C程序：
设A集合表示为：y%4==0，B集合表示为：y%100==0，C集合表示为：y%400==0，用&&表示集合中的交运算（C语言称为
与运算），用||表示集合中的并运算（C语言称为或运算），则可以用以下表达式表示：(y%4==0)&
&(y%100!=0)||(y%400==0)main(){inty,leap,k=0;
for(y=2000;y<=2500;y++){ if((y%4==0)
&&(y%100!=0) ||(y%400==0)) leap=1; elselea
p=0; if(leap) { k++; if(k%10==0)printf(“\
n”); elseprintf(“%7d”,y); }}printf(“\n”)
;}例EX2_3求算法可以表示如下：S1：1=>signS2：1=>sum
S3：2=>denoS4：(-1)×sign=>signS5：sign×(1/de
no)=>termS6：sum+term=>sumS7：deno+1=>deno
S8：若deno≤100，返回S4；否则算法结束。程序如下：main(){ intdeno; floatsig
n=1.0,sum=1.0,term; for(deno=2;deno<=100;deno++) { sign
=-sign; term=sign/deno; sum=sum+term } printf(“
SUM=%6.4f\n”,sum);}例EX2_4任意给定一个大于等于3的正整数，判断它是否为素数。
所谓素数，是指除1和它本身之外，不能被其他任何整数整除的数。判断一个数是否为素数的方法只要将给定的数（设其为n）作被除数，用
2到n–1分别去除n，如果都不能整除n，则n是素数，否则n不是素数。算法如下：S1：从键盘输入n的值；
S2：2=>i;S3：n%i=>r; /%为求余运算，r为余数/S4：如果r=0，则
表示n能被i整除，输出“n不是素数”，算法结束；否则执行S5；S5：i+1=>i;S6：如果i≤
，返回S2；否则算法结束。程序如下：main(){ intn,i,k,flag=1; printf(
“Inputaintegernumber:\n”); scanf(“%d”,&n); i=2;k
=sqrt(n); while(i<=.k&&flag!=0) { if(n%i==0)
flag=0; elsei++; } if(flag==1) printf(“%disa
primenumber.”,n); elseprintf(“%dnotisaprimenumber.”
,n);}一个算法应该具有以下特征：1、有穷性一个算法应包含有限的操作步骤，而不能是无限的。事实上
，“有穷性”往往是指“在合理的范围之内”，超过合理的限度，也就不能视作有效算法。2、确定性算法中的
一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。也就是说，算法的含义应当是唯一的而不应当产生“歧义性”，所谓“歧义性”是
指可以被理解为两种（或多种）的可能含义。3、有零个或多个输入所谓输入是指在执行算法时需要从外部得到必要的信息（数值
信息，字符信息等），当然也可以没有输入（实际上，数据信息已经表达在算法（或程序）中）。5、有效性任何算法中的每一步
骤都能有效地执行，并且得到确定的结果。因此在表达算法时应保证算法的每一过程是有意义的。4、有一个或多个输出算法的目的
是为了求得数据的解，要得到“解”，就有输出。输出可以通过显示器或打印机等设备，没有输出的算法是没有实际意义的。1、三种
基本结构1966年，Bohre和Jacopini提出了以下三种基本结构，用这三种基本结构作为表示一个良好算法的基本单元
。（2）选择结构，或称选取结构或分支结构，虚线框内是一个选择结构。此结构中必包含一个判断框，根据给定条件P是否成立而选择执行
A框或B框，P是一个根据实际问题而提出的条件，当条件P成立时，执行A框所指定的操作，否则执行B框所指定的操作。无论P条件是否成立，
只能执行A框或B框之一，不可能既执行A又执行B，无论走哪一条路径，都经过c点脱离选择结构。（1）顺序结构：虚线框内是一个顺序
结构。其中A和B两个框是顺序执行的。即在执行完A框所指定操作后，必然接着执行B框所指定的操作。顺序结构是最简单的一种结构。AB
PABYesNoaabb图一：顺序图二、选择（3）循环结构，又称重复结构，即反复执行某一部分操作，虚
线框内是一个循环结构。结构中包含一个条件判断，当条件P成立时重复执行A框所指定的操作，当条件P不成立时执行循环结构以后的操作。条件
P是隐含在循环结构中的，在执行循环结构时，每执行一次重复操作，就必须对条件进行一次判断，当条件不成立时即从循环结构中跳出，执行其以
下操作。循环结构有两种形式：当型循环（While循环）和直到循环（Until循环），将在下面的讲述中介绍。APY
esNoab图三：当循环APYesNoab图四、直到循环以上三种基本结构，有以下共同特点：（1）
只有一个入口，在结构图虚线框上部；（2）只有一个出口，在结构图虚线框下部；（3）结构内的每一部分都有机会被执行，也就是说，对每
一个框来说，都应当有一条入口到出口的路径通过它；（4）结构内不存在“死循环”（无法终止的循环）。已经证明，由三种基本结
构组成的算法结构，可以解决任何复杂的问题。由于基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在基本结构内部允许存在分支和向前或向后的转向（转移）。2、用N－S流程图表示算法既然用基本结构的顺序可以表示任何复杂的算法结构，基本结构之间的连线就属多余的了。1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，全部算法写在一个矩形框中，在该框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称为N－S结构流程图。由于流程图适用于结构化程序设计，因此很受欢迎。N－S结构流程图用以下流程图符号：（1）顺序结构：如图一，A和B两个框组成一个顺序结构。BA图一：顺序结构（2）选择结构：如图二，当P条件成立时执行A操作，P条件不成立时执行B操作。整个图是一个整体，代表一个基本结构。BATPF图二、选择结构 |
|
