计算机程序设计（C++）：第04章_问题求解的模块化（1）

1、0西安交通大学西安交通大学计算机教学实验中心计算机教学实验中心第4章 问题求解的模块化(1) 计算机程序设计（计算机程序设计（C+）上机指导程序调试的两种方法：程序调试的两种方法：临时增加输出语句临时增加输出语句断点设置断点设置(F9)、单步调试、单步调试(F10、F11) 调试运行调试运行(F5)与停止与停止(Shift+F5)上机指导变量观察与条件编译设置变量观察与条件编译设置View-Debug Window:Watch、Variable 观察变量观察变量Call Stack 调用栈调用栈Memory 内存内存Registers 寄存器寄存器Disassemly 反汇编反汇编宏定义与条件

2、编译宏定义与条件编译:#define、#ifdef、#ifundef、#else、#endif、 # undef条件编译的用法计算计算 #include using namespace std;#include #define DEBUGint main() int n=1;coutx;double u1=1,u2=x,u3=1,u4=1,u5=1,arcsin_x=x;cout.precision(20);dou1*=(2*n-1)*2*n;u2*=x*x;u3*=4;u4*=n*n;.)12() !(2)!2(.5 4 2 3 1 3 2)arcsin(221253?nnxnxxxxnnu

3、5+=2;u=u1*u2/u3/u4/u5;arcsin_x+=u;n+;#ifdef DEBUGcoutn=ntarcsin(x)arcsin_x1E-26);coutn=ntarcsin(x)arcsin_xendl;return 1;u*=(2n-1)*(2n-1)*x*x/2/n/(2n+1)内容提要 结构化程序设计方法结构化程序设计方法 模块化设计与函数模块化设计与函数 函数的定义函数的定义 函数的调用函数的调用 函数的声明函数的声明 嵌套函数嵌套函数 特殊函数特殊函数4结构化程序设计方法 什么是软件危机？软件开发方法落后，软件供不应求什么是软件危机？软件开发方法落后，软件供不应求

4、程序设计的新目标程序设计的新目标不再集中于充分发挥硬件的效率方面的问题不再集中于充分发挥硬件的效率方面的问题而是关注于程序结构的清晰、可读性强、易于分工合作编而是关注于程序结构的清晰、可读性强、易于分工合作编写和调试写和调试 结构化设计方法以模块化设计为中心。结构化设计方法以模块化设计为中心。主要思想：自顶向下, 逐步求精 自顶向下自顶向下 将复杂的、大的问题划分为小问题，找出问题的关键、重点将复杂的、大的问题划分为小问题，找出问题的关键、重点所在，然后用精确的思维定性、定量地去描述问题所在，然后用精确的思维定性、定量地去描述问题 逐步求精逐步求精 对一个事物的认识是一个从高层次抽象向低层次抽

5、象逐步转化和过对一个事物的认识是一个从高层次抽象向低层次抽象逐步转化和过渡的过程渡的过程, 首先一般性、抽象的，然后才是具体和详细的首先一般性、抽象的，然后才是具体和详细的 抽象思想抽象思想 在认识事物、分析和解决问题的过程中，忽略那些与当前研究目标在认识事物、分析和解决问题的过程中，忽略那些与当前研究目标不相关的部分不相关的部分, 以便将注意力集中于与当前目标相关的方面以便将注意力集中于与当前目标相关的方面 结构化结构化 不用不用goto 模块化模块化模块化设计 规模较大的程序按功能划分成若干相对独立的模块规模较大的程序按功能划分成若干相对独立的模块 每个模块由一个功能函数实现每个模块由一个

6、功能函数实现 通过函数调用将这些函数组织在一起通过函数调用将这些函数组织在一起 每个模块可以是一条语句、一段程序、一个函数等每个模块可以是一条语句、一段程序、一个函数等 模块控制流程：顺序、选择、循环模块控制流程：顺序、选择、循环 程序仅有一个入口和一个出口程序仅有一个入口和一个出口模块化设计示例计算器程序设计，功能包括：计算器程序设计，功能包括：求加、减、乘、除、开方、指数、对求加、减、乘、除、开方、指数、对数、平方等运算。数、平方等运算。功能选择菜单功能选择菜单+-*/X1/2X2exyxsincostanlogmain() add(a,b); min(a,b); int add(int

7、x,int y) return x+y;int sub(int x,int y) return x-y; fload exp(int x) return exp(x); float sin(fload x) return sin(x);结构化设计具体方法 从题目本身开始从题目本身开始, , 找出解决问题的基本思路找出解决问题的基本思路, , 将其用将其用结构化框图结构化框图( (可能是非常粗糙可能是非常粗糙) )表示。表示。对框图中的比较抽象的、用文字描述的模块进一步分对框图中的比较抽象的、用文字描述的模块进一步分析细化，结果仍用结构化框图表示析细化，结果仍用结构化框图表示将所求解问题的所有细

8、节都弄清楚后将所求解问题的所有细节都弄清楚后, , 再根据框图直再根据框图直接写出相应程序代码接写出相应程序代码例例1：验证：验证“哥德巴赫猜想哥德巴赫猜想” 17421742年法国数学爱好者哥德巴赫在给著名数学家年法国数学爱好者哥德巴赫在给著名数学家欧拉的信中提出欧拉的信中提出“哥德巴赫猜想哥德巴赫猜想”问题问题 “哥德巴赫猜想哥德巴赫猜想”：任何一个大于等于任何一个大于等于4 4的的偶数均可以表示为两个素数之和偶数均可以表示为两个素数之和 “哥德巴赫猜想哥德巴赫猜想”是数论中的一个著名难题，是数论中的一个著名难题，200200多年来无数数学家为其呕心沥血，却始终无人能多年来无数数学家为其呕

9、心沥血，却始终无人能够证明或伪证这个猜想够证明或伪证这个猜想验证哥德巴赫猜想的设计-1 求解第一步求解第一步 提出拟解决的问题：提出拟解决的问题：验证哥德巴赫猜想的正确性验证哥德巴赫猜想的正确性验证歌德巴赫猜想验证歌德巴赫猜想验证哥德巴赫猜想的设计-2 第二步：设一上限数第二步：设一上限数M M，验证从，验证从4 4到到M M的所有偶数是的所有偶数是否能被分解为两个素数之和否能被分解为两个素数之和X = 4X M 验证验证X是否能被分解是否能被分解为两个素数之和为两个素数之和X = X +2否否是是开开始始结束结束验证哥德巴赫猜想的设计-3 第三步：如何验证第三步：如何验证X X是否能被分解为

10、两个素数之和是否能被分解为两个素数之和P = 2P= X/ 2处理哥德巴赫猜想处理哥德巴赫猜想不成立的情况不成立的情况打印出打印出X的的分解情况分解情况是是否否开始开始结束结束验证验证X是否能被分解是否能被分解为两个素数之和为两个素数之和验证哥德巴赫猜想的设计-4 第四步：将第三步中三个模块进一步细第四步：将第三步中三个模块进一步细化化 “生成下一个素数生成下一个素数” ：生成下一个素数生成下一个素数P = P + 1是素数？是素数？P = P + 1否否返回素数返回素数 P验证哥德巴赫猜想的设计 经过四步分解精化，将经过四步分解精化，将“验证哥德巴赫猜想验证哥德巴赫猜想”这个这个命题已经分解

11、为计算机可以求解的数学模型了命题已经分解为计算机可以求解的数学模型了 剩下的问题就是编程求解了。如何编程是程序设计剩下的问题就是编程求解了。如何编程是程序设计课程要解决的问题。课程要解决的问题。哥德巴赫猜想程序/主函数主函数 验证哥德巴赫猜想验证哥德巴赫猜想 void main(void) int x;int p1,p2;x = 4; /* 从从4到到 M 开始验证开始验证 */while(x=M) /isPrimeSum(x); /验证验证X是否能被分解为两个素数之和是否能被分解为两个素数之和if(isPrimeSum(x,p1,p2)=1)cout素数素数: x=p1+p2endl;els

12、ecout哥德巴赫猜想不成立哥德巴赫猜想不成立 x不能分解为素数值和不能分解为素数值和endl;x = x+2; / 验证下一个偶数验证下一个偶数 /验证是否能分解成两个素数值和验证是否能分解成两个素数值和void isPrimeSum(int x)int p=2;int PrimeListM; CreatPrimeList(PrimeList); /*生成素数表生成素数表 */while(px/2)cout哥德巴赫猜想不成立哥德巴赫猜想不成立endl;/哥德巴赫猜想不成立的情况哥德巴赫猜想不成立的情况elsecout偶数偶数: x=p+x-py?x:y; return xy?x:y; voi

13、d show(char text) / void show(char text) / 文字显示文字显示 couttextendl; couttextr;cinr;double y=area(double r); / double y=area(double r); / 圆面积圆面积int x;int x;int y;int y;cinxy;cinxy;int z=max(x, y); / int z=max(x, y); / 最大值最大值char text20;char text20;cin.getline(text,20);cin.getline(text,20);show(text); /

14、 show(text); / 文字显示文字显示函数声明 函数（原型）声明函数（原型）声明 当函数的定义位于调用之后时，须提前对函数进行说明当函数的定义位于调用之后时，须提前对函数进行说明，以便通知编译器，以便通知编译器 函数声明的一般格式：函数声明的一般格式： 返回类型返回类型 函数名函数名 ( 形式参数表形式参数表 );函数声明举例double area(double r); / double area(double r); / 圆面积圆面积int max(int x, int y); / int max(int x, int y); / 最大值最大值void show(char text)

15、; / void show(char text); / 文字显示文字显示值传递 将实参的值依次传递给对应的形参，形参变量只有将实参的值依次传递给对应的形参，形参变量只有在发生函数调用时才分配内存单元用来接受由实参在发生函数调用时才分配内存单元用来接受由实参传过来的数据。传过来的数据。 实参与形参各占不同的单元，当调用结束后，形参实参与形参各占不同的单元，当调用结束后，形参所在内存单元被释放，而实参仍保留原值。所在内存单元被释放，而实参仍保留原值。举例：交换两个变量的值void swap(int x,int y) int z; z=x; x=y; y=z;int main() int a=5,b

16、=10; couta=a,b=bendl; swap(a,b); couta=a,b=b; return 1;结论：变量结论：变量a a和和b b的值并没有交换。的值并没有交换。引用传递 引用引用一个变量可以有多个名字，后一个名字叫一个变量可以有多个名字，后一个名字叫“引用引用”。int i;int &refi = i; 引用传递引用传递 如果函数的形参是引用，在函数调用时，形参变量与如果函数的形参是引用，在函数调用时，形参变量与实参变量实际表示的是同一内存单元。实参变量实际表示的是同一内存单元。 使用引用传递可以在被调函数中改变实参的值。使用引用传递可以在被调函数中改变实参的值。举例：交换两

17、个变量的值 void swap(int &x, int &y) int tmp = x;x = y;y = tmp;int main() int a=5,b=10; couta=a,b=bendl; swap(a,b); couta=a,b=b; return 1;数组作为函数参数 函数定义函数定义double max(double a,int N) 函数调用函数调用int main() double a100=1,2,3,34,4,4,5,6,66,7; coutxyz;int w;w=max(x,max(y,z); 示例示例2 2已知已知x值值 函数函数h(x)=x3/2， g(x)=ln

18、 (x)和和 f(x)=1/x+x2+3，编写计算编写计算y=f(g(h(x)值的程序。值的程序。 特殊函数 函数可以无返回值函数可以无返回值 函数可以无参数函数可以无参数 函数可以有缺省值参数函数可以有缺省值参数 主函数主函数函数可以没有返回值打印生日卡函数打印生日卡函数void birthdaycard(char name1, char name2)/char name141, name241;/cout endl name1;/cout endl name2;cout endl = endl;cout My dear name1 , endl;cout Happy birthday to

19、 you! endl;cout yours， endl;cout name2 endl;cout = endl;/ return 0; 没返回值，不要有没返回值，不要有return 打印数组元素函数打印数组元素函数void printarray(int a, int N) for(int i=1;i=N;i+)coutai-1t;if(i%5=0) coutendl;函数可以没有参数 例：打印九九乘法表例：打印九九乘法表void multiplicationTable(void) /两个两个void,无参数，无返回值无参数，无返回值int i, j;for(i=1; i10; i+)for(j

20、=1; j=i; j+)cout j * i =i*j t;cout endl;/return 0; 没返回值，不要有没返回值，不要有return 主函数 void main()void main() void main(int argc,char void main(int argc,char* *argv)argv) void main(int argc,char void main(int argc,char* *argv,char argv,char * *env)env) int main()int main() int main(int argc,char int main(int

21、 argc,char* *argv)argv) int main(int argc,char int main(int argc,char* *argv,char argv,char * *env)env)常用函数介绍1（补充）42 double exp(double x); Ex double log(double x); lnx double log10(double x); lgx double pow(double x, double y); xy double sqrt(double x); x double ceil(double x); x的四舍五入的四舍五入 double fl

22、oor(double x); x的四舍五入的四舍五入 double fabs(double x); |x| double sin(double x); sin(x) 弧度弧度 double asin(double x); arcsin(x) |x|=1常用函数介绍2（补充）43 int rand(void); 0-32727范围的随机数范围的随机数void srand(unsigned int seed); 随机数种子设定随机数种子设定int abs(int n); |x|int atoi(const char* s); 字符串转整数字符串转整数char *itoa(int value, ch

23、ar *string, int radix); 进制转换，其中进制转换，其中radixradix2,362,36常用函数介绍3（补充）44 time_t time(time_t* tp); 取得当前时间取得当前时间double difftime(time_t time2, time_t time1); 两个时间之差两个时间之差常用函数介绍4（补充）45 strlen 字符串长度字符串长度strcpy 拷贝字符串拷贝字符串strcat 追加字符串追加字符串strcmp(stricmp) 比较字符串比较字符串strupr 转换为大写转换为大写strlwr 转换为小写转换为小写strstr 查找字符

24、串查找字符串1. 字符串复制函数strcpy 格式：格式： strcpy (字符数组名，字符串字符数组名，字符串) 作用：作用： 将字符串复制到字符数组中将字符串复制到字符数组中 字符串可以是字符数组名、字符串常量、指针变量字符串可以是字符数组名、字符串常量、指针变量 示例：示例： strcpy(str2,str1); strcpy(str1,Friday);2字符串连接函数strcat格式：格式：strcat(strcat(字符串字符串1 1，字符串，字符串2)2)作用：将字符串作用：将字符串2 2连接到字符串连接到字符串1 1之后之后#include #include using name

25、space std;int main() char str120=computer; / 第第1个字符串保存在个字符串保存在str1中中 char str2=room; / 第第2个字符串保存在个字符串保存在str2中中 strcat(str1,-); / 第第1个字符串和个字符串和-连接连接 strcat(str1,str2); / 连接后的第连接后的第1个字符串和第个字符串和第2个连接个连接 coutstr1; return 1;3字符串比较函数strcmp 格式：格式：strcmp (strcmp (字符串字符串1 1，字符串，字符串2)2) 作用：比较两个字符串的大小并返回一个整数。作

26、用：比较两个字符串的大小并返回一个整数。 两个字符串比较过程：两个字符串比较过程： 两个字符串自左到右逐个字符比较，即先比较两个字符串的第两个字符串自左到右逐个字符比较，即先比较两个字符串的第0个个字符，如果相等，再比较这两个字符串的第字符，如果相等，再比较这两个字符串的第1个字符，个字符，参与比参与比较的是这两个字符对应的较的是这两个字符对应的ASCII码。码。 比较过程中，遇到对应字符不相等或遇到某个字符串先到结束标志比较过程中，遇到对应字符不相等或遇到某个字符串先到结束标志0时，比较结束，如果两个字符串长度相等，并且对应位置上的时，比较结束，如果两个字符串长度相等，并且对应位置上的字符都

27、相同，则比较的结果是两个字符串相等。字符都相同，则比较的结果是两个字符串相等。 函数值的规定：函数值的规定： （1）如果两个字符串相等，函数值为）如果两个字符串相等，函数值为0； （2）如果字符串）如果字符串1大于字符串大于字符串2，函数值为，函数值为1； （3）如果字符串）如果字符串1小于字符串小于字符串2，函数值为，函数值为-1。字符串比较示例一： coutstrcmp(aaa,aaaa)endl; coutstrcmp(aaa,aaaa)endl; / 字符字符0a，结果为，结果为 -1 coutstrcmp(1a,aa)endl; coutstrcmp(1a,aa)endl; / 字符

28、字符1a，结果为，结果为 -1 coutstrcmp(Abc,abc)endl; coutstrcmp(Abc,abc)endl; / 字符字符Aa，结果为，结果为 -1字符串比较示例二： 定义：定义：char a5=1234,b5=4321;char a5=1234,b5=4321; coutstrcmp(a,1234)endl; coutstrcmp(a,1234)endl; / 两个字符串相等，结果为两个字符串相等，结果为0 coutstrcmp(a,123)endl; coutstrcmp(a,123)0，结果为，结果为 1 coutstrcmp(a,b)endl; coutstrcm

29、p(a,b)endl; / 字符字符14，结果为，结果为 -1 4 4计算字符串长度函数计算字符串长度函数strlenstrlen 格式：格式：strlen(字符串字符串) 作用：返回字符串长度，即字符串中包含的字符个数。作用：返回字符串长度，即字符串中包含的字符个数。不包括结束标志不包括结束标志0。 5. 5. 字母变小写函数字母变小写函数strlwrstrlwr 格式：格式：strlwr(字符串字符串) 作用：将字符串中的大写字母转换成小写字母。作用：将字符串中的大写字母转换成小写字母。 6 6字母变大写函数字母变大写函数struprstrupr 格式：格式：strupr(字符串字符串)

30、作用：将字符串中的小写字符母转换为大写字母。作用：将字符串中的小写字符母转换为大写字母。例1 计算圆的面积 定义两个函数，根据半径计算圆的面积和周长。定义两个函数，根据半径计算圆的面积和周长。 在主函数中，输入一个圆的半径值，然后对输入的在主函数中，输入一个圆的半径值，然后对输入的半径值进行判断，当该值大于零时，调用函数计算半径值进行判断，当该值大于零时，调用函数计算这个圆的面积和周长，并输出计算的结果；否则显这个圆的面积和周长，并输出计算的结果；否则显示示“输入错误输入错误”的信息。的信息。【源程序】#include using namespace std; double area(doub

31、le r); / 声明计算面积的函数声明计算面积的函数area()double len(double r); / 声明计算周长的函数声明计算周长的函数len()void main() double r; / 定义变量定义变量r保存圆的半径保存圆的半径coutr;if(r0) cout面积面积=area(r)endl; / 调用函数调用函数area()计算面积计算面积cout周长周长=len(r)endl; / 调用函数调用函数len()计算周长计算周长elsecout输入错误输入错误endl;double area(double r) / 定义计算面积的函数定义计算面积的函数area retu

32、rn 3.1416*r*r; / 计算并返回圆的面积计算并返回圆的面积double len(double r) / 定义计算周长的函数定义计算周长的函数len return 2*3.1416*r; / 计算并返回圆的周长计算并返回圆的周长例2 打印100010000之间的回文数。 所谓回文数是指其各位数字左右对称的整数，所谓回文数是指其各位数字左右对称的整数，例如例如1232112321、789987789987、1 1等。等。 题目要求：四位数中的回文数题目要求：四位数中的回文数 算法算法1 1：对对n=1000,9999 分别取出分别取出n的个、十、百、千位。的个、十、百、千位。 如果个位

33、如果个位=千位，且十位千位，且十位=百位，则该数是回文百位，则该数是回文数。数。回文数源程序#include using namespace std; bool ishuiwen(int n)int a,b,c,d;a=n%10;n=n/10;b=n%10;n=n/10;c=n%10;n=n/10;d=n%10;if(a=d & c=b) return 1;return 0;int main() / 分别调用分别调用10次次func( ) 函函数数for(int i=1000;i10000;i+)if(ishuiwen(i)coutiendl;return 0;如果一个数位数不定如何判断 如果

34、一个数，位数不定，如何判断是否回文？如果一个数，位数不定，如何判断是否回文？ 如果该数是如果该数是abcdeabcde，如何判断？，如何判断？ 可以判别可以判别 edcba=abced ?edcba=abced ?（1）分离各位数）分离各位数 k=n ; /n=14535 while(k!=0) a=k%10; k=k/10; （2）构造逆序的数）构造逆序的数m=e;m=10m+d;m=10m+c;m=10m+b;m=10m+a若若m=14535，abcde是万位是万位到个位，到个位，m=？/ 判断是否回文数函数bool Ispalindrome(int n) int k, m=0;k=n;w

35、hile(k)m=m*10+k%10; /第第1次，次，k%10是个位是个位k=k/10;return (m=n);例3 找出2200之间的所有孪生素数。 孪生素数孪生素数 指间隔为指间隔为 2 的相邻素数，例如的相邻素数，例如3和和5，5和和7,其中最小的孪其中最小的孪生素数是生素数是3和和5。 解决方法解决方法 编写一个函数用来判断某个整数是否为素数，该函数的编写一个函数用来判断某个整数是否为素数，该函数的类型为类型为bool型，如果判断结果为素数则返回型，如果判断结果为素数则返回true,否则返否则返回回false 在主函数中调用该函数，判断某个整数在主函数中调用该函数，判断某个整数i和

36、和i+2是否同时为是否同时为素数。素数。 【源程序】#include #include using namespace std;using namespace std;bool isprime(int n) bool isprime(int n) / 判断某个整数是否为素数的函数判断某个整数是否为素数的函数 int i; int i; for(i=2;in;i+) for(i=2;in;i+) if(n%i=0) if(n%i=0) return false;return false;/ 找到找到n的某个因子后返回的某个因子后返回false值值 return true; return true

37、; / 没有找到没有找到n的因子时返回的因子时返回true值值 int main() int i; cout2200之间的孪生素数如下：之间的孪生素数如下：endl; for(i=2;i200;i+) if(isprime(i) & isprime(i+2) /同时判断同时判断i和和i+2是否同时为素数是否同时为素数couti,i+2endl; return 1;例4 冒泡法排序 编写函数，用冒泡法对一组整数进行从小到大的升编写函数，用冒泡法对一组整数进行从小到大的升序排序。序排序。 对数组中的数据进行排序，就是重新调整每个元素对数组中的数据进行排序，就是重新调整每个元素的位置，保证元素的值按

38、下标的顺序依次递增（升的位置，保证元素的值按下标的顺序依次递增（升序）或依次递减（降序）。序）或依次递减（降序）。冒泡法算法描述 对对n n个数进行个数进行n-1n-1轮的冒泡比较：轮的冒泡比较：第一轮将最大的元素沉到最底部，即放到数组的最第一轮将最大的元素沉到最底部，即放到数组的最后一个位置；后一个位置；第二轮将剩余的第二轮将剩余的n-1个数中的最大数即个数中的最大数即n个数中的次个数中的次最大值下沉；最大值下沉；依此类推，每一轮都将剩余的数中的最大数下沉；依此类推，每一轮都将剩余的数中的最大数下沉；当进行当进行n-1轮之后，最大的轮之后，最大的n-1个沉下去，最上面自个沉下去，最上面自然就

39、是最小的数，整个排序就此完成然就是最小的数，整个排序就此完成 。【源程序】#include #include using namespace std;using namespace std;void sort(int b,int n) / void sort(int b,int n) / 冒泡法排序的函冒泡法排序的函数数 int i,j,t;int i,j,t;for (j=0; jn-1;j+) for (j=0; jn-1;j+) / 外循环控制比较轮次为个数减外循环控制比较轮次为个数减1for (i=0; in-j;i+) for (i=0; ibi+1) if (bibi+1) / 相

40、邻两个进行比较相邻两个进行比较t=bi;bi=bi+1;bi+1=t; /交换两个数的位置交换两个数的位置void print(int b,int n) / 该函数顺序显示输出数组元素该函数顺序显示输出数组元素 int i;for (i=0;in;i+) coutbi ;coutendl;int main() int a10=9,4,8,12,65,-76,1,0,100,-45; / 定义并初始化一维数组定义并初始化一维数组cout排序前排序前:; print(a,10); /调用调用print函数显示排序前数组元素函数显示排序前数组元素sort(a,10); /调用调用sort函数对数组元

41、素进行排序函数对数组元素进行排序 cout排序后排序后:; print(a,10); /调用调用print函数显示排序后数组元素函数显示排序后数组元素return 1;例5 折半查找法 折半查找法用来在一个已经排好顺序的数组中查找某个折半查找法用来在一个已经排好顺序的数组中查找某个数是否存在，该数称为查找关键字数是否存在，该数称为查找关键字key。 算法算法 （1）将）将key与数组的中间位置的元素进行比较，如果相与数组的中间位置的元素进行比较，如果相等，表示找到，则返回下标值，即位置，查找结束；等，表示找到，则返回下标值，即位置，查找结束； （2）如果不相等，则缩小查找范围，在新的范围内继续

42、）如果不相等，则缩小查找范围，在新的范围内继续查找：查找： 如果如果key大于中间元素的值，则新的查找范围缩小为后半大于中间元素的值，则新的查找范围缩小为后半个数组，否则新的查找范围为前半个数组；个数组，否则新的查找范围为前半个数组； （3）重复以上（）重复以上（1）（2）不断缩小查找范围，直到找）不断缩小查找范围，直到找到返回位置或没找到时返回到返回位置或没找到时返回1标志。标志。 【源程序】 #include#includeusing namespace std; int search(int a,int n,int key) / n为数组长度，为数组长度，key为查找关键字为查找关键字

43、int low,high,mid; / low和和high为区间范围为区间范围low=0;high=n-1;while(lowamid)/新范围在后半部分新范围在后半部分low=mid+1;else/新范围在前半部分新范围在前半部分high=mid-1;return -1;int main() int a=1,3,6,7,9,12,13,15,22,43;int k,n;coutn; k=search(a,10,n);if(k=0)coutn在数组中的位置是在数组中的位置是kendl;elsecout要想找的数据在数组中不存在要想找的数据在数组中不存在endl;return 1; 例6 实现矩

44、阵相乘运算 算法说明：算法说明： 矩阵矩阵A A（LxNLxN）和矩阵）和矩阵B B（NxMNxM）相乘。）相乘。 A A是是L L行、行、N N列；列；B B是是N N行、行、M M列。列。 要求要求:A:A的列数和的列数和B B的行数必须相同。的行数必须相同。NjLiBACMkkjikij,.,2 , 1;,.,2 , 1,1算法用两重循环实现对用两重循环实现对ijij的求值的求值: : for(i=0; il; i=i+1) for(i=0; il; i=i+1) for(j=0; in; j=j+1) for(j=0; in; j=j+1) 求求ij;ij;其中其中“求求ij”ij”又

45、可以细化为又可以细化为: : ij = 0;ij = 0; for(k=0; km; k=k+1) for(k=0; km; k=k+1) ij ij ij+ij+ikikkjkj 源程序#include #include using namespace std;using namespace std;void matrix_multi(void matrix_multi(double a, double b, double c,double a, double b, double c, int l, int m, int n)int l, int m, int n) int i, j, k;

46、int i, j, k;for(i=0; il; i+)for(i=0; il; i+)for(j=0; jn; j+)for(j=0; jn; j+) cici* *n+j = 0;n+j = 0; for(k=0; km; k+)for(k=0; km; k+) cici* *n+j = n+j = cici* *n+j+ain+j+ai* *m+km+k* *bkbk* *n+j;n+j; / 测试上述矩阵相乘函数的主程序int main()double a20= 1.0, 3.0,-2.0, 0.0, 4.0,-2.0,-1.0, 5.0,-7.0, 2.0,0.0, 8.0, 4.0

47、, 1.0,-5.0,3.0,-3.0, 2.0,-4.0, 1.0;double b15= 4.0, 5.0,-1.0,2.0,-2.0, 6.0,7.0, 8.0, 1.0,0.0, 3.0,-5.0,9.0, 8.0,-6.0;double c12;matrix_multi(a, b, c, 4, 5, 3);cout The result is c= endl;for(int i=0; i4; i+)for(int j=0; j3; j+)cout ci*3+j ;cout endl;return 0;例7 用二分迭代法求方程2x3-4x2+3x-6=0在(-10,10)之间的根。 用

48、二分法求方程根的前提是方程用二分法求方程根的前提是方程f(x)=0f(x)=0有两个粗略的解有两个粗略的解x1 x1 和和x0 x0 ，这就是初值，对初值要求：，这就是初值，对初值要求：（1）f(x1)和和f(x0)符号相反；符号相反；（2）f(x) 在（在（x1，x0）内单调升或单调降。）内单调升或单调降。 【算法描述算法描述】（1）取两点区间的中点：）取两点区间的中点：x=（x1+x0）/2，这就是迭代公式。，这就是迭代公式。（2）测试中点的函数值）测试中点的函数值f(x)是否满足精度要求，这是迭代条件，若满是否满足精度要求，这是迭代条件，若满足则用足则用x作为方程的近似根，迭代过程结束；作为方程的近似根，迭代过程结束；（3）如果不满足精度，则用）如果不满足精度，则用x与与 x1 和和x0 中的一个组成新的区间，重中的一个组成新的区间，重复过程（复过程（2）不断地缩小区间。）不断地缩小区间。在组成新区间时，如果中点的函数值与在组成新区间时，如果中点的函数值与x1 点的函数值同号，则新区间点的函数值同号，则新区间为（为（x，x0），否则为（），否则为（x1，x）。）。 【源程序】#include#include#include#includeusin