1. DS静态查找之顺序查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用带哨兵的顺序查找算法
输入
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
输入样例
8
33 66 22 88 11 27 44 55
3
22
11
99
输出样例
3
5
error
参考代码
#include<iostream> using namespace std; void search(int e, int array[], int t) { for (int i = t - 1;i >= 0;i--) { if (array[i] == e) { if (i == 0)cout << "error\n"; else { cout << i << endl; break; } } } } int main() { int* array; int t, n; cin >> t; array = new int[t+1]; for (int i = 1;i <= t;i++) cin >> array[i]; cin >> n; int e; while (n--) { cin >> e; array[0] = e; search(e, array,t); } return 0; }
2. DS静态查找之折半查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用折半查找算法
输入
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
输入样例
8
11 22 33 44 55 66 77 88
3
22
88
99
输出样例
2
8
error
参考代码
#include<iostream> using namespace std; void search(int e, int array[], int t) { int low = 1, height = t; int mid; mid = (low + height) / 2; for (;low <= height;) { if (array[mid] == e) { cout << mid << endl; break; } else if (e > array[mid]) { low = mid + 1;mid = (low + height) / 2; } else if (e < array[mid]) { height = mid - 1;mid = (low + height) / 2; } } if (low > height)cout << "error\n"; } int main() { int t, n; int* array; cin >> t; array = new int[t+1]; for (int i = 1;i <= t;i++) cin >> array[i]; cin >> n; int e; while (n--) { cin >> e; search(e, array, t); } return 0; }
3. DS静态查找之顺序索引查找
题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
输入
第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error
输入样例
18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
3
22 48 86
6
13
5
48
40
53
90
输出样例
3-4
error
12-8
error
18-9
error
参考代码
#include<iostream> using namespace std; int main() { int t; int* array; cin >> t; array = new int[t + 1]; for (int i = 1;i <= t;i++) cin >> array[i]; int k; cin >> k; int* maxnum = new int[k]; for (int i = 0;i < k;i++) cin >> maxnum[i]; int *index=new int[k - 1]; index[0] = 1; for (int i = 1, j = 0;i <= t;i++) { if (array[i] > maxnum[j]) { index[j+1] = i; j++; } } int n,e; cin >> n; int count; while (n--) { count = 0; cin >> e; if (e <= maxnum[k - 1]) { int i, j; for (j = 0;j < k;j++) { count++; if (e <= maxnum[j]) { i = index[j]; break; } } int temp; if (j == k - 1)temp = t; else temp = index[j + 1]; for (;i <= temp;i++) { count++; if (e == array[i]) { cout << i << "-" << count << endl; break; } } if (i > temp)cout << "error\n"; } else cout << "error\n"; } return 0; }
4. DS查找——折半查找求平方根
题目描述
假定输入y是整数，我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则x2<y，如果我们查找的数x比y的平方根大，则x2>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x2-y|<0.00001），就可以认为找到了y的平方根。
比如求5的平方根x，则x一定满足0<=x<=5，取x为(5+0)/2=2.5，因为2.5的平方为6.25>5，所以x一定小于2.5，也即x满足0<=x<=2.5，取x为1.25，以此类推
最后求得5的平方根为2.236
温馨提示： 计算过程中为确保精确性，计算变量的类型都用double
保留小数位数请采用printf("%.3lf\n",x) 的格式输出
程序框架参考平时练习中折半查找的方法
输入
第1行输入一个整数n(<100)，表示有n个数
从第2行起到第n+1行输入n个整数
输出
输出n个数的平方根，精确到小数点后三位。
输入样例
2
13
5
输出样例
3.606
2.236
参考代码
#include<iostream> #include<cmath> #include<iomanip> using namespace std; void getsqrt(double number) { double n2=number; double n1 = 0; double n; while (1) { n = (n1 + n2) / 2; if (abs(n * n - number) < 0.00001) { cout << fixed << setprecision(3) << n << endl; break; } if (n * n > number)n2 = n; else n1 = n; } } int main() { int n; cin >> n; double number; while (n--) { cin >> number; getsqrt(number); } return 0; }
