private static readonly int CAPACITY_MAX = 10; //private static readonly int CAPACITY_MAX = 30; //private static readonly int CAPACITY_MAX = 100; private class State_t { public int Contain1; public int Contain2; public int MovedCount; public string StrAction; public State_t Prev; } private CsvFileWriter Writer; private bool WroteHeader = false; public void Test01() // main { using (Writer = new CsvFileWriter(SCommon.NextOutputPath() + ".csv")) { for (int a = 1; a <= CAPACITY_MAX; a++) { for (int b = a; b <= CAPACITY_MAX; b++) { Test01_a(a, b); } } } } private void Test01_a(int capacity1, int capacity2) { List<State_t> states = new List<State_t>(); states.Add(new State_t() { Contain1 = 0, Contain2 = 0, MovedCount = 0, StrAction = null, Prev = null, }); for (int i = 0; i < states.Count; i++) { State_t curr = states[i]; int nextMovedCount = curr.MovedCount + 1; int transfer1To2 = Math.Min(curr.Contain1, capacity2 - curr.Contain2); int transfer2To1 = Math.Min(capacity1 - curr.Contain1, curr.Contain2); State_t[] nexts = new State_t[] { new State_t() { Contain1 = 0, Contain2 = curr.Contain2, MovedCount = nextMovedCount, StrAction = "桶1を空にする", Prev = curr, }, new State_t() { Contain1 = curr.Contain1, Contain2 = 0, MovedCount = nextMovedCount, StrAction = "桶2を空にする", Prev = curr, }, new State_t() { Contain1 = capacity1, Contain2 = curr.Contain2, MovedCount = nextMovedCount, StrAction = "桶1を満杯にする", Prev = curr, }, new State_t() { Contain1 = curr.Contain1, Contain2 = capacity2, MovedCount = nextMovedCount, StrAction = "桶2を満杯にする", Prev = curr, }, new State_t() { Contain1 = curr.Contain1 - transfer1To2, Contain2 = curr.Contain2 + transfer1To2, MovedCount = nextMovedCount, StrAction = "桶1から桶2へ移せるだけ移す", Prev = curr, }, new State_t() { Contain1 = curr.Contain1 + transfer2To1, Contain2 = curr.Contain2 - transfer2To1, MovedCount = nextMovedCount, StrAction = "桶2から桶1へ移せるだけ移す", Prev = curr, }, }; foreach (State_t next in nexts) if (!states.Any(known => known.Contain1 == next.Contain1 && known.Contain2 == next.Contain2)) states.Add(next); } for (int targetContain = 1; targetContain <= CAPACITY_MAX; targetContain++) { State_t[] reacheds = states.Where(state => state.Contain1 == targetContain || state.Contain2 == targetContain).ToArray(); if (reacheds.Length == 0) continue; int bestMovedCount = reacheds.Select(reached => reached.MovedCount).Min(); State_t best = reacheds.Where(reached => reached.MovedCount == bestMovedCount).First(); if (!WroteHeader) { Writer.WriteCell("桶1の容量"); Writer.WriteCell("桶2の容量"); Writer.WriteCell("目標量"); Writer.WriteCell("最短手数"); Writer.WriteCell("最短手順"); Writer.EndRow(); WroteHeader = true; } Writer.WriteCell(capacity1.ToString()); Writer.WriteCell(capacity2.ToString()); Writer.WriteCell(targetContain.ToString()); Writer.WriteCell(bestMovedCount.ToString()); Writer.WriteCell(string.Join("\r\n", GetRoute(best))); Writer.EndRow(); } } private string[] GetRoute(State_t state) { List<string> dest = new List<string>(); while (state.Prev != null) { dest.Add(string.Format("{0} ({1}, {2}) ⇒ ({3}, {4})" , state.StrAction , state.Prev.Contain1 , state.Prev.Contain2 , state.Contain1 , state.Contain2 )); state = state.Prev; } dest.Reverse(); return dest.ToArray(); }
なんか
・1手でできる操作は6通りあるけど、そのうち3通りだけ使えば攻略できる。
・{ 小さい桶を満杯にする ⇒ 小さい桶から大きい桶へ移せるだけ移す ⇒ 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す } を繰り返せばいずれ目的量に辿り着く。
・↑で辿り着けない量はそもそも量れない。
・桶1と桶2の容量の最大公約数の倍数は量れる。それ以外は量れない。
っぽい。
知らんけど。
↑の検証用(桶の容量100以下)
source:
//private static readonly int CAPACITY_MAX = 10; //private static readonly int CAPACITY_MAX = 30; private static readonly int CAPACITY_MAX = 100; private class State_t { public int Contain1; public int Contain2; } private bool[, ,] Solvables = new bool[CAPACITY_MAX + 1, CAPACITY_MAX + 1, CAPACITY_MAX + 1]; public void Test01() // main { for (int a = 1; a <= CAPACITY_MAX; a++) { for (int b = a; b <= CAPACITY_MAX; b++) { Test01_a(a, b); } } // 以下検証... for (int a = 1; a <= CAPACITY_MAX; a++) { for (int b = 1; b <= CAPACITY_MAX; b++) { for (int c = 0; c <= CAPACITY_MAX; c++) { Test01_b(a, b, c, Solvables[a, b, c]); } } } Console.WriteLine("OK!"); } private void Test01_a(int capacity1, int capacity2) { List<State_t> states = new List<State_t>(); states.Add(new State_t() { Contain1 = 0, Contain2 = 0, }); for (int i = 0; i < states.Count; i++) { State_t curr = states[i]; int transfer1To2 = Math.Min(curr.Contain1, capacity2 - curr.Contain2); int transfer2To1 = Math.Min(capacity1 - curr.Contain1, curr.Contain2); State_t[] nexts = new State_t[] { new State_t() // 桶1を空にする { Contain1 = 0, Contain2 = curr.Contain2, }, new State_t() // 桶2を空にする { Contain1 = curr.Contain1, Contain2 = 0, }, new State_t() // 桶1を満杯にする { Contain1 = capacity1, Contain2 = curr.Contain2, }, new State_t() // 桶2を満杯にする { Contain1 = curr.Contain1, Contain2 = capacity2, }, new State_t() // 桶1から桶2へ移せるだけ移す { Contain1 = curr.Contain1 - transfer1To2, Contain2 = curr.Contain2 + transfer1To2, }, new State_t() // 桶2から桶1へ移せるだけ移す { Contain1 = curr.Contain1 + transfer2To1, Contain2 = curr.Contain2 - transfer2To1, }, }; foreach (State_t next in nexts) if (!states.Any(known => known.Contain1 == next.Contain1 && known.Contain2 == next.Contain2)) states.Add(next); } // 量0は初期状態で完了 Solvables[capacity1, capacity2, 0] = true; Solvables[capacity2, capacity1, 0] = true; // 桶1<=桶2なので逆の場合もセットしておく for (int targetContain = 1; targetContain <= CAPACITY_MAX; targetContain++) { bool solved = states.Any(state => state.Contain1 == targetContain || state.Contain2 == targetContain); if (solved) { Solvables[capacity1, capacity2, targetContain] = true; Solvables[capacity2, capacity1, targetContain] = true; // 桶1<=桶2なので逆の場合もセットしておく } } } private void Test01_b(int capacity1, int capacity2, int targetContain, bool solvable_KITAI) { // ・1手でできる操作は6通りあるけど、そのうち3通りだけ使えば攻略できる // ・{ 小さい桶を満杯にする ⇒ 小さい桶から大きい桶へ移せるだけ移す // ⇒ 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す } を繰り返せばいずれ目的量に辿り着く // ・↑で辿り着けない量はそもそも量れない。 // bool solvable = Test01_c(capacity1, capacity2, targetContain); if (solvable != solvable_KITAI) throw null; // souteigai !!! // ・桶1と桶2の容量の最大公約数の倍数は量れる。それ以外は量れない。 // bool gcdMul = IsGCDMul(capacity1, capacity2, targetContain) && // 桶キャパの最大公約数の倍数か Math.Max(capacity1, capacity2) >= targetContain; // 目的量が桶のキャパ以下であること if (gcdMul != solvable_KITAI) throw null; // souteigai !!! } private bool Test01_c(int capacity1, int capacity2, int targetContain) { if (targetContain == 0) return true; // 量0は初期状態で完了 if (Math.Max(capacity1, capacity2) < targetContain) return false; // 桶のキャパより多い量はそもそも量れないよ！ if (capacity1 > capacity2) SCommon.Swap(ref capacity1, ref capacity2); // capacity1 <= capacity2 となるようにする。 int t1 = 0; int t2 = 0; Action[] actions = new Action[] { // 小さい桶を満杯にする () => { t1 = capacity1; }, // 小さい桶から大きい桶へ移せるだけ移す () => { int transfer = Math.Min(t1, capacity2 - t2); t1 -= transfer; t2 += transfer; }, // 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す () => { if (t2 == capacity2) { t2 = t1; t1 = 0; } }, }; for (; ; ) { foreach (Action a in actions) { a(); // どちらかの桶が目的量になったので_成功 if ( t1 == targetContain || t2 == targetContain ) return true; // 初期状態に戻ってしまったので_失敗 if ( t1 == 0 && t2 == 0 ) return false; } } } private static bool IsGCDMul(int a, int b, int c) // ret: ? c == Multiple of GCD(a, b) { return c % GetGCD(a, b) == 0; } private static int GetGCD(int a, int b) { while (b != 0) { int w = b; b = a % b; a = w; } return a; }
output:
OK!
