### 二分搜索
#### 实验目的
- 掌握分治法的基本思想，并学会如何应用这一策略来解决具体的搜索问题。
#### 实验原理
二分搜索算法是一种高效的搜索技术，适用于已排序的数组。其核心思想是通过不断将搜索区间减半的方式来减少搜索范围，从而提高搜索效率。具体步骤如下：
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++代码实现，有助于深入理解和学习这些算法。
