一道面试题解决方案

一道面试题
今天面试时面试官出了这么一道题：说你在某个起点A,此处有无数个能量块，你要到100公里处的B,你每走1公里消耗1个能量块，而你每次最多携带50个能量块，请问走到B最少需要多少能量块？
谁晓得这类问题的思路呀？？
------解决方案--------------------
至少700个能量块

初始情况（至少有50个能量块可用）
每次选择都消耗掉50个能量块
选择a 不返回一次最远能走50
选择b 要返回一次最远能走25（无意义的浪费）
选择c 要返回还要留下足够下次不返回的能量块
可以设前进距离x 下次来到x这点的时候消耗x个能量块然后在这里补充x个能量块（补满50个）然后回到初始情况
所以有x = 50 - 2x， x = 50/3

可以看出如果通过一系列选择使得前进至50的时候能够补满50个能量块再加一次选择a就可以到达100处即目的地

在距离x处最多补充x的能量块（身上不能超过50）所以第一个补给点是x
同理第二个补给点是2x 第三个补给点是3x
需要一次选择c来存放x个能量块到补给点1
需要三次选择c来存放x个能量块到补给点2 （先通过2次选择c存放2x个能量块到补给点1，然后第三次可以存x个能量块去补给点2）
可以看出这就是个三进制存储
所以要达到距离100 需要三进制（每个补给点为一个数位）的值达到111（即前三个补给点都存放x个能量块）
三进制的111等于十进制的13，这个时候再触发一次选择a共14次选择所以是14*50 = 700个能量块

可以看出要达到50+m*(50/3)的距离（m为整数）最少需要 3^(m-1)+3^(m-2)+...+3^0 次选择c 加上 1次选择a
------解决方案--------------------
我算出来是1350，不知道对不对

#define POWER_MAX 50.0

int transport(double length, int powernum){

	if( length - 0.000001 <= 0){

		return powernum;

	}else if( length + 0.000001 < POWER_MAX/3){

		//return powernum + (((double)powernum/(POWER_MAX - 2*length)) > (int)(powernum/(POWER_MAX - 2*length)) ? (int)(powernum/(POWER_MAX - 2*length)) + 1 : (int)(powernum/(POWER_MAX - 2*length)));

		return powernum + powernum/(POWER_MAX - 2*length)*2*length;

	}else{

		return transport(length - POWER_MAX/3, powernum*3);

	}

}

//length是总路径长度

int getPower(int length){

	int need = 0;


	if( length <= POWER_MAX){

		need = length;

	}else{

		need = transport(length - POWER_MAX, POWER_MAX);

	}


	cout<<need<<endl;

	getchar();

	return need;

}

------解决方案--------------------
我的程序跑出来的是394，抛砖引玉，仅供参考哈：



#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;


/**************************** problem data ****************************/

struct State{

    int pos;

    int energy;

    State(int p, int e) : pos(p), energy(e){}

    friend bool operator < (const State& a, const State& b){

        return a.pos != b.pos ? a.pos < b.pos : a.energy < b.energy;

    }

};

map<State, int> record;   //record how many at least to take from origin to reach this state

map<State, int>::iterator iter;

const int D = 100, K = 50;//0 is start, D is dest, K is the maximum energy to carry once 

                          //while 1 unit step cost 1 unit energy

int previous[D + 1];


/**************************** solve procedure ***************************/

inline int carryInBatches(int from, int energy, int batches, int to)

{

    //Ç°batches - 1´Î¶¼carry K¸öµ¥Î» 

    int left = energy - K * (batches - 1);

    if(left < 1 
------解决方案--------------------
 left > K) return -1;

    return energy - (to - from)*(2*batches - 1);

}

int getPreviousEnergy(int now, int energy, int pre)

{

    int dis = now - pre, backTimes = 0;

    while(true){

        if(carryInBatches(pre, energy + dis*(1+backTimes*2), backTimes+1, now) == energy)

            break;

        ++backTimes;

    }

    return energy + dis*(1+backTimes*2);

}

int howmany(int pos, int energy)

{

    if(pos == 0) return energy;

    iter = record.find(State(pos, energy));

    if(iter != record.end()) return iter->second;

    

    int takeFromOrigin = 0x7FFFFFFF;

    int limit = max(0, energy > 0 ? pos - (K+1)/2 + 1 : pos - K);

    for(int pre = pos - 1; pre >= limit; --pre){

一道面试题解决方案

相关推荐