递归的应用.doc

文档来源：冰凝呈夏的博客 / 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。Sample Input 275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2Sample Output26.95思路分析： 本题中主要思想的是递归，我的思路是把原点和终点都当成一个站。 判断如果加满油能走几个站，并获取到几个站中的最低价格的站。而真正加油时还要判断加的量是要刚好到站还是加满，因为如果最低价站的价格要比上个加油点的价格高，就在上个站加满油；如果比上个加油点的价格低，那么加油的量能刚好到站就行。程序代码：#include #include #include /用于取小数点后有效两位using namespace std;#define TRUE 1#define FALSE 0struct Pointfloat dis;float pri;int pot;float cango;Point need_judge;float sdis = 0, bot =0, use =0, pri =0;float sum_money=0,oil =0;int canarrive = 1;float check(Point * state,int n,int start_satae);bool IsMin(Point * state,int n,int start_state);void GetMinPrice(Point * state,int n,int start_state);int main()ifstream fin;ofstream fout;int i,n;Point *state;fin.open(2.in);fout.open(2.out);finsdisbotuseprin;cango = bot*use;state = new Pointn+1;state0.dis = 0;state0.pri = pri;state0.pot = 0;for(i = 1;istatei.disstatei.pri;statei.pot = i;staten+1.dis = sdis;staten+1.pri = 0;staten+1.pot = n+1;check(state,n+1,0);if(canarrive)coutsetiosflags(ios:fixed);cout.precision(2);coutsum_moneyendl;elsecoutNo Solution!endl;return 0;float check(Point * state,int n,int start_state)float oil_use;/-获取价格最低的站need_judge = statestart_state+1;GetMinPrice( state,n,start_state);/-/计算到下个需要加油的站的总金额/能走到终点并且是几个站中价格最低的站if( staten.dis -statestart_state.dis cango & IsMin(state,n,start_state) ) if(oil=0)return sum_money += statestart_state.pri * ( (staten.dis -statestart_state.dis )/use);/走不到终点 或者 不是几个站中价格最低的站else if(need_judge.pri statestart_state.pri )sum_money += statestart_state.pri* ( need_judge.dis -statestart_state.dis )/use);oil += ( need_judge.dis -statestart_state.dis )/use-oil);elsesum_money =sum_money + statestart_state.pri* (bot-oil);oil = bot;/到达需加油站的剩余油量oil_use =(need_judge.dis -statestart_state.dis )/use;oil -= oil_use;start_state = need_judge.pot;return check(state, n, start_state);/寻找能走到的加油站中最低价void GetMinPrice(Point * state,int n,int start_state)int sta_n,i,j;for(i=start_state;i=n;i+) /寻找到能走到的站点范围if(i cango)canarrive =0;break;elseif(i statei.dis-statestart_state.dis)sta_n = i; /寻找能走到的加油站中最小值。for(j=start_state;j=sta_n;j+)if(j+1= statej+1.pri & statej+1.pri !=0)need_judge =statej+1;/判断是否为离终点的最低价bool IsMin(Point * state,int n,int start_state)int i,t=1;