第二章控制结构

1第2章控制结构本章目标•结构化程序设计方法的基本思想•C++的基本控制结构•熟悉使用伪代码的编程方法授课内容•2.1程序的基本控制结构•2.2自顶向下，逐步求精•2.3Ｃ++的控制结构•实例编程•程序设计举例2.1程序的基本控制结构•算法•程序、程序设计•结构化程序设计方法•模块化程序结构•三种基本程序结构算法•定义：指为解决特定问题而采取的有限操作步骤•特性:•有穷性算法是有限的操作序列•确定性每个操作有确定的含义；无二义性•可执行性每个操作都是可以执行的•有序性执行步骤严格按逻辑顺序进行程序、程序设计程序•是指计算机实现特定操作的指令的集合。•程序=数据结构（属性、联系）+算法程序设计•是人们关于现实问题求解的思维活动的“代码化”过程，是用计算机语言作为工具进行的创造性劳动。•编程序的一个主要内容就是如何将解决应用问题所使用的算法用Ｃ++的语句和函数来描述。换句话说，也就是如何组织Ｃ++程序的结构。结构化程序设计方法2“软件危机”---结构化程序设计基本观点：•程序设计的目标不应再集中于如何充分发挥硬件的效率方面，新的程序设计方法应以能设计出结构清晰、可读性强、易于分工合作编写和调试的程序。结构化设计方法是以模块化设计为中心模块化程序结构模块化•就是把程序划分为若干个部分，每个部分独立存放、完成一个特定的功能。其目的是降低程序的复杂度，使设计出来的程序便于阅读、调试和维护。•一个模块可以是一条语句、一段程序、一个函数等•基本特征是其仅有一个入口和一个出口•模块相互独立，内聚性很强，一个模块完成一个功能三种基本程序结构按照结构化程序设计的观点,任何算法功能都可以通过由程序模块组成的三种基本程序结构的组合:•顺序结构：程序是按程序语句或模块在执行流中的顺序逐个执行。•选择结构：程序是按设定的条件实现程序执行流的多路分支。•循环结构：程序是按给定的条件重复地执行指定的程序段或模块。结论：理论上已经证明，用三种基本程序结构可以实现任何复杂的算法。三大基本结构示意图顺序结构模块（语句）A模块（语句）B选择结构成立不成立条件条件3循环结构（当型循环）不成立成立程序模块程序模块（直到型循环）程序模块程序模块成立条件条件不成立42.2自顶向下,逐步求精结构化程序设计支持“自顶向下,逐步求精”的程序设计方法。“自顶向下”•是将复杂、大的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地去描述问题。“逐步求精”•是将现实世界的问题经抽象转化为逻辑空间或求解空间的问题。复杂问题经抽象化处理变为相对比较简单的问题。经若干步抽象（精化）处理，最后到求解域中只是比较简单的编程问题。基本思想和方法基本思想•从问题本身开始，经过逐步求精，将解决问题的步骤分解为由基本程序结构模块组成的结构化程序框图，据此编写程序。基本方法•从题目本身开始,找出解决问题的基本思路,将其用结构化框图(可能是非常粗糙)表示。•对框图中的比较抽象的、用文字描述的模块进一步分析细化，结果仍用结构化框图表示。•将所求解问题的所有细节都弄清楚后,再可以根据框图直接写出相应程序代码。[例2-1]验证“哥德巴赫猜想”“哥德巴赫猜想”•任何一个大于等于4的偶数均可以表示为两个素数之和。使用流程图分析•在分析的过程中用结构化框图表示解题思路的优点是框图中的每个程序模块与其他程序模块之间的关系非常简明,每次可以只集中精力分解其中的一个模块而几乎不影响整个程序的结构。求解第一步提出问题：验证哥德巴赫猜想第二步设一上限数M，验证从4到M的所有偶数是否能被分解为两个素数之和。•定义一个变量X，初值为4。•每次令其加2，并验证X能否被分解为两个素数之和，直到X不小于M为止。第三步如何验证X是否能被分解为两个素数之和验证哥德巴赫猜想X=4X=4否XMXM是验证X是否能被分解为两个素数之和验证X是否能被分解为两个素数之和51.从P=2开始；2.判别X-P是否仍为素数：3.若是，打印该偶数的分解式。4.否则，换更大的素数，再继续执行2.。如此循环，直到用于检测的素数大X/2且X与其之差仍不是素数，则打印“哥德巴赫猜想”不成立。2.3C++的控制结构顺序语句选择结构循环结构1、顺序结构r=p;p=q;q=r;2、选择结构（之一）一路分支:语句格式：if（表达式）语句序列P=2P=2否P=X/2且X-P不是素数P=X/2且X-P不是素数是生成下一个素数P=X/2P=X/2是否处理哥德巴赫猜想不成立的情况处理哥德巴赫猜想不成立的情况打印出X的分解情况打印出X的分解情况不成立条件？条件？成立语句序列语句序列6两路分支:语句格式：if（表达式）语句序列1else语句序列2选择结构（之二）多路（开关）选择语句：switch（整数表达式）{case数值1：语句序列1；…case数值n：语句序列n；[default:语句序列n+1；]}成立不成立条件？条件？语句序列1语句序列1语句序列2语句序列2计算整型表达式计算整型表达式值=？语句序列1语句序列1语句序列2语句序列2语句序列n语句序列n73、循环结构（之一）（执行框图参看第3页）当型循环:语句格式：while（表达式）[{}语句序列循环体[]]直到型循环:语句格式：do{语句序列}while（表达式）;3、循环结构（之二）for语句用来实现计数循环:for(表达式1;表达式2;表达式3)循环体8实例编程验证哥德巴赫猜想算法分析：•前面的流程图•伪代码---“筛法”生成素数表PrimeList[M]•将PrimeList的各元素设置为0到M-1之间的自然数;•分别从表中去掉已经确定的各素数的倍数(将其置换为0);程序逻辑功能框图建立素数表ＣreatPrimeList（PrimeList）建立素数表ＣreatPrimeList（PrimeList）x=4否XM？XM？是P=2否PM/2且PrimeList[x-p]=0？PM/2且PrimeList[x-p]=0？是取下一个素数P=NextPrimeNumber（P，PrimeList）取下一个素数P=NextPrimeNumber（P，PrimeList）x=x+2x=x+2是P=M/2？P=M/2？否显示“哥德巴赫猜想错“显示“哥德巴赫猜想错“打印该偶数分解式打印该偶数分解式9生成素数表子函数#defineM10001/*定义验证范围*///函数CreatPrimeList():生成素数表voidCreatPrimeList(intPrimeList[]){inti,j;//将PrimeList的各元素设置为从0开始的正整数for(i=0;iM;i=i+1)PrimeList[i]=i;//分别从表中去掉已经确定的各素数的倍数(将其置为0)i=2;while(iM/2)//只需验证一半数据{for(j=i+1;jM;j=j+1)if(PrimeList[j]!=0&&PrimeList[j]%PrimeList[i]==0)PrimeList[j]=0;//确定下一个素数的位置i=i+1;while(PrimeList[i]==0)i=i+1;}}求下一个素数子函数//函数NextPrimeNumber:求下一个素数intNextPrimeNumber(intp,intPrimeList[]){p=p+1;while(PrimeList[p]==0)p=p+1;returnPrimeList[p];}主函数//主函数:在从4到M的范围内验证哥德巴赫猜想intmain(){intPrimeList[M];//说明存放素数表的数组intx,p;//变量x:偶数,p:素数CreatPrimeList(PrimeList);//建立素数表//对从4到M的所有偶数验证哥德巴赫猜想x=4;while(xM){//检查偶数减去一个素数后的剩余部分是否仍为素数p=PrimeList[2];10while(p=x/2&&PrimeList[x-p]==0)p=NextPrimeNumber(p,PrimeList);//输出检查结果if(px/2)//找到了一个不能分解为两个素数和的偶数coutGreatdiscovery:Goldbachiswrong!endl;else//PrimeList[x-p]≠0,分解成功coutTheevennumberx=p+x-pendl;x=x+2;//检查下一个偶数}return0;}程序设计举例1.验证“哥德巴赫猜想”(见前述)2.水仙花3.猜幻数游戏例2.2水仙花算法分析：•用穷举法对100~999之间的每个数进行验证。验证公式为：hdn=h^3+d^3+n^3•如何分解一个3位数的百位、十位和个位？是关键！百位=n/100[整除100，丢弃小数]十位=（n/10）%10[整除10，得百位数。再对10取余数，得十位数]个位=n%10[n对10取余数，得个位]例：371•h=371/100=3•d=（371/10）%10=37%10=7•n=371%10=1程序逻辑功能框图n=100n=100否n999？n999？是i=n/100；j=（n/10）%10；k=n%10；h=I^3+j^3+k^3i=n/100；j=（n/10）%10；k=n%10；h=I^3+j^3+k^3n=n+1n=n+1否h=n?h=n?11打印水仙花程序//Example2-5：打印所有的水仙花数#includeiostream.hintmain(){intn,i,j,k;for(n=100;n=999;n=n+1){i=n/100;//取出n的百位数j=(n/10)%10;//取数n的十位数k=n%10;//取出n的个位数if(n==i*i*i+j*j*j+k*k*k)coutn=i^3+j^3+k^3endl;}return0;}例2-3猜幻数游戏系统随机给出一个数字（即幻数），游戏者去猜，如果猜对，打印成功提示，否则打印出错提示，并提示游戏者选择下一步动作，最多可以猜5次。算法for(i=0;n=5;i=i+1)if(猜对)打印成功提示;else打印出错提示;//Example2-6：猜幻数游戏#includeiostream.h#includestdlib.hintmain(){intmagic;intguess;12magic=rand();//随机数产生函数rand()，调用该函数可产生0到32767之间的任意一个数coutGuessthemagicnumber.Itisbetween0and32767.endl;for(inti=1;i=5;i=i+1){cinguess;if(guess==magic){cout***Right***endl;break;}else{if(i==5)coutTheitimeiswrong.Endofgame!endl;else{if(guessmagic)coutYouhavebeenwrongforitime(s).Pleasetryabiggerone.endl;elsecoutYouhavebeenwrongforitime(s).Pleasetryasmallerone.endl;}}}return0;}