第一题 方程求解

1.实验题目

2. 实验目的

本实验的主要目的是实现使用二分法求解非线性方程的数值求解算法，使得给定函数 y = e^x + ln(x) - 1 的自变量 x 满足要求。通过本实验，学生能够：

1. 理解数值求解方法，尤其是二分法的原理。
2. 掌握函数求值与误差判断的基本操作。
3. 提高算法设计和实现的能力，熟悉数值方法在方程求解中的应用。

3. 算法设计

为实现对给定函数的数值求解，使用二分法逐步逼近所需的自变量 x。具体的算法步骤如下：

1. 输入处理:
   • 接收目标值 y，确定误差容忍度 tolerance，初始区间为 [lower, upper]。
2. 区间扩展:
   • 如果当前上界 upper 的函数值小于 y，倍增上界，确保 y 在区间内。
3. 二分法逼近:
   • 在 [lower, upper] 区间内不断缩小范围，直到满足精度要求。
   • 使用中点 mid，计算 f(mid)，比较 f(mid) 与目标值 y 的大小：
     • 如果 f(mid) < y，则更新下界 lower = mid。
     • 否则更新上界 upper = mid。
4. 结束处理:
   • 当区间长度小于误差容忍度时，返回当前的上界值作为近似解。
5. 时间复杂度：

• 二分法每次迭代将区间长度减半，因此时间复杂度为 O(log(upper - lower))。

6. 代码实现：

#include "solve.h"
#include <cmath>
using namespace std;

long double f(long double x) {
    return exp(x) + log(x) - 1;
}

long double solve(long double y) {
    long double tolerance = 1e-12;
    long double lower = 1e-5;
    long double upper = 20;
    while (f(upper) < y) {
        upper *= 2; 
    }
    while(upper - lower > tolerance) {
        long double mid = (lower + upper) / 2;
        long double f_mid = f(mid);
        if (f_mid < y) lower = mid;
        else upper = mid;
    }
    return upper;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同范围的目标值 y：

• 输入 y：
  • y = 1, y = 10, y = 1000
• 输出 x：
  • 程序能够找到使得 f(x) 与目标值 y 的误差小于 1e-6 的 x 值。

程序运行

• 使用上述函数 solve() 对多个目标值 y 进行求解，程序在合理的时间内输出了相应的 x 值。
• 通过多次测试，包括 y 取较小值、较大值，程序均能收敛到满足误差要求的解。

5. 实验总结与心得

通过本次实验，我进一步掌握了数值求解方法的原理，尤其是二分法在求解非线性方程中的应用。实验中，使用二分法求解的过程简单且有效，但对初始区间的选择非常关键，直接影响到收敛速度和正确性。

在实际实现中，遇到的挑战是如何设置合理的初始区间和误差容忍度，以确保结果的准确性和收敛速度的平衡。特别是在扩展上界时，需要倍增上界，确保目标值在求解区间内，这种动态调整方法在实验中表现出良好的效果。

此外，通过对边界情况的测试，例如 y 取极小值或极大值时，程序的表现验证了其稳定性和健壮性。本次实验让我更加理解了数值方法的重要性，以及在实际应用中合理设计参数和判断条件的重要性。

第二题 最大值最小化

1.实验题目

2. 实验目的

本实验的主要目的是实现将一个包含 n 个正整数的序列划分为 m 个连续子序列，使得所有子序列的和的最大值尽可能小的算法。通过本实验，学生能够：

1. 理解二分查找和贪心策略在优化问题中的应用。
2. 掌握如何将复杂的划分问题转化为最优值搜索问题。
3. 提高算法设计和分析能力，尤其是处理大规模数据的能力。

3. 算法设计

为实现将序列划分为 m 个连续子序列且使最大子序列和最小化的目标，使用了二分查找与贪心的结合。具体的算法步骤如下：

1. 初始区间设定：
   • 设定二分查找的上下界，left 为序列中元素的最大值，right 为序列中所有元素之和。
   • 其中，left 表示所有子序列和的最大值的最小可能值，而 right 表示最大可能值。
2. 二分查找过程：
   • 通过二分查找，逐步缩小最大子序列和的范围，最终找到最小的最大子序列和。
   • 设 mid 为当前区间的中点，使用贪心算法判断是否能够将序列划分为 m 个子序列，使得每个子序列的和不超过 mid。
3. 贪心划分判断：
   • 使用 canDivide 函数对给定的 mid 进行验证：
     • 遍历序列并累积元素和，若累积和超过 mid，则开始一个新的子序列，并增加子序列计数。
     • 如果子序列的数量超过 m，则返回 false，表示无法满足当前的最大和要求。
4. 循环终止条件：
   • 当 left 等于 right 时，找到最小的最大子序列和，即为最终解。
5. 时间复杂度：
   • 二分查找的时间复杂度为 O(log(S))，其中 S 是所有元素之和。
   • 每次判断是否可以划分的复杂度为 O(n)，因此整体时间复杂度为 O(n log(S))。
6. 代码实现：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool canDivide(const vector<int>& nums, int m, long long maxSum) {
    long long cursum = 0;
    int cnt = 1;
    for (int num : nums) {
        if (cursum + num > maxSum) {
            cnt++;
            if (cnt > m) {
                return false; // 如果子序列数超过m，返回false
            }
            cursum = num;
        } else {
            cursum += num;
        }
    }
    return true;
}

int f(const vector<int>& nums, int m) {
    long long left = *max_element(nums.begin(), nums.end());
    long long right = accumulate(nums.begin(), nums.end(), 0LL);
    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (canDivide(nums, m, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        cout << f(nums, m) << endl;
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同规模的输入：

• 输入样例：
  • n = 6, m = 3
  • 序列：1, 2, 3, 2, 5, 4
• 输出：
  • 最优划分方案的最大子序列和为 7。
• 其他测试用例：
  • 通过测试不同规模的序列，包括较小的 n 和接近 10^6 的较大 n，程序均能在合理的时间内输出正确结果。

程序运行

• 程序使用标准输入和输出，可以处理多个测试样例。
• 通过二分法逐步缩小最大和范围，并结合贪心策略判断是否可以满足当前划分条件。
• 在大规模数据下（n 达到 10^6）测试，程序表现出良好的效率和正确性。

5. 实验总结与心得

通过本次实验，我学会了如何使用二分查找和贪心策略解决划分问题。实验中的挑战在于如何有效地确定初始区间并实现高效的划分判断。

通过二分法和贪心算法的结合，程序能够在较大规模的输入下快速得出最优解，这充分体现了二分查找在解决优化问题中的重要性。特别是在面对大数据量时，简单的暴力求解方法难以满足时间要求，而二分查找与贪心策略的结合使得问题可以在 O(n log S) 的时间复杂度内解决。

此外，本次实验让我理解了处理大规模数据时，合理选择算法的重要性，以及如何将复杂问题转化为优化搜索问题。对于类似的问题，二分查找和贪心策略的组合往往能带来很好的效果。

第三题 Binary Search

1.实验题目

2. 实验目的

本实验的主要目的是实现二分查找函数，能够在给定的有序数组中找到目标元素的最后一次出现的位置。如果目标元素不存在，则返回 -1。通过本实验，学生能够：

1. 掌握二分查找算法的基本原理及其实现方法。
2. 理解如何在有序数组中快速查找特定元素。
3. 提高对算法边界条件的处理能力，熟悉常见查找算法的优化技巧。

3. 算法设计

本实验要求实现二分查找，找到目标元素在有序数组中的最后一次出现位置。具体算法步骤如下：

1. 初始区间设定：
   • 设定查找区间的左右边界 left 和 right，初始值分别为 0 和 size - 1。
2. 二分查找过程：
   • 在区间 [left, right] 中不断寻找目标元素 target。
   • 计算中点 mid，如果 s[mid] 等于 target，则将其保存并继续在右半部分查找，寻找目标的最后一次出现。
   • 如果 s[mid] 小于 target，则更新 left = mid + 1，否则更新 right = mid - 1。
3. 终止条件：
   • 当 left 超过 right 时，查找过程结束。如果找到目标，则返回其最后一次出现的索引，否则返回 -1。
4. 代码实现：

#include "binSearch.h"

int binSearch(const int s[], const int size, const int target) {
    int left = 0;
    int right = size - 1;
    int result = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (s[mid] == target) {
            result = mid; // 记录目标元素的索引
            left = mid + 1; // 继续在右半部分查找
        } else if (s[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同情况的输入：

• 输入样例：
  • 数组 s = {0, 1, 1, 3, 3, 3, 6, 6}
  • 目标元素 target = 3
• 输出：
  • 5（目标元素 3 最后一次出现的位置）
• 其他测试用例：
  • 目标元素不存在的情况，例如 target = 4，输出应为 -1。
  • 目标元素在数组两端的情况，例如 target = 0 或 target = 6。

程序运行

• 程序通过标准输入输出进行测试，能够处理不同的数组和目标元素输入。
• 在测试过程中，程序正确地返回了目标元素最后一次出现的位置，符合预期结果。
• 通过边界条件的测试，例如数组为空、目标元素位于边界、目标元素不存在等情况，程序表现出稳定的行为。

5. 实验总结与心得

通过本次实验，我深入理解了二分查找算法的原理及其在实际问题中的应用。二分查找的核心在于每次将查找范围缩小一半，从而大大提高查找效率，时间复杂度为 O(log n)，适用于大规模有序数据的查找。

在本实验中，挑战主要在于如何正确处理目标元素的最后一次出现位置。为此，在找到目标元素后继续向右查找，确保找到的是最后一个位置。这一过程体现了对二分查找的灵活运用。

此外，通过对边界条件的处理，我学会了在算法实现中考虑各种极端情况，例如数组为空、目标元素不在数组中等，从而使程序更加健壮和可靠。本次实验让我对二分查找的实现和应用有了更加深刻的理解，并提高了对查找类算法的编程能力。