16

夜は 4 人の男性が橋を渡らなければなりません。橋を渡る場合は、1 人または 2 人の男性が懐中電灯を携帯する必要があります。懐中電灯は前後に歩く必要があります。投げることはできません。各人は異なる速度で歩きます。1 つは交差するのに 1 分かかり、さらに 2 分、さらに 5 分、最後の 10 分です。2 人の男性が一緒に横断する場合は、より遅い男性のペースで歩かなければなりません。トリックはありません-男性はすべて同じ側から始まり、懐中電灯は遠くを照らすことができず、誰も運ぶことができません.

そして問題は、それらがすべて横断できる最速の速度はどれかということです。私は基本的に、この種の問題に対する一般化されたアプローチを探しています。これはフィボナッチ数列で解決できると友人から言われましたが、その解決策はすべての人に当てはまるわけではありません。

在宅ワークではありませんのでご注意ください。

4

11 に答える 11

19

この問題の一般的なケースを (正式な証明で) 解決するPDF 全体(代替リンク) があります。

于 2009-07-17T16:07:00.163 に答える
17

17 分 - これは典型的な MS の質問です。

1,2 => 2 minutes passed.
1 retuns => 3 minutes passed.
5,10 => 13 minutes passed.
2 returns => 15 minutes passed.
1,2 => 17 minute passed.

一般に、最大の問題/最も遅い人は常にまとめて、遅いリソースを使用せずに毎回光を戻すことができるように、最も速い人を十分に移動させる必要があります。

于 2009-07-17T16:04:52.803 に答える
13

この問題を解決するには、Dice.com に偽の求人広告を掲載し、面接で誰かが正解するまでこの質問をします。

于 2009-07-17T16:08:33.280 に答える
7

ウィキペディアによると

このパズルは、1981 年に『パズルとゲームの超戦略』という本に登場したことが知られています。このバージョンのパズルでは、A、B、C、D が交差するのにそれぞれ 5、10、20、25 分かかり、制限時間は 60 分です。

しかし、この質問は、「富士山をどのように動かしますか?」という本に登場した後、広く知られるようになりました。

この質問は、橋を渡るのにかかる個々の時間が異なる N 人について一般化することができます。

以下のプログラムは、一般的な N 人の人とその時間に対して機能します。

class Program
{
    public static int TotalTime(List<int> band, int n)
    {
        if (n < 3)
        {
            return band[n - 1];
        }
        else if (n == 3)
        {
            return band[0] + band[1] + band[2];
        }
        else
        {
            int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0];
            int temp2 = band[1] + band[0] + band[n - 1] + band[1];

            if (temp1 < temp2)
            {
                return temp1 + TotalTime(band, n - 2);
            }
            else if (temp2 < temp1)
            {
                return temp2 + TotalTime(band, n - 2);
            }
            else
            {
                return temp2 + TotalTime(band, n - 2);
            }
        }
    }

    static void Main(string[] args)
    {
        // change the no of people crossing the bridge
        // add or remove corresponding time to the list
        int n = 4; 

        List<int> band = new List<int>() { 1, 2, 5, 10 };

        band.Sort();

        Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n));
        Console.ReadLine();
    }
}

出力：

橋を渡るのにかかった合計時間: 17

為に、

int n = 5; 
List<int> band = new List<int>() { 1, 2, 5, 10, 12 };

出力：

橋を渡るのにかかった合計時間: 25

為に、

int n = 4; 
List<int> band = new List<int>() { 5, 10, 20, 25 };

OUTPUT 橋を渡るのにかかった合計時間: 60

于 2013-08-08T04:02:20.367 に答える
2

このような小さな問題空間では、すべての可能性の徹底的な検索は簡単です。幅または深さが最初に機能します。CSの簡単な問題です。

私自身は宣教師と人食い人種の問題の方が好きです

于 2009-07-17T16:10:47.893 に答える
1

17 -- 非常によくある質問

-> 1-2 = 2
<- 2 = 2
-> 5,10 = 10 (どれも返す必要はありません)
<- 1 = 1
-> 1,2 = 2

反対側のすべての
合計 = 2+2+10+1+2 = 17

通常、人々は最初の試行で19として取得します

于 2009-07-17T16:06:58.277 に答える
0

私は可能な解決策を代数的に計画し、最速の時間で出てきました. A、B、C、D のリストで代数を割り当てます。ここで、A は最小で、D は最大です。最短時間の式は、B+A+D+B+B または 3B+A+D です。 、2 番目に速い時間 3 の合計であり、最も速いものと最も遅いものを足します。

番組を見ているとアイテム増量の質問もありました。私はそれを行っていませんが、式がまだ適用されると推測しています.2番目のアイテムに3を掛け、2番目に遅い時間を除くすべての合計をすべてのアイテムまで追加するだけです. たとえば、4 つの項目は 3 x 2 番目 + 1 番目と 4 番目であるためです。5 つの項目は 3 x 2 番目 + 1 番目、3 番目、5 番目です。プログラムを使って確認したいと思います。

また、上記で共有されているpdfを見ただけなので、より多くのアイテムについては、3 x秒+最速+後続の各ペアの最も遅い合計の合計です。

最適化されたソリューションの手順を見ると、アイデアは次のとおりです-右-2つのアイテムが右に移動する場合、最速は1番目と2番目に高速です-左-さらに、単一のアイテムに戻るのが最速のアイテム-右-これは、最も遅いアイテムのみを考慮し、2 番目に遅いアイテムは無視します。-左 - 2 番目に速い項目。-最後の右 - 再び 1 番目と 2 番目に速い

もう一度まとめると、2 番目に速いものは 3 回、最も速いものは 1 回、最も遅いものは 2 番目に遅いものになります。

于 2014-12-03T03:31:42.597 に答える
0

簡単なアルゴリズムは次のとおりです。「N」を同時に横断できる人数で、1 人が松明を持って横断しなければならないと仮定します。

  1. 人を第 1 側から第 2 側に移動させるときは、'N' 人の最も遅い歩行者を優先する必要があります。
  2. トーチを第 2 側から第 1 側に移動するには、常に最速の歩行者を使用してください
  3. 人を第 1 側から第 2 側に移動させるときは、次のステップで誰がトーチを持ち帰るかを考慮してください。次のステップでトーチベアラーの速度が、現在のステップで最も遅い「N」人の歩行者のうち、最も速い歩行者と等しい場合は、「1」で指定された「N」人の最も遅い歩行者を選択する代わりに、「N」を選択します。 '最速の歩行者

これを行うサンプルの python スクリプトを次に示します: https://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py

于 2016-12-14T03:59:24.257 に答える