博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
刷题:《算法笔记》-二分法
阅读量:484 次
发布时间:2019-03-06

本文共 3309 字,大约阅读时间需要 11 分钟。

只知道数据结构的一点皮毛,突然听说有个PAT考试,不管有用没用先报名了,还有一个整月,抱一本《算法笔记》压压惊,祝福我自己>_<。

有时遇到二分问题时脑子不清醒,停止的条件和左右指针如何变化总是乱乱的。作者总结了一个模板。

  • 问题:寻找有序序列中第一个满足某条件的元素的位置。这个条件是从序列左起到右,从不满足条件到开始满足。

例如:

1). 从小到大排序的数列中,从左到右找第一个大于等于x的位置,条件可以设置为

if(A[mid] >= x)

2). 从小到大排序的数列中,从左到右找到第一个大于x的位置,条件可以设置为

if(A[mid]>x)

3). 从大到小排序的数列中,找到最小的一个大于等于x的位置,即从右到左找到第一个大于等于x的位置。相当于从左到右寻找第一个小于x的位置并且-1。条件可以设置为

if(A[mid] < x)//最终返回值为return left -1;

模板为:

int solve(int left,int right){	int mid;	mid = (left + right)/2;	while(left < right){		if(条件成立){			right = mid;		}else{			left = mid + 1;		}		return left;}

等价于

int solve(int left,int right){	int mid;	mid = (left + right)/2;	while(left +1< right){		if(条件成立){			right = mid;		}else{			left = mid;		}		return right;}
  • 问题:查找序列中是否存在满足某条件的元素,用最常用的写法即可
int find(int A[],int left,int right,int x){	int mid;	while(left <= right){		mid = (left + right)/2;		if(A[mid] == x) return mid;		else if (A[mid]  >x){			right = mid-1;		}		else{			left = mid+1;		}	}	return -1;}

两个具体的题目

  1. 木棒切割问题:给出N根木棒,长度均已知,现在希望通过切割它们得到至少K段长度相等的木棒(长度必须是整数),问这些长度相等的木棒最长能有多长。例如三根长度分别为10、24、15的木棒来说,K=7,那么最大长度为 6。
    分析:长度越长,得到的总段数越少;若把长度作为数组的下表,那么数组就是一个由大到小排序。想要找下标最大,即值最小的但 k ≥ K k \geq K kK的值。把条件变成第一个满足条件 k &lt; K k &lt; K k<K的位置。
#include 
int sumk(int A[],int n,int l){ int re=0; for(int i=0;i
  1. 给出N个线段长度,试将它们头尾相接(顺序任意),组合成一个凸多边形,使得该凸多边形的外接圆(即能使凸多边形的所有顶点都在圆周上的圆)的半径最大,求最大半径。其中N不超过 1 0 5 10^5 105,线段长度不超过100,要求算法中不涉及坐标的计算。
    分析:
  • 首先半径一定大于等于最长线段的一半。
  • 这题的意思是这些线段组成的凸多边形的顶点一定能放在某个圆上,我们只需要考虑半径最大就行,不用考虑如何组成的这种图形。
  • 如果圆心在凸多边形的内部,假设最大半径是 r ^ \hat r r^,这时所有的线段对应的圆心角之和为 2 ∗ π 2*\pi 2π
    • 如果半径比 r ^ \hat r r^大,那么这些线段的圆心角之和 s u m &lt; 2 ∗ π sum &lt; 2*\pi sum<2π,线段没法首尾相连的在外接圆上,半径应变小
    • 如果半径比 r ^ \hat r r^小,那么这些线段的圆心角之和 s u m &gt; 2 ∗ π sum &gt; 2*\pi sum>2π,这时构成的外接圆不是半径最大的外接圆,半径应变大
    • 因此可以对半径长度二分,寻找圆心角之和为 2 ∗ π 2*\pi 2π的那个值即可。
  • 如果圆心在凸多边形的外部,假设最大半径是 r ^ \hat r r^,那么最长的线段的圆心角,一定等于其他线段的圆心角之和。取计算目标为 其 他 圆 心 角 和 + 2 π − 最 大 圆 心 角 其他圆心角和 + 2\pi - 最大圆心角 +2π,此时情况取反。
    • 举例,半径4,有圆心角90度的线段长 8 ∗ s i n ( π 4 ) = 5.65 8*sin(\frac{\pi}{4}) = 5.65 8sin(4π)=5.65,两个圆心角45度的线段长 8 ∗ s i n ( π 8 ) = 3.06 8*sin (\frac{\pi}{8}) = 3.06 8sin(8π)=3.06
    • 如果半径变为3,原5.65线段圆心角变为141度;原3.06线段圆心角变为62度;这时 其 他 圆 心 角 − 最 大 圆 心 角 + 2 π &lt; 2 π 其他圆心角 - 最大圆心角 + 2\pi&lt;2\pi +2π<2π,此时半径应变大
const double PI = acos(-1.0);const double eps = 1e-5;//求圆心角之和double totalCornerAngles(double edges[], int n, double r) {	double sum = 0.0;	for (int i = 0; i < n; i++) {		sum += asin(edges[i] / r / 2) * 2;	}	return sum;}//2分求半径double radius(double A[],int n) {	double left,right, mid;	//最大线段的圆心角,剩余线段的圆心角和	double maxangle, other;	//最大线段长	double maxedge = *max_element(A, A + n);	//如果最大线段恰好是直径	double sum = totalCornerAngles(A, n, maxedge / 2);	if (fabs(sum - PI) < eps) {		return max_ridge / 2;	}	//半径应大于最大线段的一半	left = maxedge / 2, right = 100;	//循环求解	while ((right - left) > eps) {		mid = (left + right) / 2;		maxangle = asin(maxedge / 2 / mid) * 2;		sum = totalCornerAngles(A, n, mid);		other = sum - maxangle;		//如果其他圆心角之和小于pi,圆心在多边形外面		if (other < PI) {			sum = other - maxangle + 2 * PI;			if (fabs(sum - 2 * PI) < eps) {				return mid;			}			else if (sum < 2 * PI) {				left = mid;			}			else {				right = mid;			}		}		else {   //否则在内部			if (fabs(sum - 2 * PI) < eps) {				return mid;			}			else if (sum > 2 * PI) {				left = mid;			}			else {				right = mid;			}		}			}}

转载地址:http://xeldz.baihongyu.com/

你可能感兴趣的文章