第7章结构化算法的实现.ppt

第7章 结构化算法的实现,7.1 基本控制结构的C+实现 7.2 子算法设计与C+实现 7.3 递归与迭代,学习目的： 理解算法控制结构与C+控制语句之间的关系； 能够根据结构化算法的PAD图编制C+程序； 深入理解递归与迭代的原理与过程； 熟练应用递归技术解决问题。,7.1 基本控制结构的C+实现,7.1.1 顺序结构的C+实现 7.1.2 分支结构的C+实现 7.1.3 循环结构的C+实现 7.1.4 复杂结构C+实现示例,理想的算法设计应是语言无关的，可使用任何语言实现它，但是这将带来两个问题： 其一，常用算法描述工具的描述能力有限，有些问题采用具体程序 语言所提供的语法对算法进行描述效率会更高、结构更简单； 其二，由于算法与语言的脱离，在使用具体语言实现算法时，程序 与算法描述之间并不总是一一对应的，经常需要对算法进行适当调 整，以利于实现。 在结构化程序设计与实现时巧妙地应用高级语言所提供的各种便利的语法，能起到事半功倍的效果。,7.1.1 顺序结构的C+实现,如果将程序中的每条分支语句和循环语句等复杂语句作为一个整体（一条复杂的语句），那么C+程序中物理上顺序排列的语句（除goto外）的执行顺序与其排列的前后顺序相同，它们之间构成了顺序结构，因此可以将C+的所有语法用于顺序结构算法的实现。,#include “iostream.h“ void main() double r, Peri_bottom, S_bottom, S_side, V, h; coutr; couth; Peri_bottom=6.28*r; S_side=Peri_bottom*h; S_bottom=9.86*r; V=S_bottom*h; cout“The lateral area is “S_sideendl; cout“The volume is “Vendl; ,7.1.2 分支结构的C+实现,算法的分支结构在C+中可以采用if语句或switch语句来实现，其中switch语句主要用于实现多分支结构，这两种语句的结构与算法的分支结构具有很好的对应关系。,例7.1 例2.4中算法的C+实现。 #include “iostream.h“ #include “math.h“ void main() double a, b, c, x1, x2, q; couta; coutb; coutc; if(a=0) cout“错误输入“endl; else q=b*b-4*a*c; if(q0) cout“没有实数解“endl; else /下面两行为减少运算次数 q=sqrt(q); a*=2; x1=(-b+q)/a; x2=(-b-q)/a; cout“第一个根为 “x1endl; cout“第二个根为 “x2endl; ,例7.2 例2.6中算法的C+实现 #include “iostream.h“ void main() int Month; coutMonth; if(Month12) cout“错误月份序号“endl; else switch(Month-1) case 0: cout“January“endl; break; case 1: cout“February“endl; break; case 2: cout“March“endl; break; case 3: cout“April“endl; break; case 4: cout“May“endl; break; /其他月份此处忽略 ,7.1.3 循环结构的C+实现,循环结构在C+程序中有多种实现方式，较好的风格是直到型循环使用do语句、当型循环使用while语句、步长型采用for语句。,#include “iostream.h“ void main() int n=0, s=0, temp=0; coutn; while(n!=0) temp=n/10; s=s*10+(n-temp*10); n=temp; coutsendl; ,#include “iostream.h“ void main() int n=0, s=0, temp=0; coutn; for( ; n!=0; temp=n/10,s=s*10+(n-temp*10),n=temp) ; coutsendl; ,7.1.4 复杂结构C+实现示例,. do if(con2) if(con4) block3 else block4 else if(con3) block1 else block2 while(con1) block5,7.1.4 复杂结构C+实现示例,例7.3 求任意n个整数中的最大者与最小者。 算法输入： 依次输入n个整数。 算法输出： 上述整数中的最大、最小值。 数据结构： n为整数，意义与题同。Max和Min均为整数，是已经输入数 据中的 最大和最小数。x为每次输入的整数。i为整数。 问题分析： 每循环一次输入一个整数，将之与以前的最大数Max和最小 数Min对 比后，根据比较结果更新Max和Min的值。,void main() int n=0, x=0, i=2; coutn; coutx; int Max=x, Min=x; while(ix; if(Maxx) Min=x; i+; cout“Max=“Maxendl; cout“Min=“Minendl; ,7.2 子算法设计与C+实现,7.2.1 参数为普通类型的子算法 7.2.2 参数为指针的子算法 7.2.3 参数为引用的子算法 7.2.4 子算法设计与C+实现示例,对于出现在算法中不同部分的一组相同操作，为减少算法描述工作量，同时使算法更加简洁易读，通常的做法是将这个重复部分提取出来作为一个独立模块并加以命名，在需要的地方通过模块名及参数等信息调用这个模块，而不是反复重复相同的描述，这样的模块被称为子算法（或函数）。PAD图表示方式如下：,7.2.1 参数为普通类型的子算法,子算法的参数为基本类型变量，调用子算法时的调用参数（实在参数）与子算法输入参数（形式参数）的形实结合采用传值方式，对应于C+函数定义及其调用的一般形式 。,算法输入： 子算法入口参数为正整数n和i。 算法输出： 返回上述整数组成的 的值。 数据结构： k为整型变量，含义见下述公式，该量同时用作循环变量。 问题分析： 所给公式中有多个阶乘运算，时间代价较高。同时，阶乘运算的结果往往很大，比如10的阶乘就已达3628800，因此当n稍大就可能造成存储溢出。考虑到分子和分母之间存在公共因子，因此首先对所给公式化简如下：,例7.4 编写算法求,变形后公式的优点在于：,7.2.1 参数为普通类型的子算法,算法描述及程序实现如下：,long GetCombination(int n, int i) long nTemp=1; for(int k=1; k=i; k+) nTemp=nTemp*(n-i+k)/k; return nTemp; ,7.2.2 参数为指针的子算法,这类子算法的参数可以为基本类型指针、数组、函数指针等。,例7.5 使用子算法求n个正整数中的最小数，并求两组5个整数中 最小数之和。 算法输入： 子算法的入口参数为一维数组array及其所含元素数。算法输出： 子算法返回数组中的最小值。 数据结构： data为整型数组。n为所含元素数； nTemp、nTemp1、 nTemp2为整型变量存储中间结果。 算法分析： 因为需要两次从一个数组中提取最小值，因此将这部分功 能独立作为一个模块，形成一个子算法，以便在需要时调 用。这个功能比较简单，按照一般思路得到下面子算法及 调用子算法的主算法。,7.2.2 参数为指针的子算法,这类子算法的参数可以为基本类型指针、数组、函数指针等 。,#include “iostream.h“ int GetMin(int array, int nNum) int nTemp=array0; for(int i=0; iarrayi) nTemp=arrayi; return nTemp; ,void main() int data15= 8, 12, 4, 3, 6; int data25= 2, 7, 8, 2, 1; int nTemp1=GetMin(data1, 5); int nTemp2=GetMin(data2, 5); coutnTemp1+nTemp2endl; ,7.2.3 参数为引用的子算法,引用类型参数使子算法定义形式与其调用形式之间具有直观的对应性，达到类似于传址调用的效果，引用类型参数可以提高数据传递效率。,例7.7 设计子算法，根据汽车的信息（车牌号、油箱体积、本年度累计加油次数）计算本年度该汽车使用汽油量。 算法名称： GetTotalConsumption； 算法输入： 汽车信息（包括汽车牌照、油箱体积、加油次数）。 算法输出： 子算法返回汽车的年耗油量。 数据结构： 类型CarInfo为结构，具有三个字段：szSerial(汽车牌照 号，字符串)、nVol（油箱体积，整型）、nNum（加油次 数，整型）。进入返回 问题分析： 由于子算法所需要的输入均与某辆汽车相关，显然最好的 风格是将它们作为一个整体，因此在本算法实现中定义了 结构类型CarInfo，而为了提高参数的传递效率，将子算法 的参数类型取为引用类型CarType&。具体描述和相应的C+ 实现（其中包括子算法的调用方法示例）如下：,7.2.3 参数为引用的子算法,#include “iostream.h“ #include “string.h“ struct CarInfo char* szPlate; int nVol; int nNum; ; int GetTotalConsumption(CarInfo ,7.2.4 子算法设计与C+实现示例,例7.8 设计一个班级成绩管理程序，该程序能够将每个学生的成绩按照总成绩由高到低的顺序存储，并可通过学号查寻学生的成绩。学生的成绩包括总成绩、语文成绩、数学成绩、化学成绩等。,算法名称： InsertScore 主要功能： 将学生的各科成绩按照总成绩排序插入到班级成绩表的 适当位置。 算法输入： nNum（整型，学号）、pName（字符串，学生姓名）、 nChi（整型，语文成绩）、nMath（整型，数学成绩）、 nChem（整型，化学成绩） 算法输出： 无返回值 数据结构： 使用了班级成绩表ClassScore。,7.2.4 子算法设计与C+实现示例,例7.8,算法名称： ShiftRight。 主要功能： 将某个名次以下的成绩名次顺次下降一名，空出位置用于插入新成绩。 算法输入： nIndexFrom（整型，该名次及该名次后的所有学生名次向后移一名）。 算法输出： 无返回值。 问题分析： 向后移动一个数组的元素应从数组的倒数第二个元素开始，将这个元素拷贝到倒数第一个元素、将第i-1个元素拷贝到第i个元素，直到第nIndexFrom拷贝完为止。这个过程中如果发现某个元素尚未被赋给有效值，那么没必要拷贝这个元素，直接进入下一个元素的拷贝即可。,7.2.4 子算法设计与C+实现示例,例7.8,算法名称： GetScore。 主要功能： 根据学生的学号查寻班级成绩表，并得到该学生的成绩。 算法输入： No（整型，学号）、marks（类型为SCORE&）。 算法输出： 无返回值，查得的学生成绩放置于子算法参数marks中。 数据结构： 使用了ClassScore 。 问题分析： 从成绩表中的第一名顺序检索全表，发现某项的学号与检索关键字nNo相同则返回相应的成绩。,7.3 递归与迭代,7.3.1 递归 7.3.2 迭代 7.3.3 应用示例,7.3.1 递归,分治法： 将复杂问题它分解成若干规模较小，复杂程度较低的小问题，在解决了所有小问题后，根据这些小问题之间的关系，将它们组合在一起，从而得到复杂问题的解。,递 归： 在采用分治法解决复杂问题时经常会发现，在将问题划分成各个层次后，虽然各层次问题的解题算法相同，并且随着层次的加深，问题的复杂性变低，但是解决某个层次的问题往往依赖于下一层问题的解决，只要下一层问题得到解决，这一层的问题就可以解决。由于各层的算法相同，因此很容易就会想到将任意一层的解题过程用一个函数描述出来，由于上一层和下一层的依赖关系，显然解决上一层复杂问题时需要调用解决当前层相对简单问题的函数，解决当前层问题又需要调用解决下一层更简单问题的函数，周而复始，直到最底层极其简单问题的解决，一旦最底层的问题得以解决，那么回过头来解决它上一层的问题，然后是再上一层的问题，一层一层地向上，最终将解决所有各层问题。注意：在对问题划分层次时应该保证总层次数是有限的，这是在有限步骤内解决问题的必要条件。上面这种特殊的采用分治法解决问题的过程称为递归。,7.3.1 递归,Factorial(0) Factorial(n) = n×Factorial(n-1),int Factorial(int n) long Factorial(int n) if(n=1) return 1; else return n*Factorial(n-1); ,7.3.1 递归,例7.9 编写程序求斐波那契（Fibonacci）数列的第n项。 问题的提出源于兔子问题：一对兔子每两月繁殖一对兔子，设第n月兔子对数F(n)，则F(n)=F(n-1)+F(n-2)，即第n月兔子对数等于上月兔子对数加上新生兔子对数，新生兔子对数正好是前个月兔子对数，故有： F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2),long Fibonacii(int n) switch(n) case 0: return 0; case 1: return 1; default:return Fibonacii(n-1)+Fibonacii(n-2); void main() coutFibonacii(10)endl; ,7.3.2 迭代,long Factorial(int n) int Vi_1=1, Vi=0; for(int i=1; i=n; i+) Vi=i*Vi_1; Vi_1=Vi; return Vi; ,Factorial(0) Factorial(n) = n×Factorial(n-1),F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2),long Fibonacii(int n) int Vi_2=0, Vi_1=1, Vi=0; if(n=1) return 1; for(int i=2; i=n; i+) Vi=Vi_1 + Vi_2; Vi_2=Vi_1; Vi_1=Vi; return Vi; ,比较,比较,7.3.3 应用示例,例7.11 编程显示汉诺（Hanoi）塔问题的解答。,MoveTower(n-1, '1', '3', '2') 首先以右侧的针'3'作为过渡，将左侧针'1'上的n-1个盘子移动到中 间的针'2'上，于是各针上的盘子形成图a所示的状态。 MoveTo('1', '3') 将左侧针1上的最大盘子直接移动到右侧针3'上，各针上的盘子形 成图b。 MoveTower(n-1, '2', '1', '3') 以左侧针'1'作为过渡，将中间针'2'上面的盘子移动到右侧针'3' 上，从而完成了将左侧针'1'上的全部盘子移动到右侧针'3'上的操 作，这时各针上的盘子形成图c所示的状态。,a,b,c,7.3.3 应用示例,例7.12 求常系数n次多项式的值。,a0 + a1x + a2x2 + a3x3 + am-1xm-1 + anxm = a0 + x(a1 + x(a2 + x(a3 + + x(am-1 + amx),A(n-1)=an-1+xA(n) A(m)=am, nm,#include “iostream.h“ double Polynomial(double a, int n, int m, double x) if(n=m) return *(a+m); return *(a+n)+x*Polynomial(a, n+1, m, x); void main() double a=5,6,7,8; coutPolynomial(a, 0, 3, 2)endl; ,