十進（ 問 題 ）
-
湖から ４Ｌ の水を汲みたい。 使用できるのは、 ５Ｌの容量の容器１個 と ８Ｌの容量の容器１個 のみである。
１回の行為で出来るのは次の３つのうちのどれかである。
・ １つの容器に水を汲む
・ １つの容器の水を捨てる
・ 一方の容器の水の一部または全部を他方の容器に移す
最低何回の行為で思いを達成することができるか？
-
＜ 小さい容器から大きい容器に水を移していく方法 ＞
５Ｌの容器 ： 5 0 5 2 2 0 5 0 5 4
８Ｌの容器 ： 0 5 5 8 0 2 2 7 7 8
→ 最低 10 回 の行為で達成できる。
＜ 大きい容器から小さい容器に水を移していく方法 ＞
５Ｌの容器 ： 0 5 0 3 3 5 0 5 0 1 1 5
８Ｌの容器 ： 8 3 3 0 8 6 6 1 1 0 8 4
→ 最低 12 回 の行為で達成できる。
したがって、 答えは 「 最低 10 回 の行為で達成できる。」 である。
この問題を一般的にして、 十進BASIC に解かせてみましょう。
-
＜ 小さい容器から大きい容器に水を移していく方法 ＞
５x ＋ ８y ＝ ４ （ x ＞ 0 ，y ＜ 0 ） を満たす整数解（ x，y ）を示せ
という問題の答えを求める方法です。
捨てる方の回数は負の整数、汲む方の回数は正の整数です。
（ x，y ）＝（ 4，−3 ）
＜ 大きい容器から小さい容器に水を移していく方法 ＞
５x ＋ ８y ＝ ４ （ x ＜ 0 ，y ＞ 0 ） を満たす整数解（ x，y ）を示せ
という問題の答えを求める方法です。
捨てる方の回数は負の整数、汲む方の回数は正の整数です。
（ x，y ）＝（ −4，3 ）