【算法教程】【C/C++】二分答案——程序设计思路与代码实现

faryou4个月前 (06-15)技术教程

前言

        事实上,我们在解决实际问题时一般会用二分答案而不是二分查找。今天我就来给大家介绍一下二分查找这种由二分法衍生出来的办法。


程序设计思路

        相比于二分查找,二分答案有极为重要的一点不同——check思想。也就是说,每查到一个答案都将其经过特定的程序后再与基准数比较。这样看来,二分答案其实就是在二分查找的基础上加了一步检查。

        二分查找往往是在一堆数里查找答案,而二分答案则通常面对一个范围,这也是它们之间的一显著区别。


代码实现

        解方程中经常会用到二分答案,因为它的范围很广,而且往往包含浮点数答案。来看下面这题:

IMG_20240821_172431.png

        这题目明摆着要我们用二分答案,否则如果用浮点数试过去效率太低,容易TLE。看代码:

#include <bits/stdc++.h>

double a,b,c,d,l,m,r;//a、b、c、d如题意,l、m、r分别为左、中、右指针

double f(double x){//检查解是否合法,算一遍方程
	return a*pow(x,3)+b*pow(x,2)+c*x+d;
}

int main(){
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	for(int i=-100;i<100;i++){//由题意得有200个整数区间,分别查找
		l=i;
		r=i+1;
		if(f(l)==0){//特判,正好相等时直接输出
			printf("%.2lf ",l);
			continue;
		}
		if(f(l)*f(r)>=0) continue;//用题目中所给式子判断
		while(r-l>0.001){//不断缩小范围
			m=(l+r)/2;
			if(f(l)*f(m)<=0) r=m;
			else l=m+0.001;
		}
		printf("%.2lf ",m);
	}
	return 0;
}

        代码中的f()函数就是所谓check思想。这样一来便很好理解了。


结语

        二分答案作为二分算法的一个衍生分支,能够解决很多问题。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/101.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/101.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。