第二章控制结构.doc

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