【GESP】C++五级练习题 luogu-P1163 银行贷款 | 二分答案和精密模拟

GESP C++ 五级练习题，二分答案考点应用，重点理解二分答案和精密模拟方法。五、六级考生都可以练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1163 银行贷款

题目要求

题目描述

当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

输入格式

三个用空格隔开的正整数。

第一个整数表示贷款的原值 $w_0$，第二个整数表示每月支付的分期付款金额 $w$，第三个整数表示分期付款还清贷款所需的总月数 $m$。

输出格式

一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 $0.1\%$。

数据保证答案不超过 $300.0\%$。

输入输出样例 #1

输入 #1

1000 100 12

输出 #1

2.9

说明/提示

数据保证，$1 \leq w_0, w\leq 2^{31}-1$，$1 \leq m\leq 3000$。

---

题目分析

这道题的核心考点是“二分答案（实数域）”与“模拟”。

1. 题目模型转化与单调性分析

题目要求找出一个未知的月利率 $x$，使得在给定的初始贷款 $w_0$、每月还款 $w$ 的情况下，刚好在 $m$ 个月后将贷款还清（即第 $m$ 个月还完后剩余欠款为 $0$）。

如果直接根据金融复利公式正向推导去求解高次方程，在算法编程中会非常困难。因此我们逆向思考：如果我们“猜”一个利率，能否验证它对不对？ 这就需要分析利率与最终欠款之间的关系：

• 利率越高，每个月产生的利息就越多，为了抵消这些利息，最终 $m$ 个月后剩下的欠款也会越多（在固定还款额的前提下）。
• 利率越低，每个月产生的利息就越少，最终 $m$ 个月后剩下的欠款也会越少。

由于最终欠款金额随着利率的增加而单调递增，两者之间具备极强的单调性，因此我们可以使用二分查找来“猜”这个利率进行试错逼近（即二分答案）。

2. Check 函数的设计（模拟还款过程）

二分答案的核心在于编写 check(x) 函数，用来验证当前猜测的利率 $x$ 是否符合实际情况。 由于题目明确给定了逻辑是“假设利率按月累计”，我们可以直接用一个循环模拟这 $m$ 个月的还款过程：

• 设初始欠款 balance = w0。
• 第 1 个月结算时：欠款 = 原欠款 + 原欠款产生的利息 - 当月还款，即 balance = balance * (1 + x) - w。
• 依次循环 $m$ 个月。

最后检查剩余的 balance：

• 如果 balance > 0：说明最后还欠银行钱。这就意味着我们猜的利率 $x$ 太高了，导致计算出的利息超出了实际还款能力，所以真实的利率应该比猜测的 $x$ 小，应该去左半区间寻找。
• 如果 balance <= 0：说明刚好还清或者还超了。这意味着猜测的利率 $x$ 太低了（或刚好），真实利率应该比猜测的 $x$ 大（或等于），应该去右半区间寻找。

3. 二分查找的实现与两套写法的对比

由于要寻找的利率是一个实数（浮点数），这属于实数域上的二分查找。根据题目的数据保证“答案不超过 300%”（即 3.0），所以二分的初始区间为 [0, 3.0]。

对于实数二分，最关键的难点在于循环结束条件的判定（精度控制），这两套示例代码恰好展示了两种不同的控制策略：

（1）基于差值的精度控制 (while (l < r - 0.0001))

• 思路：当左右边界 l 和 r 的差值小于一个极小的值（如 $10^{-4}$）时，认为 l 和 r 已经足够接近，此时的区间边界即可作为最终答案。
• 细节把控：题目要求最终结果保留到 $0.1\%$（即保留小数点后一位的百分数，转换成实数就是小数点后 3 位）。为了防止中途计算导致精度丢失，用于控制循环的 eps（误差阈值）一般至少要比要求的精度再多一到两位，所以代码中巧妙地使用了 0.0001 作为判断条件。
• 优缺点：逻辑直观，符合常人的直觉；但如果由于大意将精度 eps 设置得太小（例如 $10^{-15}$），由于浮点数的舍入误差特性，极容易导致死循环（Time Limit Exceeded）。

（2）固定次数的迭代控制 (for (int i = 0; i < 100; i++))

• 思路：摒弃使用具体的差值去判断，而是采取简单粗暴的强制二分固定次数（如 $100$ 次）。
• 细节把控：二分法的区间每次折半，循环 $100$ 次后，区间长度会缩小到原来的 $\frac{1}{2^{100}}$ （约为 $7.8 \times 10^{-31}$）。这个极限精度已经远远超出了 C++ 中 double 类型的精度表示范围，绝对能满足任何算法竞赛题目的严苛要求。
• 优缺点：这是算法竞赛中极为推崇的“终极”防错写法。它彻底避免了因浮点数精度误差而导致的死循环困扰，并且运行时间为固定常数，不会超时，稳健性极高。

4. 答案的收尾输出

题目要求输出百分数，且四舍五入精确到 $0.1\%$。程序中二分最终求出来的是原始小数（比如结果求出 $x = 0.0294$），在最终输出时需要通过乘上 $100$ 放大为百分比数值（变为 $2.94$），最后利用 printf 中的 %.1f 格式化符号，利用其自带的四舍五入功能，漂亮地输出最终结果。

---

示例代码

写法一，用0.0001作为精度

#include <cstdio>

double w0, w;
int m;
/**
 * check 函数：根据猜测的月利率 x，模拟整个还款过程
 * @param x 当前猜测的月利率
 * @return true 表示在给定利率下，还完 m 个月后仍有欠款（即猜测的利率太高）
 *         false 表示还完 m 个月后刚好还清或超额还款（即猜测的利率太低或刚好）
 */
bool check(double x) {
    double w1 = w0;
    for (int i = 1; i <= m; i++) {
        // 每月结算：原欠款加上产生的利息，再减去当月还款额
        w1 = w1 * (1 + x) - w;
    }
    // 如果最后余额 > 0，说明利率定高了，导致最后还欠钱
    return w1 > 0;
}

int main() {
    // 读取贷款原值、每月还款额、总月数
    scanf("%lf %lf %d", &w0, &w, &m);

    // 二分查找范围：0.0 到 3.0 (题目保证答案不超过 300%)
    double l = 0, r = 3;

    // 精度控制：当左右边界的差值小于 0.0001 (0.01%)
    // 时，认为已经达到了题目要求的精确度 (0.1%)
    while (l < r - 0.0001) {
        double mid = l + (r - l) / 2;
        if (check(mid)) {
            // 如果欠款 > 0，说明猜测的利率太高，应该在左半区继续找更小的利率
            r = mid;
        } else {
            // 如果欠款 <=
            // 0，说明猜测的利率太低（或刚好），应该在右半区继续找更大的利率
            l = mid;
        }
    }

    // 题目要求输出百分数，所以要把计算出的小数形式的利率乘以 100
    // 例如：计算出的 l = 0.029，乘以 100 后变为 2.9
    // %.1f 会自动进行四舍五入并保留一位小数
    printf("%.1f\n", l * 100);
    return 0;
}

写法二、用100次循环作为精度控制

#include <cstdio>

double w0, w;
int m;

/**
 * check 函数：根据猜测的利率 x，计算 m 个月后的剩余欠款。
 * @return 如果剩余欠款 > 0，返回 true (表示利率高了)；否则返回 false。
 */
bool check(double x) {
    double current_balance = w0;
    for (int i = 1; i <= m; i++) {
        // 每月结算：原欠款加上产生的利息，再减去当月还款额
        current_balance = current_balance * (1 + x) - w;
    }
    return current_balance > 0;
}

int main() {
    // 输入贷款原值、每月分期金额、总月数
    scanf("%lf %lf %d", &w0, &w, &m);

    // 二分搜索利率范围：从 0% 到 300%
    double left = 0, right = 3.0;

    // 进行 100 次迭代，足以保证极高精度（远超题目要求的 0.1%）
    for (int i = 0; i < 100; i++) {
        double mid = left + (right - left) / 2.0;
        if (check(mid)) {
            // 如果期末还有欠款，说明利息收多了，需要调低利率
            right = mid;
        } else {
            // 如果期末欠款已经清零或多还了，说明利率可能偏低
            left = mid;
        }
    }

    // 题目要求输出百分数，四舍五入到 0.1%
    // 例如：0.029 应该输出 2.9
    printf("%.1f\n", left * 100.0);

    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号