算法设计与分析---减治法实验
实验题目：
甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。
【输入】
仅一行，三个数据分别表示AB两地的距离s，人的步行速度a，车的速度b。
【输出】
两人同时到达B地需要的最短时间。
【样例】
输入：
120 5 25
输出
9.60
提示：
- 最优方案是：小车先载甲到某个地方K，然后回头接乙，关键是K的求取
- 假设t1,t2分别表示甲乙从A到B的时间，当K从A移动到B，t1减少，t2增加，当t1=t2时，即为问题的解
- 求解方法可参考折半查找的思路
代码：
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
double s,a,b;
cin>>s;
cin>>a;
cin>>b;
int n=1;
while(n--)
{double t1=0,t2=0; //t1为甲从A到达B所用时间,t2为乙方从A到达B所用时间
double k1=0,k2=s,k=0;
do{
k=(k1+k2)/2;
t1=k/b+(s-k)/a;
t2=k/b+k/(a+b)+(s-a*(k/b+k/(a+b)))/b;
if (t1<t2) //比较t1和t2大小
{
k2=k;
}
else
{
k1=k;
}
}while (fabs(t1-t2)>1); //满足精度要求
cout<<t1<<endl;
}
return 0;
}
运行截图：