数学上的二分法
对于在区间[a, b]上连续不断且f(a)*f(b) < 0的函数 y = f(x), 通过不断地把函数f(x)的零点所在区间一分为二,使区间的两个端点逐步逼近零点. 进而得到零点近似值的方法叫做二分法(Bisection)
- 递归
double Find_Zero_Point(double left, double right, double precision){
// f(left) * f(right) < 0
if (right - left < precision)
return left;
double mid = (left + right) / 2;
if (f(mid) == 0)
return mid;
if (f(mid) * f(right) > 0)
return Find_Zero_Point(left, mid, precision);
else
return Find_Zero_Point(mid, right, precision);
}- 非递归
double Find_Zero_Point(double left, double right, double precision){
// f(left) * f(right) < 0
while (right - left > precision) {
double mid = (left + right) / 2;
if (f(mid) == 0)
return mid;
if (f(mid) * f(right) > 0)
right = mid;
else
left = mid;
}
return left;
}Level3-4-Q4 一元三次方程求解（P1024 一元三次方程求解）
分析
- 好吧, 暴力枚举[-100, 100], 步长 0.01 也能过. 如果精度再高的话, 枚举就会超时了.
- 还是考虑二分吧. 直接BinarySearch(-100,100)一遍就行吗?
- 两个根之差的绝对值不小于1！！所以，从-100到99循环，每次BinarySearch(i, i + 1.0)才行. 然后注意，如果f(Mid) == 0 和 f(r) == 0, 输出，此处一定要特判，不然有些刚刚好整数的答案出不来
参考代码
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double a, b, c, d;
double ans[3];
double precision = 0.001;
inline double f(double x) {
return a * x * x * x + b * x * x + c * x + d ;
}
void bs(double x1, double x2) {
if((x2 - x1) < precision) {
cout << fixed << setprecision(2) << x1 << " ";
return;
}
double mid = (x1 + x2) / 2;
if((f(mid)) == 0) {
cout << fixed << setprecision(2) << mid << " ";
return;
}
if(f(x2) == 0) {
cout << fixed << setprecision(2) << x2 << " ";
return;
}
if(f(mid) * f(x2) < 0)
bs(mid, x2);
if(f(x1) * f(mid) < 0)
bs(x1, mid);
}
int main()
{
cin >> a >> b >> c >> d;
double x1 = -100, x2 = 100;
for(double x1 = -100; x1 < 100; x1++) {
if(f(x1) * f(x1 + 1.0) <= 0)
bs(x1, x1 + 1.0);
}
return 0;
}
二分答案
前面学习了在有序的数组上进行二分查找和数学上的二分法求零点的解.
还有种问题是二分答案. 就是用二分的方法，在可能的答案区间里找出问题的答案.
典型的使用场景:
- 给定一个评价函数，求评价函数的最小值 / 最大值 。
- 给定一个条件，要求在满足条件的同时，使得代价最小。
- 求最大的最小值 / 求最小的最大值
使用前提:
- 答案在一个固定的区间内(范围很大, 暴力枚举会超时)
- 难以通过搜索来找到符合要求的值, 但给定一个值你可以很快的判断它是不是符合要求
- 可行解对于区间要符合单调性, 因为有序才能二分嘛
模板
最大值最小化 最小值最大化
while(low < high)
{
int mid = (low + high) >> 1;
if(check(mid))
high = mid;
else
low = mid + 1;
}
ans = low; // 左侧值 最小化
ans = low - 1; // 右侧值 最大化近乎万能的整数二分
while(low <= high)
{
int mid = (low + high) >> 1;
if(check(mid)) {
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}浮点数二分模版
while(high - low > eps)//eps为精度
{
double mid = (low + high) >> 1;
if(check(mid))
high = mid;
else
low = mid;
}
ans = low;洛谷P1163 银行贷款
分析
这道题需要一定的财经知识.
假设当前贷款额 m, 月利息是 x, 月还款是 y 的话, 那么这个月的欠款总额是 , 因为会还 y 元, 所以这个月结束的时候欠款是 . 后面的月份同理可以计算. 最后 t 个月后, 欠款额应该是 0.
二分中，需要从 0-5 之间进行二分查找。判断 t 个月后按二分得到的利率下还剩下多少钱没有还。如果剩余的欠款是正数说明利率过大，则从左侧继续二分查找；如果剩余的欠款是负数说明利率过小，则从右侧继续二分查找；如果欠款等于零则输出结束程序。二分查找结束的另一个条件是精度小于0.0001
参考代码
#include <iostream>
#include <iomanip>
using namespace std;
double loan, pay, month;
bool check(double lv)
{
double m = loan;
for(int i = 1; i <= month; i++) {
m = m * ( 1 + lv) - pay;
}
return m > 0;
}
int main()
{
cin >> loan >> pay >> month;
double low = 0, high = 5;
while(high - low >= 0.0001) {
double mid = (low + high) / 2;
if(check(mid)) {
high = mid;
} else {
low = mid;
}
}
cout << fixed << setprecision(1) << low * 100;
return 0;
}洛谷P2678 跳石头
分析
题目很直观了，最小值的最大化。设最小的起跳距离 len, 那么如果两块石头 i-1, i 之间的距离小于 len, 就把第i块拿走. 如果拿走的石头多余 M, 说明 len 太大了, 要取小的那一半继续二分. 如果拿走的石头大于等于M, 那取大的那一半进行尝试更大的 len. 有可能尝试失败的, 所以最终结果是 low – 1.
使用「整数二分模板」更简单些.
参考代码 – 最值模板
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 8;
int l, m, n, d[MAXN];
int ans;
bool check(int len) {
int cnt = 0;
int st = 0;
for(int i = 1; i <= n+1; i++) {
if(d[i] - st >= len) {
st = d[i];
continue;
} else
cnt++;
}
if(cnt > m)
return false;
return true;
}
int main()
{
cin >> l >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> d[i];
}
d[n+1] = l;
int low = 1, high = l+1;
while(low < high) {
int mid = (low + high) >> 1;
if(check(mid))
low = mid + 1;
else
high = mid;
}
cout << low - 1;
return 0;
}参考代码 – 整数二分
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 8;
int l, m, n, d[MAXN];
int ans;
bool check(int len) {
int cnt = 0;
int st = 0;
for(int i = 1; i <= n+1; i++) {
if(d[i] - st >= len) {
st = d[i];
continue;
} else
cnt++;
}
if(cnt > m)
return false;
return true;
}
int main()
{
cin >> l >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> d[i];
}
d[n+1] = l;
int low = 1, high = l+1;
while(low < high) {
int mid = (low + high) >> 1;
if(check(mid)) {
ans = mid;
low = mid + 1;
}
else
high = mid;
}
cout << ans;
return 0;
}总结
- 判断答案是否单调
- 确定二分区间，找准条件
- 判断mid是否满足条件
- 更新答案区间
- 边界为浮点时，循环条件要控制精度，更新区间不能+1