6

Google で尋ねられたインタビューの質問に出くわしましたが、それは解決できません。

N町から数キロ離れたオアシスにキログラムの穀物の山がありDます。穀物は、最初の場所がオアシスにあるラクダのカートで運ぶ必要があります。カートはC一度にkgの穀物を運ぶことができます。ラクダは穀物を運ぶ際に燃料として使用します。Fkg/km消費します。

X町に輸送できる穀物の最大量 (kg) を計算する関数を作成します。

私は再帰を使おうとしましたが、自分自身を混乱させずに先に進むことはできませんでした.

これが私がこれまでに持っているものです：

number of transports = N / C

fuel amount for distance D = D * F

X = N - ((number of transports) * 2 * (fuel amount for distance D))
4

4 に答える 4

4

N、D、C、および F が入力であると仮定すると、 -

float computeMaxGrains(float N, float D, float C, float F)
{
    //Case when the cart can carry all grains at once
    if(N <= C)
    {
        float remainingGrains = N - D*F;
        if(remainingGrains >= 0)
        {
            return remainingGrains;
        }
        else
        {
            //out of fuel
            return 0;
        }
    }

    // Grains consumed per Km = (Total Number of Trips) * F
    // Total Number of Trips = 2*(N/C) + 1
    float grainsConsumedPerKm = (float) (2*(Math.floor(N/C)) + 1);

    // Remaining grains after Camels fuel = C*(N/C - 1)
    float remainingGrains = (float) (C*(Math.floor(N/C)));

    // Distance that the Camel is able to travel before the camel is 
    // 1 less round trip = 
    // (N - Remaining Grains) / grainsConsumedPerKm
    // From equation N - (grainsConsumedPerKm * distanceTravelled) = 
    // Remaining Grains
    float distanceTravelled = (N - remainingGrains) / grainsConsumedPerKm;

    if(distanceTravelled >= D)
    {
        return N - (D * grainsConsumedPerKm);
    }

    //Use recursion for every 1 less round trip
    return computeMaxGrains(remainingGrains, D-distanceTravelled, C, F);
}
于 2012-11-19T18:49:51.873 に答える
2

この問題は、繰り返し、順方向に処理するのが最善だと思います。判断ポイントを分けていきます。式を 1 つ書く場合は、?: すべての結果の単位は Kg です。

The first question is whether there is enough grain, and cart capacity, to 
justify an initial trip from oasis to town. The camel would eat FD, so 
if FD >= min(N,C) the answer is 0

If FD < min(N,C), the net amount transferred on the initial oasis to town 
trip is min(N,C)-FD. 

The camel is now in town, the remaining grain pile is N-min(N,C), and we 
have to decide whether to send it back again. If C <= 2FD, no round trip
can be profitable.

Otherwise consider a round trip with at least C remaining at the oasis. That 
gains net C-2FD (FD put in the cart in town to keep the camel fed getting 
to the oasis, C-FD remaining in the cart when it gets back to town).

If N>C, we can do floor((N-C)/C) of those round trips, net gain 
floor((N-C)/C)*(C-2FD).

After doing the initial run and any full cart round trips, the remaining 
grain pile is N%C, the remainder on dividing N by C.

If N%C > 2FD it is worth doing a final trip to empty the grain pile, with 
an additional net gain of N%C-2FD.
于 2012-11-19T09:27:38.747 に答える
0

アイデアとして、オアシスに D*F よりも多くの穀物がある場合、ラクダは C kg で移動します。ラクダはそこへの移動で D*F kg を消費し、荷物を降ろします - 2*D*F kg の穀物を降ろし、帰りの旅を正当化するのに十分な穀物が残っていれば戻ってきます。

于 2012-11-19T03:09:58.057 に答える
0

これは単なる推測です。よくわかりません。

G(x) が、供給源から x の距離に輸送される穀物の最大量を表すとします。それで

G(x+1)= (G(x)/C)*(C-2F) + max(F,G(x)%C - F)

ここで、G(0)=N であり、上記の定式化を使用して G(D) を見つける必要があります。

第 2 項 max(F,G(x)%CF) は、

  1. F = 前回の訪問で残りの穀物を収集するために彼が戻ってこなかったとき
  2. G(x)%C - F = 前回の訪問での残りの穀物であり、F を消費して目的地に戻る
于 2012-11-19T08:56:42.923 に答える