结构化程序相关设计讲义

结构化程序相关设计讲义2第三章结构化程序设计与基本算法3.1算法及其表示3.2结构化程序设计3.3顺序结构3.4选择结构3.5循环结构3.6流程转移控制语句3.733.1算法及其表示N.Wirth提出：数据结构+算法=程序算法：为解决一个具体问题而采取的确定的有限的操作步骤，这里仅指计算机能执行的算法算法特性：有穷性确定性

有效性

没有输入或有多个输入

有一个或多个输出

算法分类：数值算法：解决的是求数值解的问题，例如用辗转相除法求两个数的最大公约数等。非数值算法：主要用于解决需要用分析推理、逻辑推理才能解决的问题，例如人工智能中的许多问题，查找、分类等问题。43.1算法及其表示算法的表示方式自然语言传统的流程图

N-S结构化流程图

伪代码

开始/准备过程/处理选择/决策手动输入文档显示/输出终止离页连接53.2结构化程序设计已经证明，任何程序均可只用顺序结构、选择结构、循环结构这三种结构综合描述。只用这三种结构编制的程序，叫结构化程序。程序应符合结构化规则。采用顺序、选择和循环三种基本结构作为程序设计的基本单元只有一个入口；只有一个出口；无死语句，即不存在永远都执行不到的语句；无死循环，即不存在永远都执行不完的循环，但也有例外。采用“自顶向下、逐步求精”和模块化的方法进行结构化程序设计E.W.Dijkstra，生于1930年，卒于2002年8月6日63.2结构化程序设计—流程表示BABA条件P顺序结构选择结构73.2结构化程序设计—流程表示条件PA真假假条件PA假真当型循环直到型循环83.3顺序结构顺序结构：按照语句出现的先后顺序依次执行。一般：表达式；例如：

i++;sum=a+b; cout<<a<<b<<endl;特例：；(空语句)

作用:当程序中某个位置在语法上需要一条语句，而在语义上又不要求执行任何动作时，可放上一条空语句。一般适用于在循环语句中做空循环体：for(m=0;m<1000;m++);93.3顺序结构复合语句：

{ [变量定义]

语句组

}作用：当程序中某个位置在语法上只允许一条语句，而在语义上要执行多条语句才能完成某个操作时，需要使用复合语句。变量仅在定义它的复合语句内有效一般适用于选择、循环语句中的内嵌语句。也有时为了清晰，特意将某段程序中{}括起来。103.4选择结构选择结构：根据条件的值来判断程序的流向。C/C++中，提供两类选择控制语句:if语句，实现n分支，要求n个表达式;switch语句，实现多分支；只用1个表达式。113.4选择结构3.2.1if语句if语句的三种形式:

形式1：

if(表达式)语句作用：当表达式为真(非0)时，执行表达式后面的语句,否则绕过该语句，而执行其后面的语句。例3.1已知两个数x和y，比较它们的大小，使得x大于y。思考：如何将一瓶油与一瓶酒互相换瓶？

需借助于一个空瓶子内存中的两个单元也可以看成放着一瓶油与一瓶酒，要交换其中放的内容，同样需借助于一个空的内存单元。这是由内存”取之不尽，一冲就走”的物点决定的。123.4选择结构于是，有if(x<y){t=x;x=y;y=t;} cout<<x<<y;#include"iostream.h"voidmain(){intx,y,t;cout<<"输入xy"<<endl;cin>>x>>y;if(x<y){t=x;x=y;y=t;}//x与y交换

cout<<x<<">"<<y<<endl;}完整的程序如右：133.4选择结构形式2：

if(表达式)

语句1else

语句2

作用：当表达式为真时，执行语句1，否则执行语句2。例3.2计算分段函数：143.4选择结构实现此题可采用双分支结构，也可采用单分支结构。if(x)y=sin(x)+sqrt(x*x+1);elsey=cos(x)－x*x+3*x;y=cos(x)－x*x+3*x;if(x)y=sin(x)+sqrt(x*x+1);思考：若将右边的两个语句上下交换一下，还能实现上例的要求吗？

不能153.4选择结构形式3：

if(表达式1)

语句1 elseif(表达式2)

语句2 ┆ elseif(表达式n)

语句n else

语句n+1作用：当表达式1的值为true时，执行语句1；否则判断当表达式2的值为true时执行语句2；依此类推，若表达式的值都为false，则执行语句n+1。163.4选择结构例3.3已知成绩mark，要求显示对应五级制的评定，评定条件：if(mark>=90)cout<<"优"; elseif(80<=mark&&mark<90)cout<<"良"; elseif(60<=mark&&mark<70)cout<<"及格"; elseif(70<=mark&&mark<80)cout<<"中"; else cout<<"不及格"; if(mark>=60)cout<<"及格";elseif(mark>=70)cout<<"中";elseif(mark>=80)cout<<"良";elseif(mark>=90)cout<<"优";elsecout<<"不及格";√×注意：①不管有几个分支，程序执行一个分支后，其余分支不再执行。②elseif不能写成elseif。③当多分支中有多个表达式同时满足，则只执行第一个与之匹配的语句。173.4选择结构if语句的嵌套形式

if语句的嵌套是指if或else后面的语句本身又是一个if语句。如：if(表达式1) if(表达式11)

语句11else

语句12else

语句2if(表达式1)if(表达式2)

语句1else

语句2

如何使之与第一个if配对？注意：为了增强程序的可读性，建议采用锯齿型的书写形式。

else始终与它上面的最近的if语句配对，而这个if语句又没有其它的else与之匹配。183.4选择结构例3.4已知x，y，z三个数，使得x>y>z。可用一个IF语句和一个嵌套的IF语句实现。if(x<y){t=x;x=y;y=t;}if(y<z){t=y;y=z;z=t; if(x<y) {t=x;x=y;y=t;}}193.4选择结构现场编程：体型判断。按“体指数”对肥胖程度进行划分，体指数t=体重w/(身高h)2

（w单位为公斤，h单位为米）当t<18时，为低体重；当t介于18和25之间时，为正常体重；当t介于25和27之间时，为超重体重；当t>=27时，为肥胖。编程从键盘输入你的身高h和体重w，根据给定公式计算体指数t，然后判断你的体重属于何种类型。提示：可用3种方法编程中的一种算法1：用不带else子句的if语句编程算法2：用在if子句中嵌入if语句的形式编程算法3：用在else子句中嵌入if语句的形式编程

(10分钟，请自告奋勇)203.4选择结构

3.2.2switch语句形式：switch(表达式）{case常量表达式1：语句组1；

[break；]case常量表达式2：语句组2；

[break；]┆case常量表达式n：语句组n；

[break；][default：语句组n+1]}执行顺序：当表达式的值与某个常量表达式的值相等时，则执行该常量表达式后面相应的语句，若使用了break,则执行完该语句后便退出switch语句；否则，还要依次执行其后面的各条语句。若找不到相匹配的常量表达式，则执行default后面的语句。必须为整型或字符型

213.4选择结构现场编程：设计一个简单的计算器程序，要求根据用户从键盘输入的表达式：操作数1运算符op操作数2

然后，计算表达式的值，指定的运算符为加（+）、减（-）、乘（*）、除（/）提示：用switch语句。223.4选择结构 2a+1(1<=a<2)【例3.5】用switch结构求分段函数b=a2-3(2<=a<4) a其它正确：switch((int)a){case1:b=2*a+1;break;case2:case3:b=a*a-3;break;default:b=a;}错误：switch((int)a){casea>=1&&a<2:……casea>=2&&a<4:.…..default:b=a;}共用同一个语句组

思考：若省去break语句，情况会怎样？

233.5循环结构C语言提供了三种循环语句，流程图如下：

while do-while forwhile(表达式)

语句do语句while(表达式);for(表达式1;表达式2;表达式3)语句243.5循环结构例3.6/3.8用上述三种循环语句求while语句:n=1;s=0;while(n<=100){s=s+n;n=n+1;}n=1;s=0;do{s=s+n;n=n+1;}while(n<=100);do-while语句:for(n=1,s=0;n<=100;n++)s=s+n;for语句:253.5循环结构例3.7求下列级数的前m项和,要求其误差小于0.00001分析:级数的通项为xm/m!,

第i项ti与第i-1项ti-1之间存在如下关系：

ti=ti-1*x/iinti(1);floatt(1),e(0);while(t>1e-5){e+=t;t/=i;i++;}inti(1);floatt(1),e(0);for(;t>1e-5;){e+=t;t/=i;i++;}for(i=1,t=1,e=0;t>1e-5;e+=t,t/=i,i++);分号不能省略空语句263.5循环结构例3.9将可打印的ASCII码制成表格输出，使每个字符与它的编码对应起来，每行打印7个字符。看程序，思考：你认为完成该例，关键在什么地方？for通常有一个循环变量控制循环的次数，不要在循环体内改变这个变量273.5循环结构现场编程----猜数游戏：先由计算机“想”一个数请人猜，如果人猜对了，则计算机给出提示：“Right!”，否则提示：“Wrong!”，并告诉人所猜的数是大还是小。现场编程----先由计算机“想”一个1到100之间的数请人猜，如果人猜对了，则结束游戏，否则计算机给出提示，告诉人所猜的数是太大还是太小，直到人猜对为止。计算机记录人猜的次数，以此来反映猜数者“猜”的水平。283.5循环结构猜数游戏用到的库函数随机函数rand()#include<stdlib.h>

产生[0,32767]之间随机数.

随机函数srand为函数rand()设置随机数种子实现对函数rand所产生的伪随机数的“随机化”,使用计算机读取其时钟值并把该值自动设置为随机数种子，产生[0,100]之间的随机数C中函数time()返回以秒计算的当前时间值，该值被转换为无符号整数并用作随机数发生器的种子#include<time.h>srand(time(NULL));magic=rand()%101+0;

293.5循环结构#include"iostream.h"#include"stdlib.h"voidmain(){ inti,a; for(i=0;i<10;i++) { a=rand()%101; cout<<a<<''; }}问题：每一次运行程序，所得到的随机数序列都一样吗？一样这是因为初始种子是默认的，要改变必须使每次运行的初始种子不一样，这就要用到srand函数了，想一想如何修改程序？303.5循环结构循环的嵌套：循环体内包含另一个完整的循环结构。三种循环语句皆可以相互嵌套。例3.10打印九九乘法表

313.5循环结构#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){ for(intj=1;j<=9;j++) cout<<i<<"×"<<j<<"="<<i*j<<'\t'; cout<<endl;}}程序：思考：打印上三角或下三角程序如何改动？323.5循环结构#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){for(intk=1;k<=i-1;k++)cout<<'\t';for(intj=i;j<=9;j++)cout<<i<<"×"<<j<<"="<<i*j<<'\t'; cout<<endl;}}#include"iostream.h"voidmain(){cout<<"\t九九乘法表"<<endl;cout<<"\t-----------"<<endl;for(inti=1;i<=9;i++){for(intj=1;j<=i;j++)cout<<i<<"×"<<j<<"="<<i*j<<'\t';cout<<endl;}}打印下三角的程序打印上三角的程序333.5循环结构使用嵌套的循环体时，应注意以下问题：在嵌套的各层循环体中，使用复合语句（即用一对大花括号将循环体语句括起来）保证逻辑上的正确性

内层和外层循环控制变量不应同名，以免造成混乱

嵌套的循环最好采用右缩进格式书写，以保证层次的清晰性

循环嵌套不能交叉，即在一个循环体内必须完整的包含着另一个循环

合法的嵌套循环343.5循环结构现场编程：国王的许诺。相传国际象棋是古印度舍罕王的宰相达依尔发明的。舍罕王十分喜欢象棋，决定让宰相自己选择何种赏赐。这位聪明的宰相指着8×8共64格的象棋盘说：陛下，请您赏给我一些麦子吧，就在棋盘的第一个格子中放1粒，第2格中放2粒，第3格放4粒，以后每一格都比前一格增加一倍，依此放完棋盘上的64个格子，我就感恩不尽了。舍罕王让人扛来一袋麦子，他要兑现他的许诺。

国王能兑现他的许诺吗？试编程计算舍罕王共要多少麦子赏赐他的宰相，这些麦子合多少立方米？（已知1立方米麦子约1.42e8粒）

总粒数为：sum=1+2+22+23+…+263

353.5循环结构死循环永远不会退出的循环为死循环for(;;){}while(1){}do{}while(1)一般情况下，要极力避免死循环绝大多数程序不需要死循环。如果出现，往往都是bug时间过长的循环会造成“假死”效果，也要考虑解决363.5循环结构选择三种循环的一般原则：如果循环次数已知，用for如果循环次数未知，用while如果循环体至少要执行一次，用do-while

这只是“一般”原则，不是“原则”373.6流程转移控制语句—break&continueBreak在switch语句中出现过，保证多分支情况的正确执行；break和continue还对for、while、do-while循环进行内部手术：break，退出循环continue，中断此次循环体的执行，开始下一次

少用为妙假假真真break表达式1表达式2循环语句的下一条语句循环语句的下一条语句假假真真contiue表达式1表达式2continue383.6流程转移控制语句—break&continue分析下面两段代码如何执行的。for(m=20;m>0;m--){if(m%6==0)break;cout<<m<<"";}for(m=20;m>0;m--){if(m%6==0)continue;cout<<m<<"";}393.6流程转移控制语句—gotogoto与标号标号举例error:goto举例gotoerror;一般形式

goto语句标号;

……

语句标号：……或语句标号：……

……goto语句标号;糟糕的goto：START_LOOP:if(fStatusOk){if(fDataAvaiable){i=10;gotoMID_LOOP;}else{gotoEND_LOOP;}}else{for(i=0;i<100;i++){MID_LOOP://lotsofcodehere……}gotoSTART_LOOP;}END_LOOP:Dijkstra早在1968年就指出：“Gotoconsideredharmful”

，“Ibecameconvincedthatthegotostatementshouldbeabolishedfromall"higherlevel"programminglanguages.”“Thegotostatement…istoomuchaninvitationtomakeamessofone'sprogram.”现代观点认为：混乱根源不在goto，而在标号；任何程序都可以不用goto就实现其功能；但在某些情况下，使用goto可以让程序更清晰使用原则：使用之后，程序仍然是单入口，单出口不要使用一个以上的标号不要用goto往回跳，要向下跳不要让goto制造出永远不会被执行的代码403.6流程转移控制语句exit(0)作用是终止整个程序的执行，强制返回操作系统,调用该函数需要嵌入头文件stdlib.h。此函数为出现异常，结束整个程序的运行提供了支持。例3.11分别用if和goto、for语句实现求和。

记住要写上标号。413.7应用举例1.求最大值（或最小值）例3.12从键盘输入一组数，求这组数中的最大值。cin>>m;max=m;//第一个数假设为最大数

while(cin>>m,m!=0)if(m>max)max=m;max=0;//设一个较小的数为最大值的初值

for(inti=0;i<10;i++){cin>>m;if(m>max)max=m;}以输入0作为结束，输入数的个数未知

输入数的个数已知

423.7应用举例2求最大公约数例3.13输入两自然数m、n，求最大公约数。方法1:欧几里德的辗转相除法

(1)对于已知两数m、n，使m>n；

(2)m除以n得余数r；

(3)若r=0,则n为最大公约数，算法结束；否则继续进行下一步；

(4)则令nm，rn,转第2步继续相除得新的r。方法2:辗转相减法先用两个数相减，判别差是否为0，用小数和差组成新的数对再相减，直到差为0时为止。最后那一组相同的数对即为最大公约数。43#include"iostream.h"voidmain() { intm,n,t,r; cout<<"请输入mn:"<<endl; cin>>m>>n; if(m<n){t=m;m=n;n=t;} while((r=m%n)!=0) { m=n;n=r; }cout<<"最大公约数为"<<m<<endl;//退出循环时m为最大公约数

}3.7应用举例#include"iostream.h"voidmain() { intm,n; cout<<"请输入mn:"<<endl; cin>>m>>n;

while(m-n!=0) if(m>n)m-=n;elsen-=m;cout<<"最大公约数为"<<m<<endl;//退出循环时m为最大公约数

}方法1方法2不要这句行吗？443.7应用举例3求素数例3.14求2~100之间的素数。素数(质数)----就是除1和它本身以外设有其他的约数的整数。判别某数为质数的最简单方法就是用j=2,3,…,m-1逐个判别m能否被j整除，若都不能被整除，m是素数。另一种判别方法是用j=2,3,…,sqrt(m)逐个判别m能否被j整除，若都不能被整除，m是素数。显然，第一种方法比第二种循环要多一些。453.7应用举例#include"iostream.h"voidmain(){intm,i,countm(0);booltag;for(m=2;m<=100;m++) {tag=false;//tag初值为false for(i=2;i<=m-1;i++) if(m%i==0)tag=true;//m被整除，设置为true //出了内循环，tag的值若为false，说明m没有被i整除过m是素数

if(tag==false) //等价于if(!tag) {cout<<m<<'\t'; countm++; if(countm%8==0)cout<<endl; } }}第一种方法463.7应用举例#include<stdio.h>#include<math.h>voidmain(){ intm,i,k; printf("Pleaseenteranumber:"); scanf("%d",&m); k=sqrt(m); for(i=2;i<=k;i++){ if(m%i==0)break; } if(i>k) printf("Yes!\n"); else printf("No!\n"); printf("Programisover!\n");}进一步，输入一个数，判断其是否是素数。473.7应用举例4穷举法----测试所有的情况例3.15a马克思手稿中有一道趣味数学题：有30个人，其中有男人、女人和小孩，在一家饭馆里吃饭共花了50先令，每个男人各花3先令，每个女人各花2先令，每个小孩各花1先令，问男人、女人和小孩各有几人？对这种不定方程组，可采用穷举法。提示，本题就是解方程组483.7应用举例#include<stdio.h>main(){intx,y,z;printf("Man\tWomen\tChildern\n");for(x=0;x<=30;x++)for(y=0;y<=30;y++)for(z=0;z<=30;z++)if(x+y+z==30&&3*x+2*y+z==50)printf("%3d\t%5d\t%8d\n",x,y,z);}三重循环穷举493.7应用举例#include<stdio.h>

main(){intx,y,z;printf("Man\tWomen\tChildern\n");for(x=0;x<=16;x++)for(y=0;y<=25;y++){z=30–