[Daimayuan] 高利贷(C++,二分)
191919岁的大学生小 LLL 家里情况不好,每月固定生活费不足以买一部苹果手机。当他得知有贷款机构可以贷小额贷款并且可以分期等额还款,每月只需要还几百块时,在虚荣心的驱使下他开始自己的贷款之旅。
贷款机构声称利率按月累计,贷款人在贷款期间每月偿还固定的分期付款金额。
给出小 LLL 贷款的原值为 nnn,分期付款金额 mmm 和分期付款还清贷款所需的总月数 kkk,求该贷款的月利率 ppp。
输入格式
三个用空格隔开的正整数 nnn,mmm,kkk,含义如上述所示。
输出格式
一个实数 ppp,表示该贷款的月利率(用小数表示),和标准输出绝对值不超过10−610^{−6}10−6即可。
数据范围
1≤n,m≤1061≤n,m≤10^61≤n,m≤106,1≤k≤3001≤k≤3001≤k≤300
0≤p≤50≤p≤50≤p≤5,
n≤m×kn≤m×kn≤m×k
输入样例1
1000 1200 1
输出样例1
0.200000
输入样例2
1000 100 12
输出样例2
0.029229
样例解释
对于第一组样例,小 LLL 贷款了 100010001000 元,并在一个月后支付 120012001200 元还清了贷款。因此计算月利率 ppp 的公式为 1000×(1+p)=12001000×(1+p)=12001000×(1+p)=1200 或 1200(1+p)=1000\\frac{1200}{(1+p)}=1000(1+p)1200=1000,求出 p=0.200000p=0.200000p=0.200000。
对于第二组样例,小 LLL 贷款了 100010001000 元,并以每月支付 100100100 元的方式在 121212 个月后还清了贷款。由于月利率的存在,他第 kkk 个月偿还的金额只相当于 100(1+p)k\\frac{100}{(1+p)^k}(1+p)k100 元的初始金额,且这121212个月共偿还初始金额100010001000元,求出 p=0.029229p=0.029229p=0.029229。
解题思路
首先重新理解一下题意:
我们一共需要还款nnn元,每个月的还款金额mmm是固定的,分kkk个月还清,题目要求月利率ppp
于是有n=∑i=1km(1+p)kn=\\sum_{i=1}^{k}{\\frac{m}{(1+p)^k}}n=∑i=1k(1+p)km,直观的理解就是虽然我们每月还款金额固定,但所占初始金额的比重越来越小
根据这个计算公式,因为题目给出了m,km,km,k,对于任意的ppp,我们可以计算出相应nnn
如果计算出的nnn值更大,我们应该尝试把ppp上调;反之,把ppp下调
可以看出,二分搜索的算法与这一思路完全吻合
接下来实现代码
题目给出了ppp的搜索区间[0,5][0,5][0,5],停止二分的条件就是精度达到要求,即把答案区间长度收缩到小于10−610^{-6}10−6
double bin_search() {double l = 0.0, r = max_p, m;while (r - l > 1e-6) {m = (l + r) / 2;if (judge(m)) l = m;else r = m;}return l;
}
关于judge
函数的实现,之前已经说过,这里直接展示代码
bool judge(double p) {double down = 1 + p;double sum = 0.0;for (int i = 0; i < k; i++) {sum += m / down;down *= 1 + p;}return sum - n > 0;
}
最后,AC代码如下
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int max_n = 1e6;
const int max_m = 1e6;
const int max_k = 300;
const int max_p = 5;int n, m, k;bool judge(double p) {double down = 1 + p;double sum = 0.0;for (int i = 0; i < k; i++) {sum += m / down;down *= 1 + p;}return sum - n > 0;
}double bin_search() {double l = 0.0, r = max_p, m;while (r - l > 1e-6) {m = (l + r) / 2;if (judge(m)) l = m;else r = m;}return l;
}int main() {cin >> n >> m >> k;cout << setiosflags(ios::fixed) << setprecision(6) << bin_search() << endl;return 0;
}