トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

8-25 油分け算1 {10,7,3}を{5,5,0}

問題

10リットル入りの容器に油がいっぱい入っており、
他に3リットルと7リットルの容器がある。
これらの容器だけを使って、油を正確に5リットルずつ分けるには
どうすればよいか。

寛永4年の油分け算 : クイズ&パズルの部屋「Quizzical Days.」


ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Youki10;
        internal int Youki07;
        internal int Youki03;
        internal List<string> Log;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Youki10 = 10;
        WillEnqueue.Youki07 = WillEnqueue.Youki03 = 0;
        WillEnqueue.Log = new List<string>();
        WillEnqueue.Log.Add(MakeOneLog(10, 0, 0));
        que.Enqueue(WillEnqueue);

        int MaxLevel = int.MaxValue;
        int AnswerCnt = 0;
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();
            if (MaxLevel < Dequeued.Log.Count) continue;

            if (Dequeued.Youki10 == 5 && Dequeued.Youki07 == 5) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
                Dequeued.Log.ForEach(X => Console.WriteLine(X));
                if (MaxLevel > Dequeued.Log.Count)
                    MaxLevel = Dequeued.Log.Count;
                continue;
            }

            Action<int, int, int> EnqueSyori = (pYouki10, pYouki07, pYouki03) =>
            {
                WillEnqueue.Youki10 = pYouki10;
                WillEnqueue.Youki07 = pYouki07;
                WillEnqueue.Youki03 = pYouki03;

                string NewLog = MakeOneLog(pYouki10, pYouki07, pYouki03);
                if (Dequeued.Log.Contains(NewLog)) return;

                WillEnqueue.Log = new List<string>(Dequeued.Log);
                WillEnqueue.Log.Add(NewLog);
                que.Enqueue(WillEnqueue);
            };

            if (Dequeued.Youki10 > 0) {
                if (Dequeued.Youki07 < 7) {
                    int Aki = 7 - Dequeued.Youki07;
                    int Fill = Math.Min(Aki, Dequeued.Youki10);
                    EnqueSyori(Dequeued.Youki10 - Fill, Dequeued.Youki07 + Fill, Dequeued.Youki03);
                }
                if (Dequeued.Youki03 < 3) {
                    int Aki = 3 - Dequeued.Youki03;
                    int Fill = Math.Min(Aki, Dequeued.Youki10);
                    EnqueSyori(Dequeued.Youki10 - Fill, Dequeued.Youki07, Dequeued.Youki03 + Fill);
                }
            }
            if (Dequeued.Youki07 > 0) {
                if (Dequeued.Youki10 < 10) {
                    int Aki = 10 - Dequeued.Youki10;
                    int Fill = Math.Min(Aki, Dequeued.Youki07);
                    EnqueSyori(Dequeued.Youki10 + Fill, Dequeued.Youki07 - Fill, Dequeued.Youki03);
                }
                if (Dequeued.Youki03 < 3) {
                    int Aki = 3 - Dequeued.Youki03;
                    int Fill = Math.Min(Aki, Dequeued.Youki07);
                    EnqueSyori(Dequeued.Youki10, Dequeued.Youki07 - Fill, Dequeued.Youki03 + Fill);
                }
            }
            if (Dequeued.Youki03 > 0) {
                if (Dequeued.Youki10 < 10) {
                    int Aki = 10 - Dequeued.Youki10;
                    int Fill = Math.Min(Aki, Dequeued.Youki03);
                    EnqueSyori(Dequeued.Youki10 + Fill, Dequeued.Youki07, Dequeued.Youki03 - Fill);
                }
                if (Dequeued.Youki07 < 7) {
                    int Aki = 7 - Dequeued.Youki07;
                    int Fill = Math.Min(Aki, Dequeued.Youki03);
                    EnqueSyori(Dequeued.Youki10, Dequeued.Youki07 + Fill, Dequeued.Youki03 - Fill);
                }
            }
        }
    }

    static string MakeOneLog(int pYouki10, int pYouki07, int pYouki03)
    {
        return string.Format("容器10={0,2},容器7={1},容器3={2}", pYouki10, pYouki07, pYouki03);
    }
}


実行結果

解1を発見しました。
容器10=10,容器7=0,容器3=0
容器10= 3,容器7=7,容器3=0
容器10= 3,容器7=4,容器3=3
容器10= 6,容器7=4,容器3=0
容器10= 6,容器7=1,容器3=3
容器10= 9,容器7=1,容器3=0
容器10= 9,容器7=0,容器3=1
容器10= 2,容器7=7,容器3=1
容器10= 2,容器7=5,容器3=3
容器10= 5,容器7=5,容器3=0


解説

ListジェネリックのContainsメソッドで同じ状態への遷移を防いでます。
MSDN --- List<T>.Containsメソッド