g*l
发帖数: 385 | 1 感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没
有 remingingNuts. 但你在计算 traveled 是假设有 remainingNuts, 可是同时用的
costPerKm是以没有 remainingNuts 来算的. Circular logic?
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are able to travel before you
// reac... 阅读全帖 |
|
i**********e
发帖数: 1145 | 2 其实我之前的帖子有一些错误.
例如，我的假设是integer是错的.
liveInBoston 也犯了这个错误，题目说 N, D, C, F is real numbers.
另外，我也漏了一些细节部分.
例如，忘了处理当中间没油了的情况.
但是基本思路还是对的.
我已经把我解这道题的详细思路 记录在这里:
http://www.ihas1337code.com/2011/01/nuts-in-oasis-interview-que
Below is my output for the sample test cases:
N: 1 D: 1 C: 1 F: 1 maxNuts: 0
N: 1 D: 2 C: 1 F: 1 maxNuts: 0
N: 1 D: 0.25 C: 1 F: 1 maxNuts: 0.75
N: 2 D: 1 C: 1 F: 1 maxNuts: 0.333333
N: ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 3 Straight conversion to iterative version. This would prevent stack from
overflowing.
double getMaxNutsIter(double N, double D, double C, double F) {
while (N > C) {
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are abl... 阅读全帖 |
|
i**********e
发帖数: 1145 | 4 感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没有 remingingNuts.
>> 当 remainingNuts 为零的时候，随即被再次调入 getMaxNuts 函数的时候，不要忘
了有 if (N <= C) 这个 base case 的检查。这时候 N 就是 remaining nuts，也就是
0. 这时候 N <= C 的条件必定满足，然后就检查是不是还有剩下的距离。如果还有的
话，那就返回0，因为马以经走不下去了。
我了解你对递归的不确定而感到困惑。递归的解法就是先从简单的例子开始解，然后由
此获取这个问题 (problem) 中的问题 (subproblems)。递归的难点就在于你怎么从一
个 problem 和另一个 subproblem 里寻找那个关系。只要能证明从这个关系把一个问
题引申到下一个 subproblem，问题就能迎刃而解，不用想的太复杂。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
