2第章算法——程序的灵魂算法+数据结构=程序数据结构对数据的描述。在程序中要指定用到哪些数据，以及这些数据的类型和数据的组织形式。算法对操作
的描述。即要求计算机进行操作的步骤沃思数据结构程序设计方法语言工具算法程序员算法广义地说，为解决一个问题而采取的方法和步骤，就称为
“算法”。对同一个问题，可以有不同的解题方法和步骤。为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。
数值运算的目的是求数值解。由于数值运算往往有现成的模型，可以运用数值分析方法，因此对数值运算的算法的研究比较深入，算法比较成熟。
非数值运算算法算法计算机在非数值运算方面的应用远超在数值运算方面的应用。非数值运算的种类繁多，要求各异，需要使用者参考已有的类似算
法，重新设计解决特定问题的专门算法。数值运算算法1.算法算法定义算法特征定义：现实生活中解决问题时，一般都要制订一个针对具体问
题的步骤和方法，以此为据去实现目标。将为了解决问题所制订的步骤、方法称为算法(Algorithm)。算法描述：计算下面的分段函数。
（1）输入x的值；（2）判断x是否大于0，若大于0，则y为2x-1，然后转第5步；否则进行第3步；（3）判断x是否等于0，
若等于0，则y为0，然后转第5步；否则进行第4步；（4）y为3x+1；（5）输出y的值后结束。C语言程序设计1.算法算法定
义算法特征特征：（1）有穷性：算法中所包含的步骤必须是有限的，不能无穷无止，应该在一个人所能接受的合理时间段内产生结果；（2）
确定性：算法中的每一步所要实现的目标必须是明确无误的，不能有二义性；（3）有效性：算法中的每一步如果被执行了，就必须被有效地执行
。例如，有一步是计算X除以Y的结果，如果Y为非0值，可有效执行，但如果Y为0值，则无法得到有效执行；（4）有零或多个输入：根据
算法的不同，有的在实现过程中需要输入一些原始数据，而有些算法可能不需要输入原始数据；（5）有一个或多个输出：设计算法的最终目的
是为了解决问题，为此，每个算法至少应有一个输出结果，来反应问题的最终结果。C语言程序设计简单的算法举例若题目改为:求1×3×5
×7×9×11【例2.1】求1×2×3×4×5算法步骤算法步骤S1:先求1乘以2，得到结果2S2:将步骤1得到的乘积2再乘以3
，得到结果6S3:将6再乘以4，得24S4:将24再乘以5，得120S1:令p=1，或写成1=>p(表示将1存放在变量p中)
S2:令i=2，或写成2=>i(表示将2存放在变量i中)S3:使p与i相乘，乘积仍放在变量p中，可表示为:pi=>pS4:
使i的值加1，即i+1=>iS5:如果i不大于5，返回重新执行S3及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5
!的值。3=>ii=3i+2=>i2若i≤11，返回S3；否则，结束或者若i>11，结束；否则，返回S3用这种方法表示的算法具有
一般性、通用性和灵活性简单的算法举例算法步骤【例2.2】有50个学生，要求输出成绩在80分以上的学生的学号和成绩S1:1=>iS
2:如果gi≥80，则输出ni和gi，否则不输出S3:i+1=>iS4:如果i≤50，返回到S2，继续执行，否则，算法结束
n：表示学生学号下标i：表示第几个学生n1：表示第一个学生的学号ni：表示第i个学生的学号g：表示学生的成绩g1：表示第一个学生的
成绩gi：表示第i个学生的成绩简单的算法举例【例2.3】判定2000—2500年中的每一年是否为闰年，并将结果输出Year被100
整除，又能被400整除03算法步骤S1:2000=>yearS2:若year不能被4整除，则输出year的值和“不是闰年”。
然后转到S6，检查下一个年份S3:若year能被4整除，不能被100整除，则输出year的值和“是闰年”。然后转到S6S4:若
year能被400整除，输出year的值和“是闰年”，然后转到S6S5:输出year的值和“不是闰年”S6:year+1=>
yearS7:当year≤2500时，转S2继续执行，否则算法停止其他非闰年闰年0401闰年非闰年Year不能被4整除Year被
4整除，但不能被100整除02简单的算法举例?【例2.4】求算法步骤S1:sign=1S2:sum=1S3:deno=2S
4:sign=(-1)signS5:term=sign(1/deno)S6:sum=sum+termS7:deno=d
eno+1S8:若deno≤100返回S4；否则算法结束sign：表示当前项的数值符号term：表示当前项的值sum：表示当前项
的累加和deno：表示当前项的分母简单的算法举例【例2.5】给出一个大于或等于3的正整数，判断它是不是一个素数算法步骤S1:输入
n的值S2:i=2（i作为除数）S3:n被i除，得余数rS4:如果r=0，表示n能被i整除，则输出n“不是素数”，算法结束；
否则执行S5S5:i+1=>iS6:如果i≤n-1，返回S3；否则输出n的值以及“是素数”，然后结束解题思路:所谓素数(p
rime)，是指除了1和该数本身之外，不能被其他任何整数整除的数。?实际上，n不必被2~(n-1)之间的整数除，只须被2~n/2间
整数除即可，甚至只须被2~之间的整数除即可。?i≤算法的特性1有穷性一个算法应包含有限的操作步骤，而不能是无限的2确定性算法中
的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的3有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息4有一
个或多个输出算法的目的是为了求解，“解”就是输出5有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果自然语言算法的表示
传统流程图结构化流程图伪代码用流程图表示算法处理框起止框流程线输入输出框连接点判断框注释框算法的流程图表示举例开始1=>p【例2.
6】将例2.1的算法用流程图表示。求1×2×3×4×5。算法步骤S1:1=>pS2:2=>iS3:pi=>pS4:i
+1=>iS5:如果i≤5，则返回S3；否则结束2=>ipi=>pP:表示被乘数i:表示乘数i+1=>iNi>5Y输出p结
束算法的流程图表示举例开始1=>i【例2.7】例2.2的算法用流程图表示。有50个学生，要求输出成绩在80分以上的学生的学号和成
绩。算法步骤输入ni、giS1:1=>iS2:如果gi≥80，则输出ni和gi，否则不输出S3:i+1=>iS4:如果i
≤50，返回到S2，继续执行，否则，算法结束i+1=>in：表示学生学号下标i：表示第几个学生n1：表示第一个学生的学号ni：表示
第i个学生的学号g：表示学生的成绩g1：表示第一个学生的成绩gi：表示第i个学生的成绩Ni>50Y1=>iYgi≥80输出ni、g
ii+1=>iNi>5Y结束开始算法的流程图表示举例2000=>year【例2.8】例2.3判定闰年的算法用流程图表示。判定2
000—2500年中的每一年是否为闰年，将结果输出。Year不能被4整除YNYear不能被100整除NYYear不能被400整除N
Y输出year“是闰年”输出year“不是闰年”输出year“是闰年”输出year“不是闰年”Year+1=>yearYear>2
500Y结束开始算法的流程图表示举例1=>sum2=>deno【例2.9】将例2.4的算法用流程图表示。求?算法步骤1=>si
gnS1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)signS5:term=sign(1
/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否则算法结束(-1)
sign=>signsign(1/deno)=>termsign：表示当前项的数值符号term：表示当前项的值sum：表示当前
项的累加和deno：表示当前项的分母sum+term=>sumdeno+1=>denoNdeno>100Y输入sum结束简单的算法
举例开始输入n【例2.10】例2.5判断素数的算法用流程图表示。对一个大于或等于3的正整数，判断它是不是一个素数。2=>i算法
步骤?S1:输入n的值S2:i=2（i作为除数）S3:n被i除，得余数rS4:如果r=0，表示n能被i整除，则输出n“不是
素数”，算法结束；否则执行S5S5:i+1=>iS6:如果i≤，返回S3；否则输出n的值以及“是素数”，然后结束n/i的余数=
>rr=0i+1=>i输出n“不是素数”N?i>Y输出n“是素数”结束传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流
程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律，阅读时要花很大精力去追踪流程，使人难
以理解算法的逻辑。三种基本结构真P假P假AAB真BA顺序结构选择结构循环结构三种基本结构的特点只有一个入口1只有一个出口2结构内的
每一部分都有机会被执行到3结构内不存在“死循环”4用N-S流程图表示算法用伪代码表示算法伪代码是用介于自然语言和计算机语言之间的文
字和符号来描述算法。它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便，格式紧凑
，修改方便，容易看懂，也便于向计算机语言算法(即程序)过渡。算法的流程图表示举例begin (算法开始)1=>p2=>I
whilei≤5{pi=>pi+1=>I}printpend (算法结束)【例2.16】求5!，用伪
代码表示。算法步骤S1:1=>pS2:2=>iS3:pi=>pS4:i+1=>iS5:如果i≤5，则返回S3；否则结束
P:表示被乘数i:表示乘数伪代码算法的流程图表示举例begin (算法开始)1=>sign1=>sum2=>deno
whiledeno≤100{(-1)sign=>signsign(1/deno)=>termsum+
term=>sumdeno+1=>deno}printsumend (算法结束)?【例2.17】求，用伪代码表示。
算法步骤S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)signS5:term=sign
(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否则算法结束s
ign：表示当前项的数值符号term：表示当前项的值sum：表示当前项的累加和deno：表示当前项的分母伪代码用计算机语言表示算法
【例2.18】将例2.16表示的算法（求5!）用C语言表示。算法步骤S1:1=>pS2:2=>iS3:pi=>pS4:i
+1=>iS5:如果i≤5，则返回S3；否则结束#includeintmain(){ inti,p; p
=1; i=2; while(i<=5) { p=pi; i=i+1; } printf(″%d\n″,p); retu
rn0;}P:表示被乘数i:表示乘数用计算机语言表示算法?【例2.18】将例2.17表示的算法求的值用C语言表示。算法步骤S
1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)signS5:term=sign(1/d
eno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否则算法结束#inclu
deintmain(){ intsign=1; doubledeno=2.0,sum=1.0,term; while(deno<=100) { sign=-sign; term=sign/deno; sum=sum+term; deno=deno+1; } printf(″%f\n″,sum); return0;}sign：表示当前项的数值符号term：表示当前项的值sum：表示当前项的累加和deno：表示当前项的分母结构化程序设计方法模块化设计自顶向下13结构化编码逐步细化42一个流程图包括以下几部分。(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。 |
|
