9299.net
大学生考试网 让学习变简单
赞助商链接
当前位置:首页 >> 数学 >>

06习题课—期中测试题2013+上机作业+折半查找法

06习题课—期中测试题2013+上机作业+折半查找法


C++程序设计
主讲:王金湘

wangjx@seu.edu.cn

期中测试题目
3.以下属于C++语言的基本类型是 (3) A) ACF B) ABC C) ACD D) CDF A. 整型 B. 数组型 C. 字符型 D. 构造型 E. 实形 F. 空类型 7.设有定义 int a,b; 执行语句 b=(a=2+3,a*4),a+5; 后,a和b的值是_(7)_ A) 10 10 B) 20 25 C) 5 20 D) 5 25 8 . 有说明:int m=4;执行语句 m+=m*=m-=m/=m;后,m的值是: (8) A) 0 B) 1 C) 8 第六章 D) 16 2 数组
2014-6-22

期中测试题目
10.有说明:int x=1,y=1,z=1,k;执行语句 k=x++||++y&&++z;后,变量x、y、z、k的 值依次是: (10) A) 1 2 2 1 B) 1 2 1 0 C) 1 1 2 0 D) 2 1 1 1 12. 设有变量定义int x=100,y=1; 若执行语 句:x=y>1? ++x=100: y=x--;则变量x,y的 值为_(12)_ A) 101, 99 B)100, 100 C)101, 1 D)99, 100
2014-6-22 习题课 3

期中测试题目
14. for(x=0,y=0;y!=250||x<4;x++) y+=50; 其循环体共执行 (14) 次。 A. 5 B. 4 C. 3 D. 2
16 设有说明 int x=1,y=1,z=1,c; 执行语句 c=--x&&--y||--z; 后,x、y、z的值分别为 (16) 。 A.0、1、1 B. 0、1、0 C. 1、0、1 D. 0、0、1
2014-6-22 习题课 4

期中测试题目
19. 设有说明语句:int a=1,b=0;则执行以下 语句后,输出为 (19) A)**0** B)**0**\**2** C)**0**\**1**\**2** D)有语法错误
switch(a) { case 1: switch(b) {case 0: cout<<"**0**"<<'\\';break; case 1: cout<<"**1**"<<'\\';break; } case 2: cout<<"**2**"<<'\n'; break; }
2014-6-22 习题课

5

期中测试题目
填空题: 6. 在C++语言中,字符串常量 23 “It?s a piece of cake.\n”的长度是 (6) 。 8.对于嵌套的if…else语句,C++语法规定 else总是与 (8)匹配。最近的未配对的if 9.若x为int 型变量,则执行语句 -60 x=6; x+=x- =x*x;后,x的值为 (9) 。

2014-6-22

习题课

6

期中测试题目——阅读程序
#include<iostream.h> 问题1.运行程序时,若输入数据’a?,

输出是_(1)_ error \n.....。 void main( ) { char grade; 问题2.如果输入数据是’B?,输出是 cin>>grade; _(2)_ 70~84 60~69\n….. while(grade!=?&?) switch(grade) { case 'A': cout<<"85~100\t"; case 'B': cout<<"70~84\t "; case 'C': cout<<"60~69\n ";break; case 'D': cout<<"<60\t "; default: cout<<"error\n "; } }
2014-6-22 习题课 7

期中测试题目——阅读程序
#include<iostream.h> 问题3.如果输入数据是’D?,输出

void main( ) 是_(3)_ 60 error\n... { char grade; 问题4.该程序有一个循环语句,它 cin>>grade; 的循环体是_(4)_语句 开关 while(grade!=?&?) switch(grade) { case 'A': cout<<"85~100\t"; case 'B': cout<<"70~84\t "; case 'C': cout<<"60~69\n ";break; case 'D': cout<<"<60\t "; default: cout<<"error\n "; } }
2014-6-22 习题课 8

期中测试题目——阅读程序
#include<iostream.h> 问题5.该程序的算法有错误,这个错误

void main( ) 导致_(5)_ D { char grade; (A) 程序不能运行 (B) 不能输出结果 (C) cin>>grade; 不能做循环 (D) 不能结束循环 while(grade!=?&?) switch(grade) { case 'A': cout<<"85~100\t"; case 'B': cout<<"70~84\t "; case 'C': cout<<"60~69\n ";break; case 'D': cout<<"<60\t "; default: cout<<"error\n "; } }
2014-6-22 习题课 9

期中测试题目——阅读程序
#include<iostream.h>

问题3:该程序有两个错误,分别发生在 void main( ) ( 结构语句及 结构语句中。 { char grade; 开关语句,和循环语句 cin>>grade; while(grade!=?&?) switch(grade) { case 'A': cout<<"85~100\t"; case 'B': cout<<"70~84\t "; case 'C': cout<<"60~69\n "; case 'D': cout<<"<60\t "; default: cout<<"error\n "; } }
2014-6-22 习题课 10

期中测试题目——阅读程序
#include<iostream.h> 为避免产生“死循环”,在保持原程序基本

不变的前提下,应在 的 语句之后 void main( ) { char grade; 插入语句 。 循环语句 switch cin>>grade; cin>>grade; while(grade!=?&?) switch(grade) { case 'A': cout<<"85~100\t"; case 'B': cout<<"70~84\t "; case 'C': cout<<"60~69\n "; case 'D': cout<<"<60\t "; default: cout<<"error\n "; } }
2014-6-22 习题课 11

期中测试题目——阅读程序
void main() { char ch; int sum=0,j=0; 执行程序时,如果依次输入 以下数据: cin.get(ch); This is a test. if(ch>=?A?&& ch<=?Z?) 输出结果是: _(10)_ 114 { while(ch!=?.?) 问题2:这个程序可用来统计 { if(ch==? ?) j++; 一个英文句子中的单词个数 else sum++; 和_(11)_个数,其中sum表 cin.get(ch); 示_(12)_个数,j表示_(13)_ } 个数; (11)字母(12)字母 j++; (13)单词 } else cout<<”fall short of request”; if(sum!=0) cout<<sum<<j; }014-6-22 12 习题课 2

期中测试题目——阅读程序
#include<iostream.h> void main() { int m,n,r,t; cin>>m>>n; if(m<n) {t=m;m=n;n=t;} r=m%n; for(;r!=0;m=n,n=r,r=m%n); cout<<”n=”<<n<<?\n?; } 问题2:该程序有一个 循环语句,它的循环 体是_(15)_语句 空 问题3:循环参数中有 两个表达式,一个是 关系表达式,另一个 是_(16)_表达式
逗号表达式/赋值表达式

2014-6-22

习题课

13

期中测试题目——阅读程序
#include<iostream.h> int main() { char a='A',b='F',c='\t',d=65+6; cout<<a<<b<<c<<d<<'\n'; cout<<char(a+2)<<c<<char(b-1)<<endl; ////A cout<<char(d-1)<<'\\'<<char(a+1)<<'\n'; return 0; } 一共输出_(17) 行,输出结果的第一行为 (18) ,第二行为

19) ,第三行为 (20) 。A行改为 cout<<int(a+2)<<c<<int(b-1)<<endl;后,输出为 21)。

(17)3 (18)AF G (19) C E(20)F\B (21) 67 69
2014-6-22 习题课 14

期中测试题目——阅读程序
int y=10; void print(int m){ cout<<m%10<<','<<m/10%10<<','<<m/100; } void print(int x, int y){ cout<<x%10<<(x-x%y)/y<<endl; cout<<(x%::y)*y; } void main(){ int a=135, b=8642 ; print(a); cout<<endl; print(b, 1000); cout<<endl; }

一共输出3行(21)5,3,1 (22)28 (23) 2000
2014-6-22 习题课 15

期中测试题目——阅读程序
int i=2,j=3; int f(int a,int b) { int c=0; static int d=3; d++; if(a>b) c=1; else if (a==b) c=0; else c=-1; i=i+1; return (c+d); } void main() { int p; p=f(i,j); cout<<i<<','<<j<<','<<p<<endl; i=i+1; p=f(i,j); cout<<i<<?,?<<j<<?,?<<p<<endl; i=i+1; p=f(i,j); cout<<i<<','<<j<<','<<p<<endl; }

一共输出3行(24)3,3,3 (25)5,3,6 (26) 7,3,7
2014-6-22 习题课 16

期中测试题目——阅读程序
void sub(int n){ int m, r ; if(n==0) {cout<<"**"<<endl; return ; } m=n/10; r=n%10; sub(m); cout<<"**"<<r; } void main( ){ int a=123; sub(a); cout<<"++"<<endl; }

一共输出3行(27)** (28)**1**2**3++
2014-6-22 习题课 17

期中测试题目——完善程序
1. 下列程序用来判断输入的整数number是否为素数(质数)。 当number为素数时,输出字符串yes,否则输出no。程序中用flag 来标志number是否为素数。

#include (1) <iostream.h> void main() flag { int i,k,number, (2) ; cout<<"Input data: "; cin>>number; flag=1; i=2; k=number/2 ; while(flag&& (3) ) i<=k i++ if(number%i ) (4) ; else (5) ; flag=0 cout<<"number="<<number; if(flag)cout<<" (6) "; yes else cout<<" (7) "; no }
2014-6-22 习题课 18

期中测试题目——完善程序
以下程序输入一个在1~10之间(包括1和10)的数 void main() { int val; do { cout<<"请输入一个在1~10之间的数:"; cin>>val; } while( (11) ); val<1||val>10 cout<<"您输入的数是 "<<val<<endl; }
?
2014-6-22 习题课 19

期中测试题目——完善程序
以下程序求?。先利用公式求出?/4的值,然后求?值,公式为: (要求:求解?/4时,当某项绝对值小于10-8表示达到求解精度) (提示:求解x值绝对值可调用库函数 fabs(x)) ? 1 1 1

void main() 0 { double s= (12) , x= (13) ; 1 long k= (14) ; 1 int sign = (15) ; 1 while( (16) ) fabs(x)>0.00000001 { s+= (17) ; x k+= (18); 2 sign*= (19) ; -1 x=sign/double(k); } s*=4; cout<<"PI="<<s<<endl; } 习题课
2014-6-22

=1- + - ? ... 4 3 5 7

20

期中测试题目——完善程序
int prime(int n){ for(int m=2; m<=sqrt(n); m++) if( (20) ) n%m==0 return 0; (21) return 1 ; } void main(){ n<51 for(int n=4; (22) ;n+=2){ for(int a=2; a<=n/2; a++){ prime(n-a) if( prime(a) && (23) ){ cout<<n<<'='<<a<<'+'<<na<<endl; break; }}}}
2014-6-22 习题课 21

按要求写出一个程序判断一个整数n是否为 11的倍数。
multiple11(int n) //递归实现 { static int sum,i=1; 将静态变量重新初始化 int flag; sum+=n%10*i,i*=-1; if (n/10) return multiple11(n/10); else { flag=sum%11==0; sum=0,i=1; return flag;} }
void main() { cout<<"1000以内所有11的倍数的数为:"<<endl; for(int i=1,k=0;i<1001;i++) if (multiple11(i)) { cout<<i<<'\t'; if (++k%5==0) cout<<endl; } } 22 习题课 2014-6-22

第10周上机题1
#include <iostream.h> #define N 5 // 可用宏定义一个常量 int check(int ); void main() { int a[N],b[N],count=0; //数组长度必须是常量表达式 cout<<"输入"<<N<<"个整数:"<<endl; for(int i=0;i<N; i++) cin>>a[i]; for(i=0;i<N; i++) if(check(a[i])) b[i]=1,count++; else b[i]=0; cout<<"输入的"<<N<<"个数中有 "<<count<<"个数高位与 低位相同。"<<endl; for(i=0;i<N; i++) cout<<b[i]<<'\t'; cout<<endl; } 2014-6-22 23 第六章 数组

第10周上机题1
int check(int m) #include <iostream.h> { int high,low; #define N 5 // 可用宏定义一个常量 low=m%10; int check(int); while(m>=10) m/=10; void main() high=m; { int a[N],b[N],count=0; //数组长度必须是常量表达式 return(!(high-low)); cout<<"输入"<<N<<"个整数:"<<endl; } for(int i=0;i<N; i++) cin>>a[i]; for(i=0;i<N; i++) if(check(a[i])) b[i]=1,count++; else b[i]=0; cout<<"输入的"<<N<<"个数中有 "<<count<<"个数高位与 低位相同。"<<endl; for(i=0;i<N; i++) cout<<b[i]<<'\t'; cout<<endl; } 2014-6-22 24 第六章 数组

第9周上机题4
#include <iostream.h> int sum(int [ ][4]); void trans(int [ ][4]); void output(int [ ][4]); void input(int [ ][4]); void main( ) { int a[4][4],sum1; cout<<"请输入一个4×4矩阵:"<<endl; input(a); cout<<"输入的矩阵是:"<<endl; output(a); sum1=sum(a); trans(a); cout<<"矩阵对角线之和是:"<<sum1<<endl; cout<<"矩阵转置的结果是:"<<endl; output(a); 第六章 数组 2014-6-22 }

25

第9周上机题4
#include <iostream.h> int sum(int [ ][4]); void input(int a[ ][4]) void trans(int [ ][4]); { for(int i=0;i<4;i++) void output(int [ ][4]); for(int j=0;j<4;j++) void input(int [ ][4]); cin>>a[i][j]; void main( ) } { int a[4][4],sum1; cout<<"请输入一个4×4矩阵:"<<endl; input(a); 如果实参、形参是二维 cout<<"输入的矩阵是:"<<endl; 数组,则形参可以省略 output(a); 第一维,不可省略第二 维,且第二维必须与实 sum1=sum(a); 参中的维数相等 trans(a); cout<<"矩阵对角线之和是:"<<sum1<<endl; 用数组名作函数参数,应在主调函数和 cout<<"矩阵转置的结果是: "<<endl; 被调函数中分别定义数组,且类型一致 output(a); 26 第六章 数组 2014-6-22 }

第9周上机题4
#include <iostream.h> int sum(int [ ][4]); void output(int a[][4]) void trans(int [ ][4]); { for(int i=0;i<4;i++) void output(int [ ][4]); { for(int j=0;j<4;j++) void input(int [ ][4]); cout<<a[i][j]<<'\t'; void main( ) cout<<endl; { int a[4][4],sum1; } cout<<"请输入一个4×4矩阵: } "<<endl; input(a); cout<<"输入的矩阵是:"<<endl; output(a); sum1=sum(a); trans(a); cout<<"矩阵对角线之和是:"<<sum1<<endl; cout<<"矩阵转置的结果是:"<<endl; output(a); 27 第六章 数组 2014-6-22 }

第9周上机题4
#include <iostream.h> int sum (int b[ ][4]) int sum(int [ ][4]); { int sum1=0; 形参 void trans(int [ ][4]); for(int i=0;i<4;i++) void output(int [ ][4]); for(int j=0;j<4;j++) void input(int [ ][4]); if(i==j||3-i==j) void main( ) sum1+=b[i][j]; { int a[4][4],sum1; return sum1; cout<<"请输入一个4×4矩阵: } "<<endl; 函数值 input(a); cout<<"输入的矩阵是:"<<endl; output(a); 数组b与数组a共 sum1=sum(a); 用一段内存 trans(a); 实参 cout<<"矩阵对角线之和是:"<<sum1<<endl; cout<<"矩阵转置的结果是:"<<endl; output(a); 28 第六章 数组 2014-6-22 }

第9周上机题4
#include <iostream.h> void trans(int a[ ][4]) int sum(int [ ][4]); { int t; void trans(int [ ][4]); for(int i=0;i<4;i++) void output(int [ ][4]); for(int j=i;j<4;j++) void input(int [ ][4]); { t=a[i][j]; void main( ) a[i][j]=a[j][i]; { int a[4][4],sum1; a[j][i]=t; cout<<"请输入一个4×4矩阵:"<<endl; } input(a); } cout<<"输入的矩阵是:"<<endl; output(a); sum1=sum(a); trans(a); cout<<"矩阵对角线之和是:"<<sum1<<endl; cout<<"矩阵转置的结果是:"<<endl; output(a); 第六章 数组 2014-6-22 }

29

10周上机题3
编写一个程序,处理某班学生3门课程(语 文、数学和英语)的成绩。 ① 先输入学生人数(最多为50个人); ② 再调用一个函数按编号从小到大的顺序依 次输入学生成绩; ③ 然后调用函数统计每门课程全班的总成绩 和平均成绩以及每个学生课程的总成绩和 平均成绩; ④ 最后调用函数输出学生的成绩。
?
2014-6-22 第六章 数组 30

10周上机题3
#define N 50 void input (float[ ][5], int); void calculate(float[ ][5],float[2][3], int); void print(float[ ][5],float[2][3],int); void main( ) { float s[N][5],a[2][3]; int n; do{ cout<<"输入学生人数,学生数最大为"<<N<<":"; cin>>n; }while(n>50||n<0); input(s,n); calculate(s,a,n); print(s,a,n); } 31 第六章 数组 2014-6-22

13 周上机题 3][5], int n) void input(float s[
{

#define N 50位同学的语文、数学和英语成绩:"<<endl; cout<<“ 输入"<<n<<"

for(int i=0;i<n;i++) void input (float[ ][5], int); { cout<<" 第"<<i+1<<"位同学的语文、数学和英语成绩: void calculate(float[ ][5],float[2][3], int); "<<endl; cin>>s[i][0]>>s[i][1]>>s[i][2]; void print(float[ ][5],float[2][3],int); } void main( ) } { float s[N][5],a[2][3]; int n; 地址传递 do{ cout<<"输入学生人数,学生数最大为"<<N<<":"; cin>>n; }while(n>50||n<0); input(s,n); calculate(s,a,n); print(s,a,n); } 32 第六章 数组 2014-6-22

10周上机题3
void calculate(float s[ ][5], float a[2][3],int n) #define N 50 { input int i,j; void (float[ ][5], int); for(j=0;j<3;j++) 各科的全班总 void calculate(float[ ][5],float[2][3], int); a[0][j]=0; 成绩赋初值 void print(float[ ][5],float[2][3],int); for(i=0;i<n;i++) { ) s[i][3]=0; void main( for(j=0;j<3;j++) { float s[N][5],a[2][3]; 每位同学的 { s[i][3]+=s[i][j]; 地址传递 int n; 总成绩赋初 a[0][j]+=s[i][j]; 值 } do{ s[i][4]=s[i][3]/3; cout<<"输入学生人数,学生数最大为 "<<N<<":"; } cin>>n; for(j=0;j<3;j++) a[1][j]=a[0][j]/n; }while(n>50||n<0); }

input(s,n);
2014-6-22

calculate(s, a, n); print(s,a,n);
第六章 数组 33

}

10周上机题3
void #define print(float ][5], float a[2][3], int n) N s[ 50 { void for(int i=0;i<n;i++) input (float[ ][5], int); { cout<<“ 第”<<i+1<<“ 位同学的语文、数学和英语 ”; void calculate(float[ ][5],float[2][3], int); cout<<“ 成绩、总成绩和平均成绩分别是: ”<<endl; void print(float[ ][5],float[2][3],int); for(int j=0;j<5;j++ ) cout<<s[i][j]<<'\t'; void main( ) cout<<endl; { float s[N][5],a[2][3]; } int n; cout<<“全班的总成绩和平均成绩分别是: "; do{ cout<<“语文课:”<<a[0][0]<<'\t'<<a[1][0]<<endl; cout<<"输入学生人数,学生数最大为"<<N<<":"; cout<<“数学课:”<<a[0][1]<<'\t'<<a[1][1]<<endl; cin>>n; cout<<“ 英语课:”<<a[0][2]<<'\t'<<a[1][2]<<endl; } }while(n>50||n<0);

input(s,n);
2014-6-22

calculate(s,a,n); print(s,a,n);
第六章 数组 34

}

查找和排序算法
顺序查找法 ? 二分法查找
?

冒泡法排序 ? 插入排序法 ? 选择排序法
?

2011/12/4

第六章 数组

35

查找算法
在一组数中查找一个数据有多种办法,最简单的 就是顺序查找——从第0个元素开始依次逐个找 如果这组数据的量很大,而且是有序排列,那么, 有一种查找的办法要比顺序查找的效率高得多,这 就是折半查找法(二分法) 下面分别介绍顺序查找和折半查找的算法

2011/12/4

第六章 数组

36

查找算法——顺序查找
假如以下数组表示学生某一课程的成绩,要查 找成绩为89分的学生(用x表示)。通常的做法是用 x 与各个元素比较,如果其中一个元素的数据与 x 相 等,就记下它的学号(下标) 算法如下 for(j=0;j<10;j++)

if(a[j]==x) p=j;
x 89 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9] 85 73 75 67 63 92 74 89 81 90

2011/12/4

第六章 数组

37

查找算法——顺序查找
运行算法时的查找过程

请问,循环结束时, (1)j= ? (2)p= ? (3) 找到哪个元素?
(4)这个算法存在什么缺点? (5)怎样克服这个缺点?

for(j=0;j<10;j++) if (a[j]==x) p=j;
循环查找
x 89

找到了

a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9] 85 73 75 67 63 92 74 89 81 90
j= 0 1 2 3 4 5 6 7 8 9
38

2011/12/4

第六章 数组

查找算法——顺序查找

数据找到后,先记下元素的下标,再执行 break 使循环 中断。这样,不管其后还有多少数据也不再查找,提高了 算法的效率 for(j=0;j<10;j++) if(a[j]==x)p=j; { p=j; break; }
循环查找 x 89 找到了

a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9] 85 73 75 67 63 92 74 89 81 90 j= 0 1 2 3 4 5 6 7
第六章 数组 39

2011/12/4

查找算法——顺序查找
但是,如果一组数据有成千上万个,且待查的数据 可能排在末位,那么,这样的查找就很费事 如果这组数排列有序,那么,就可采用折半查找 的算法。这种算法的效率比顺序查找更高。下面就 来介绍这种算法
循环查找 x 89 找到了

a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9] 85 73 75 67 63 92 74 89 81 90 j= 0 1 2 3 4 5 6 7
第六章 数组 40

2011/12/4

查找算法——折半查找
所谓折半查找,就是把所有待查的数据拆分成两半 (两个查找区)然后试探被查的数据在哪个区 如何拆分呢? 首先,利用元素下标顺序排列的特点,将最小与最 大下标之和除以 2 ,即把数组分成两半 。本例中: (0+9)/2=4 而下标为4的元素是折点,不妨称a[4]为折点元素
左查找区 x 89
2011/12/4

右查找区

63 67 73 74 75 81 83 89 90 92
第六章 数组 41

查找算法——折半查找
为了用算法来描述,下面用变量和表达式来表示 折半的关系 mid=(low+high)/2 首先,利用元素下标顺序排列的特点,将最小与最 大下标之和除以 2 ,即把数组分成两半。本例中: (0+9)/2=4
low 最小下标 x 89
2011/12/4

mid 折点下标

high 最大下标

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 42

查找算法——折半查找
执行这个表达式,即把数组拆成两半 mid=(low+high)/2 此时可将x与折点元素比较。如果x恰好等于折点元 素,就是找到了,即可结束查找 如果 x 小于或大于折点元素,就要继续在左区或右 区查找
左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 43

查找算法——折半查找
为了继续利用下面的表达式 mid=(low+high)/2 应注意下标变量 low 和 high 的位置变化。在左区, low不变
low high 左查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 44

查找算法——折半查找
为了继续利用下面的表达式 mid=(low+high)/2 由于high是折点下标mid的邻居,因此 high=mid-1
low high 左查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 45

查找算法——折半查找
为了继续利用下面的表达式 mid=(low+high)/2 在右区,high不变
low high

左查找区
63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 46

查找算法——折半查找
为了继续利用下面的表达式 mid=(low+high)/2 由于low也是折点下标mid的邻居,因此
low=mid+1 low high

左查找区
63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 47

查找算法——折半查找
然后即可继续利用下面的表达式对左或右区折半 mid=(low+high)/2 本例中mid=7,因此
low=mid+1 low high

左查找区
63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 48

查找算法——折半查找
再用x比较当前的折点元素 找到了! 然后即可继续利用下面的表达式对左或右区折半 mid=(low+high)/2 本例中mid=7,因此
左查找区 81 83 a[5]a[6]

89 a[7] 右查找区

右查找区 90 92 a[8]a[9]

x 89
2011/12/4

81 83 89 90 92 a[5]a[6]a[7]a[8]a[9] 63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 49

查找算法——折半查找
mid=(low+high)/2;

现在用算法来总结查找的过程 1.将数组折半
左查找区
63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 50

查找算法——折半查找
mid=(low+high)/2; if(x!=a[mid]) //1.若条件为False,找到了! if(x<a[mid])high=mid-1; else low=mid+1; 比较结果分三种情况 2.将待查数据与折点元素比较 左查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 51

查找算法——折半查找
mid=(low+high)/2; if(x!=a[mid]) 1.若条件为True if(x<a[mid])high=mid-1; else low=mid+1; 再分两种情况! 比较结果分三种情况 2.将待查数据与折点元素比较 左查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 52

查找算法——折半查找
mid=(low+high)/2; if(x!=a[mid]) if(x<a[mid])high=mid-1; 2.若条件为True,查左区 else low=mid+1; high=mid-1 low high 左查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4]

右查找区
81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 53

查找算法——折半查找
mid=(low+high)/2; if(x!=a[mid]) if(x<a[mid])high=mid-1; else low=mid+1; 3.若条件为False,查右区 low=mid+1 low 右查找区 75 a[4]

high

左查找区
63 67 73 74 a[0]a[1]a[2]a[3]

x 89
2011/12/4

81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 54

查找算法——折半查找
while(low<=high){ mid=(low+high)/2; if(x!=a[mid]) if(x<a[mid])high=mid-1; else low=mid+1;

}

本例可知,此时应再将右区折半。这需要重复以上算法。 low=mid+1 如何重复呢? low high 左查找区 右查找区
63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 55

查找算法——折半查找
while(low<=high){ mid=(low+high)/2; 拆分,并求折点元素 if(x!=a[mid]) if(x<a[mid])high=mid-1; else low=mid+1;

左查找区 右查找区 先分析本例如何结束循环。 81 83 89 90 92 假设循环可以继续,则有 a[5]a[6] a[7] a[8]a[9] 左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

}

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 56

查找算法——折半查找
while(low<=high){ mid=(low+high)/2; if(x!=a[mid]) 条件为False,找到了! if(x<a[mid])high=mid-1; else low=mid+1; 一旦执行,即中断循环 else {p=mid;break;} 左查找区 右查找区 } 89 90 92 如何用算法来确认找到了呢? 81 83 a[5]a[6] a[7] a[8]a[9] 左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 57

查找算法——折半查找
while(low<=high){ 这是把找到的元素 mid=(low+high)/2; 下标记录在变量p中 if(x!=a[mid]) if(x<a[mid])high=mid-1; 该算法说明,被找到 的元素必定是折点元素, else low=mid+1; 其下标必定是:mid else {p=mid;break;} 左查找区 右查找区 } 就是说,即使拆剩一个元素, 81 83 89 90 92 仍需进行折半来确认 a[5]a[6] a[7] a[8]a[9] 左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 58

查找算法——折半查找
while(low<=high){ mid=(low+high)/2; 如果数组中没有 if(x!=a[mid]) if(x<a[mid])high=mid-1; 待查的数据,如何 保证循环结束? else low=mid+1; else {p=mid;break;} 左查找区 右查找区 } 81 83 89 90 92 a[5]a[6] a[7] a[8]a[9] 左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 59

查找算法——折半查找
while(low<=high){ low<=high mid=(low+high)/2; 当出现low>high if(x!=a[mid]) if(x<a[mid])high=mid-1; 结果必定出错,该结 else low=mid+1; 束循环了! else {p=mid;break;} 左查找区 右查找区 } 81 83 89 90 92 a[5]a[6] a[7] a[8]a[9] 左查找区 右查找区 63 67 73 74 a[0]a[1]a[2]a[3] 75 a[4] 81 83 89 90 92 a[5]a[6]a[7]a[8]a[9]

x 89
2011/12/4

63 67 73 74 75 81 83 89 90 92 a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
第六章 数组 60

查找算法——折半查找
void find( ){ int low,high,mid,p; while(low<=high){ low<=high mid=(low+high)/2; if(x!=a[mid]) if(x<a[mid])high=mid-1; else low=mid+1; else {p=mid;break;}

形参

}
return ?; }

返回值?

2011/12/4

第六章 数组

61

查找算法——折半查找
void find( int a[ ], int x, int n ){ int low=0,high=n-1,mid,p; while(low<=high){ low<=high mid=(low+high)/2; if(x!=a[mid]) 在主函数中调用 if(x<a[mid])high=mid-1; find()函数 else low=mid+1; else {p=mid;break;}

}
return p ?; } void main(){ int a[10],x,p; cin>>x; for(int i=0;i<10;i++)cin>>a[i]; p=find(a,x,10); cout<<“a[”>>p>>“]=”>>a[p]>>“\n”; }
第六章 数组 62

2011/12/4

查找算法——折半查找
void find( int a[ ], int x, int n ){ int low=0,high=n-1,mid,p; while(low<=high){ low<=high mid=(low+high)/2; if(x!=a[mid]) if(x<a[mid])high=mid-1; else low=mid+1; 实参向形参传递数 else {p=mid;break;}

}
return p ?; }

据——形、实结合

void main(){ int a[10],x,p; cin>>x; for(int i=0;i<10;i++)cin>>a[i]; p=find(a,x,10); cout<<“a[”>>p>>“]=”>>a[p]>>“\n”; }
第六章 数组 63

2011/12/4



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com