二分搜索_快速排序_背包问题

### 二分搜索 #### 实验目的 - 掌握分治法的基本思想，并学会如何应用这一策略来解决具体的搜索问题。 #### 实验原理 二分搜索算法是一种高效的搜索技术，适用于已排序的数组。其核心思想是通过不断将搜索区间减半的方式来减少搜索范围，从而提高搜索效率。具体步骤如下： 1. 计算当前搜索区间的中间位置 `mid`。 2. 比较目标值 `x` 和中间位置的元素 `a[mid]`。 - 如果 `x = a[mid]`，则找到了目标值，搜索结束。 - 如果 `x < a[mid]`，则只需在数组的左半部继续搜索。 - 如果 `x > a[mid]`，则只需在数组的右半部继续搜索。 3. 重复以上步骤直到找到目标值或者搜索区间为空。 #### 实验内容 编写一个程序，用于实现二分搜索算法，输入一组已排序的数字和要查找的目标值，输出目标值在数组中的索引位置（如果存在）或不在数组中的提示信息。 #### C++ 实现 ```cpp #include <iostream> using namespace std; template<class Type> int binarySearch(Type a[], const Type& x, int n) { int left = 0; int right = n - 1; while (left <= right) { int middle = (left + right) / 2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; } return -1; } int main() { int n, x; cout << "请输入您要查找的数组长度：（最大长度为100）" << endl; cin >> n; cout << "请输入一个升序数组：（长度为" << n << "）" << endl; int a[100]; for (int i = 0; i < n; i++) cin >> a[i]; cout << "请输入您要查询的数值：" << endl; cin >> x; int r = binarySearch(a, x, n); if (r != -1) cout << "该数下标：" << r << endl; else cout << "该数不在数组中!" << endl; return 0; } ``` ### 快速排序 #### 实验目的 - 学习并实践分治法的另一个典型应用场景——快速排序。 #### 实验原理 快速排序的基本思想是选取一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。 #### 实验内容 编写一个程序，使用快速排序算法对一个数组进行排序。 #### C++ 实现 ```cpp #include <iostream> #include <algorithm> using namespace std; template<class T> int Partition(T a[], int p, int r) { int i = p, j = r + 1; T x = a[p]; while (true) { while (a[++i] < x && i < r); while (a[--j] > x); if (i >= j) break; swap(a[i], a[j]); } a[p] = a[j]; a[j] = x; return j; } template<class T> void QuickSort(T a[], int p, int r) { if (p < r) { int q = Partition(a, p, r); QuickSort(a, p, q - 1); QuickSort(a, q + 1, r); } } int main() { int n; cin >> n; int a[100]; for (int k = 0; k < n; k++) cin >> a[k]; QuickSort(a, 0, n - 1); for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } ``` ### 背包问题 #### 实验目的 - 掌握贪心法的应用之一——解决背包问题。 #### 实验原理 背包问题是一种典型的动态规划问题，其核心是通过动态规划的方法计算出在给定的背包容量限制下，如何选择物品才能使得总价值最大化。常用的动态规划方程为：`f[i][v] = max{f[i-1][v], f[i-1][v-c[i]] + w[i]}`，其中 `f[i][v]` 表示前 `i` 件物品恰放入一个容量为 `v` 的背包可以获得的最大价值。 #### 实验内容 编写一个程序，解决一个具体的背包问题实例。 #### C++ 实现 ```cpp #include <iostream> using namespace std; // 假设物品数量为 5，每个物品的价值和重量分别为： int value[] = {10, 20, 30, 40, 50}; int weight[] = {1, 2, 3, 4, 5}; int capacity = 7; // 背包容量 int knapsack(int W, int n) { int dp[W + 1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = W; j >= weight[i - 1]; j--) { dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1]); } } return dp[W]; } int main() { int maxValue = knapsack(capacity, 5); cout << "最大价值为: " << maxValue << endl; return 0; } ``` 以上三个实验不仅介绍了二分搜索、快速排序以及背包问题的基本原理，还提供了具体的C++代码实现，有助于深入理解和学习这些算法。