习题1
(Leonhard Euler ,1707 —1783) 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉提出并解
决了该问题。七桥问题是这样描述的:一个人是否能在
一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗
的海南岸)城中全部的七座桥后回到起点,且每座桥只
经过一次,图1.7是这条河以及河上的两个岛和七座桥的
草图。请将该问题的数据模型抽象出来,并判断此问题
是否有解。
七桥问题属于一笔画问题。输入:一个起点输出:相同的点
1,一次步行
2,经过七座桥,且每次只经历过一次
3,回到起点
该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶
点。另一类是只有二个奇点的图形。
2 ?在欧几里德提出的欧几里德算法中(即最初的欧几里德
算法)用的不是除法而是减
法。请用伪代码描述这个版本的欧几里德算法
1. r= m-n
2. 循环直到r=0
2.1 m=n
2.2 n=r
2.3 r=m-n
3输出m
3 ?设计算法求数组中相差最小的两个元素(称为最接近数)
的差。要求分别给出伪代码和C++描述。
//采用分治法
//对数组先进行快速排序
//在依次比较相邻的差
#in clude
using n amespace std;
int parti on s(i nt b[],i nt low,i nt high) {
int prvotkey=b[low]; b[0]=b[low]; while (low
b[low]=b[high];
while (low b[high]=b[low]; } b[low]=b[0]; return low; } void qsort(int l[],int low,int high) { int prvotloc; if(low } } void quicksort(int l[],int n) { qsort(l,1,n); // 第一个作为枢轴} int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;// 将最小差的值赋值给value for (int b=1;b<11;b++) cout< cout< quicksort(a,11); for(int i=0;i!=9;++i)将第一次排序的结果作为枢轴 递归调用排序由low 到prvotloc-1 递归调用排序由prvotloc+1 到high ,从第一个排到第n 个 { if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) ) value=a[i+1]-a[i]; else value=a[i+2]-a[i+1]; } cout< return 0; } 4. 设数组 a[n] 中的元素均不相等, 设计算法找出 a[n] 元素,并说明最坏情况下的比较次数。要求分别给出伪代码和 #include int a[]={1,2,3,6,4,9,0}; int mid_value=0;// 将“既不是最大也不是最小的元素 for(int i=0;i!=4;++i) { if(a[i+1]>a[i]&&a[i+1] break; } else if(a[i+1]a[i+2]) { mid_value=a[i+1]; cout< } }//for return 0; } 中一个既不是最大也不是最小的 C++描述。 的值赋值给它 5. 编写程序,求n 至少为多大时,n 个“ 1”组成的整数能被2013 整除。 #include using namespace std; int main() { double value=0; for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为:"< break; } }//for return 0; } 6?计算n值的问题能精确求解吗?编写程序,求解满足给定精度要求的n值 #include using namespace std; int main () { double a,b; double arctan(double x);// 声明 a = 16.0*arcta n( 1/5.0); b = 4.0*arcta n(1/239); cout << "PI=" << a-b << endl; return 0 ; } double arctan(double x) { int i=0; double r=0,e,f,sqr;// 定义四个变量初 sqr = x*x; e = x; while (e/i>1e-15)// 定义精度范围 { f = e/i;//f是每次r需要叠加的方程 r = (i%4==1)?r+f:r-f; e = e*sqr;//e 每次乘于x 的平方i+=2;//i 每次加2 }//while return r; } 天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;//k 为该自然数所有因子之和 value = value/ i; } }//for if(k==value) cout<<" 该自然数是完美数"< else cout<<" 该自然数不是完美数"< return 0; } 8. 有4 个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用 1 分钟,乙过桥要用 2 分钟,丙过桥要用 5 分钟,丁过桥要用10 分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间? } } 由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟:甲,乙过桥且甲回来 第二趟:甲,丙过桥且甲回来 第一趟:甲,丁过桥 一共用时19小时 9 ?欧几里德游戏:开始的时候,白板上有两个不相等的正整数,两个玩家交替行动, 每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这 个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写 不出新数字时,他就输了。请问,你是选择先行动还是后行动?为什么? 设最初两个数较大的为 a,较小的为b ,两个数的最大公约数为 factor 。 则最终能出现的数包括 :factor, factor*2, factor*3,…,factor*(a/factor)=a. —共 a/factor 个。 如果a/factor 是奇数,就选择先行动;否则就后行动。 习题2 1 ?如果 T i (n)=O(f (n)), T 2(n)=O(g(n)),解答下列问题: (1 )证明加法定理: T 1(n)+ T 2(n)=max{ O(f (n)), O(g(n))}; (2 )证明乘法定理: 「(n )x T 2(n)=O(f (n))x O(g(n)); (3)举例说明在什么情况下应用加法定理和乘法定理 (3)比如在 for (f(n)) { for(g( n)) } 中应该用乘法定理 如果在“讲两个数组合并成一个数组时” ,应当用加法定理 2 ?考虑下面的算法,回答下列问题:算法完成什么功能?算法的基本语句是什么?基本 语句执行了多少次?算法的时间复杂性是多少? (2) int Q(int n) { if (n == 1) return 1; else return Q(n-1) + 2 * n - 1; (1) int Stery(int n) { int S = 0; for (int i = 1; i <= n; i++) S = S + i * i; return S; (1) 完成的是1-n 的平方和 基本语句:s+=i*i ,执行了 n 次 时间复杂度O (n ) (2) (2)完成的是n 的平方 基本语句:return Q(n -1) + 2 * n - 1,执行了 n 次 时间复杂度O (n ) 3. 分析以下程序段中基本语句的执行次数是多少,要求列出计算公式。 (1) int T(i nt n) { if(n==1) return 4; else if(n >1) return 3*T( n-1); } (2) int T(int n) { if(n==1) return 1; else if(n >1) return 2*T( n/3)+n; } 5. 求下列问题的平凡下界,并指出其下界是否紧密。 (1) 求数组中的最大元素; (2) 判断邻接矩阵表示的无向图是不是完全图; (3) 确定数组中的元素是否都是惟一的; (1) for (i = 1; i <= n; i++) if (2*i <= n) for (j = 2*i; j <= n; j++) y = y + i * j ; (2) m = 0; for (i = 1; i <= n; i++) for (j = 1; j <= 2*i; j++) m=m+1; (1) 基本语句2*i (2) 基本语句 m+=1 执行了 (n/2)*n=0(n*n) 4. 使用扩展递归技术求解下列递推关系式: 门)T(n) 4 n 1 3T (n 1) n 1 (2) T(n) 1 n 1 2T(n 3) n n 1 (4)生成一个具有n 个元素集合的所有子集 ⑴ Q (n) 紧密? (2) Q ( n*n) ⑶ Q (logn+n )(先进行快排,然后进行比较查找) (4) Q (2A n) 7.画出在三个数 &国际象棋是很久以前由一个印度人 Shashi 发明的,当他把该发明献给国王时,国王 很高兴,就许诺可以给这个发明人任何他想要的奖赏。 Shashi 要求以这种方式给他一些粮 食:棋盘的第1个方格内只放1粒麦粒,第2格2粒,第3格4粒,第4格8粒,……, 以此类推,直到64个方格全部放满。这个奖赏的最终结果会是什么样呢? #in clude long double result=1; double j=1; for(int i=1;i<=64;++i) { j=j*2; result+=j; j++; } cout< a, b, c 中求中值问题的判定树。 //BF 算法 #include int BF(char S[], char T[]) { int index = 0; int i = 0, j = 0; while ((S[i] != '\0') && (T[j] != '\0')) { if (S[i] == T[j]) { i++; j++; } else { ++index; i = index; j = 0; } } if (T[j] == '\0') return index + 1; else return 0; } int main() { char s1[19]="ababcabccabccacbab";习题3 1.假设在文本"ababcabccabccacbab" 中查找模式"abccac" ,写出分别采用BF 算法和KMP 算法的串匹配过 char s2[7]="abccac"; cout<< BF( s1, s2) < return 0; } //KMP 算法 #include void GetNext(char T[ ], int next[ ]) { int i, j, len; next[0] = -1; for (j = 1; T[j]!='\0'; j++) { for (len = j - 1; len >= 1; len--) { for (i = 0; i < len; i++) if (T[i] != T[j-len+i]) break; if (i == len) { next[j] = len; break; } }//for if (len < 1) next[j] = 0; }//for } int KMP(char S[ ], char T[ ]) { int i = 0, j = 0; int next[80]; GetNext(T, next); while (S[i] != '\0' && T[j] != '\0') { if (S[i] == T[j]) //求模式T 的next 值 // 依次求next[j] // 相等子串的最大长度为j-1 // 依次比较T[0]~T[len-1] 与T[j-len]~T[j-1] //其他情况,无相等子串 //求T 在S 中的序号 //假定模式最长为80 个字符 { i++; j++; } else { j = next[j]; if (j == -1) {i++; j++;} if (T[j] == '\0') return (i - strlen(T) +1); else return 0; } int main() { char s1[]="ababcabccabccacbab"; char s2[]="abccac"; cout< } 2. 分式化简。 设计算法, 将一个给定的真分数化简为最简分数形式。 #include { int n;// 分子 int m;// 分母 int factor;// 最大公因子 int factor1; cout<<" 输入一个真分数的分子与分母: "< { factor1 =factor; factor = r; r = factor1% factor; cout<<" 输出该真分数的最简分数: "<<(n/factor)<<"/"<<(m/factor)< } 3. 设计算法,判断一个大整数能否被 11 整除。可以通过以下方法:将该数的十进制表示 从右端开始,每两位一组构成一个整数,然后将这些数相加,判断其和能否被 11 整除。 例如,将 //返回本趟匹配的开始位置 例如,将 6/8 化简为 3/4。 562843748 分割成5,62,84,37,48,然后判断(5+62+84+37+48) 能否被11 整除 //将一个大整数看成一个数组 //数组的奇数位对应数的10 倍加上数组偶数对应数的本身 //验证结果能否被11 整除 #include int main() { int a[9]={5,6,2,8,4,3,7,4,8}; int result=0; //result 为题目要求的各位之和for(int i=0;i!=9;++i) { if(i%2==0) result+=a[i]; //i 为偶数位时,结果加上其对应数组数的本身else result+=a[i]*10; //i 为奇数位时,结果加上对应数组数的10 倍} if(result%11==0) cout<<" 该整数能被11 整除"< else cout<<" 该整数不能被11 整除"< return 0; } 4. 数字游戏。把数字1,2,…,9这9个数字填入以下含有加、减、乘、除的四则运算式中,使得该等式成立。要求9 个数字均出现一次且仅出现一次,且数字 1 不能出现在乘和除的一位数中(即排除运算式中一位数为 1 的平凡情形) 。 X + - - = 0 5. 设计算法求解a n mod m,其中a、n和m均为大于1的整数。(提示: 超出int 型的表示范围,应该每做一次乘法之后对n 取模) #include using namespace std; int square(int x) { return x*x; } //用递归思想 int resultmod(int a, int n) { if(n== 0) return 1; if(n%2 == 0) return square(resultmod(a, n/2)); //n 为偶数的时,取n 的一半防止溢出else return a*resultmod(a, n-1); //n 为奇数时,取n-1 ; } int main() { int a, n, m; cout<<"请输入a,n, m:"<<""; cin>>a>>n>>m; cout< int result = resultmod(a, n); cout<<"a A n mod m 的结果为:"<< result % m< return 0; } 6. 设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂性为 复杂性为O(1)。 7. 设计算法,在数组r[n]中删除重复的元素,要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include int b[100]={0}; int i,k; k=0; static int j=0; for(i=0;i b[a[i]]++; for(i=0;i<100;i++) { if(b[i]!=0) { if(b[i]==2) { k++; } a[j]=i; j++; } } for(i=0;i } int main() { int a[]={1,2,1,3,2,4}; deletere(a,6); return 0; } //在数组查找相同的元素 //把其中一个相同的数值的元素位置设成一个“特殊数值” //输出所求函数#include using namespace std; int main() { int a[]={1,2,1,5,3,2,9,4,5,5,3,5}; int i,j; for( i=0;i<12;i++) { for(j=0;j { if(a[j]==a[i]) a[i]=64787250;// 设一个数组不存在的数值} }//for for(i=0;i<12;i++) { if(a[i]!=64787250) cout< } cout< return 0; } 8. 设表A={a i, a2,…,a n},将A拆成B和C两个表,使A中值大于等于表B,值小于0的元素存入表C,要求表B和C不另外设置存储空间而利用表 //先对A 进行快排 〃将大于0的元素给B ,小于0的元素给C #include using namespace std; int partions(int l[],int low,int high) { int prvotkey=l[low]; l[0]=l[low]; while (low { while (low --high; l[low]=l[high]; while (low l[high]=l[low]; l[low]=l[0]; return low; }0 的元素存入 A 的空间。 void qsort(int l[],int low,int high) { int prvotloc; if(low { prvotloc=partions(l,low,high); // 将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); // 递归调用排序由low 到prvotloc-1 qsort(l,prvotloc+1,high); // 递归调用排序由prvotloc+1 到high } } void quicksort(int l[],int n) { qsort(l,1,n); // 第一个作为枢轴,从第一个排到第n 个 } int main() { int a[11]={-2,2,32,43,-23,45,36,-57,14,27,-39}; quicksort(a,11); for(int i=1;i<11;i++) { if(a[i]<0) cout<<"C: "< else cout<<"B: "< } cout< return 0; 表兰色,这都是荷兰国旗的颜色)构成的数组,使得所有的 B 排在最后。为荷兰国旗问题设计一个算法,其时间性能是 //0 代表红; 1 代表白; 2 代表蓝 #include void swap_ab ( int *p , int *q ) { int tmp = *p; *p = *q; *q = tmp; } void process ( int a[], int n ) { int *p, *q; p = q = a; while ( p != a+n-1 ) //p 向前遍历,直到便利完毕 { if ( *(p+1) < *p ) { q = p+1; while ( *q < *(q-1) ) { swap_ab ( q, q-1 ); --q; //q 指针后移 } } //if ++p; } //while } int main() 9. 荷兰国旗问题。要求重新排列一个由字符 R, W, B ( R 代表红色,W 代表白色,B 代 R 都排在最前面, W 排在其次, O(n)。 { int a[N] = { 0, 2, 1,2, 0, 1,0, 2, 2, 1, 0, 1,2, 1, 1, 0, 0, 1, 1,2}; // 待处理的数组 cout << "处理后的数组序列:"< 10. 设最近对问题以k 维空间的形式出现,k 维空间的两个点 y 2,…,y k )的欧几里德距离定义为: d(p 1, p 2) (y i -xj 2。对 \ i 1 蛮力算法,并分析其时间性能。 11 ?设计蛮力算法求解小规模的线性规划问题。假设约束条件为: x+3y w 6; (3) x > 0且y 》0;使目标函数3x+5y 取得极大值。 #in clude int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0<=4;++x0) { for(y0=0;(x0+y0<=4) &&(x0+3*y0<=6);++y0) temp=3*x0+5*y0; if(temp>=summax) { summax=temp; x=x0;〃符合sum 最大值的x y=y0;//符合sum 最大值得y } }//for cout<<"x= "< char t[5]="rewq"; for(i nt i=0;i!=4;++i) { if(s[i]!=t[3-i]) { cout<<"qwer 禾口rewq 不是变位词"< return 0; break; } } cout<<"qwer 禾口rewq 是变位词"< 15.在美国有一个连锁店叫7-11 店,因为这个商店以前是早晨7 点开门,晚上11 点关门。有一天,一个顾客在这个店挑选了四样东西,然后到付款处去交钱。营业员拿起计算器,按了一些键,然后说:“总共是$7.11。”这个顾客开了个玩笑说:“哦?难道因为你们的店名叫7-11,所以我就要付$7.11 吗?”营业员没有听出这是个玩笑,回答说:“当然不 是,我已经把这四样东西的价格相乘才得出这个结果的!”顾客一听非常吃惊,“你怎么把 他们相乘呢?你应该把他们相加才对!”营业员答道:“噢,对不起,我今天非常头疼,所以把键按错了。”然后,营业员将结果重算了一遍,将这四样东西的价格加在一起,然而,令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少? 该算法为: int $7.11(float a[],float b[],float c[],float d[],int n) { for(int i=0;i!=n;++i) for(int j=0;j!=n;++j) for(int k=0;k!=n;++k) for(int m=0;m!=n;++m) { if((a[i]+b[j]+c[k]+d[m])==7.11 && a [i]*b[j]*c[k]*d[m]==7.11)