19 19 19岁的大学生小 L L L 家里情况不好,每月固定生活费不足以买一部苹果手机。当他得知有贷款机构可以贷小额贷款并且可以分期等额还款,每月只需要还几百块时,在虚荣心的驱使下他开始自己的贷款之旅。
贷款机构声称利率按月累计,贷款人在贷款期间每月偿还固定的分期付款金额。
给出小 L L L 贷款的原值为 n n n,分期付款金额 m m m 和分期付款还清贷款所需的总月数 k k k,求该贷款的月利率 p p p。
输入格式
三个用空格隔开的正整数 n n n, m m m, k k k,含义如上述所示。
输出格式
一个实数 p p p,表示该贷款的月利率(用小数表示),和标准输出绝对值不超过 1 0 − 6 10^{−6} 10−6即可。
数据范围
1 ≤ n , m ≤ 1 0 6 1≤n,m≤10^6 1≤n,m≤106, 1 ≤ k ≤ 300 1≤k≤300 1≤k≤300
0 ≤ p ≤ 5 0≤p≤5 0≤p≤5,
n ≤ m × k n≤m×k n≤m×k
输入样例1
1000 1200 1
输出样例1
0.200000
输入样例2
1000 100 12
输出样例2
0.029229
样例解释
对于第一组样例,小 L L L 贷款了 1000 1000 1000 元,并在一个月后支付 1200 1200 1200 元还清了贷款。因此计算月利率 p p p 的公式为 1000 × ( 1 + p ) = 1200 1000×(1+p)=1200 1000×(1+p)=1200 或 1200 ( 1 + p ) = 1000 \frac{1200}{(1+p)}=1000 (1+p)1200=1000,求出 p = 0.200000 p=0.200000 p=0.200000。
对于第二组样例,小 L L L 贷款了 1000 1000 1000 元,并以每月支付 100 100 100 元的方式在 12 12 12 个月后还清了贷款。由于月利率的存在,他第 k k k 个月偿还的金额只相当于 100 ( 1 + p ) k \frac{100}{(1+p)^k} (1+p)k100 元的初始金额,且这 12 12 12个月共偿还初始金额 1000 1000 1000元,求出 p = 0.029229 p=0.029229 p=0.029229。
解题思路
首先重新理解一下题意:
我们一共需要还款 n n n元,每个月的还款金额 m m m是固定的,分 k k k个月还清,题目要求月利率 p p p
于是有 n = ∑ i = 1 k m ( 1 + p ) k n=\sum_{i=1}^{k}{\frac{m}{(1+p)^k}} n=∑i=1k(1+p)km,直观的理解就是虽然我们每月还款金额固定,但所占初始金额的比重越来越小
根据这个计算公式,因为题目给出了 m , k m,k m,k,对于任意的 p p p,我们可以计算出相应 n n n
如果计算出的 n n n值更大,我们应该尝试把 p p p上调;反之,把 p p p下调
可以看出,二分搜索的算法与这一思路完全吻合
接下来实现代码
题目给出了 p p p的搜索区间 [ 0 , 5 ] [0,5] [0,5],停止二分的条件就是精度达到要求,即把答案区间长度收缩到小于 1 0 − 6 10^{-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;
}