このようなゲーム (ハノイの塔はもう 1 つの典型的な例です) は、帰納法と再帰の数学的原理を説明するためのものであり、再帰はプログラミングに特に関連しています。
n 個の石の山が勝ちの山か負けた山かを判断したいと思います。直観的に言えば、勝利のパイルとは、対戦相手がどのような順序で選択を行ったとしても、勝利を保証するために常に一定数の石を獲得できるパイルのことです。同様に、負け山とは、あなたがどのような選択をしようとも、常に対戦相手に勝利戦略を残すものです。
明らかに、n = 0は負け組です。あなたはすでに負けています。そして、n = 1は、石を 1 つ取り、相手にn=0を残すため、勝ちの山です。n=2はどうですか？さて、あなたは石を 1 つしか取ることができず、その時点で対戦相手に勝ち山 ( n=1 ) を与えているので、n=2は負け数です。これを数学的により正確にすることができます。
定義:整数nは、n=0の場合、または1 とsqrt(n)の間のすべての整数kに対して敗者であり、nkは勝者です。1 とsqrt(n)の間に整数kが存在し、nkが敗者である場合、整数nは勝者です。
この定義では、nは山のサイズ、kは選択した石の数です。取り除かなければならない有効な数の石が対戦相手に勝利の山を与える場合、その山は負けの山であり、勝利の山とは、何らかの選択で対戦相手に負けの山を与えるものです。
もちろん、その定義は少し不安になるはずです。なぜなら、すでに確認したn=0,1,2以外に意味があるかどうかは実際にはわからないからです。おそらく、勝者と敗者の両方の定義に当てはまる数字、またはどちらの定義にも当てはまらない数字があるでしょう。これは確かに混乱するでしょう。ここで誘導の出番です。
定理:すべての非負の整数は勝者または敗者のいずれかですが、両方ではありません。
証明:強力または完全誘導の原則を使用します。n=0は (定義により) 敗者であることがわかっており、 n=1が勝者で、n=2が敗者であることは既に示しました。これらは私たちの基本的なケースです。
ここで、整数n_0 > 2を考えてみましょう。(強い帰納法を使用して) n_0未満のすべての非負の整数は勝者または敗者のいずれかであると仮定しますが、両方ではありません。s = floor(sqrt(n_0))とし、整数のセットP = {n_0-s, n_0-s+1, ..., n_0 - 1} を考えます。( {1, 2, ..., s}は取り除く石の可能な選択肢のセットであるため、Pは対戦相手に残すことができる山のセットです。) Pの各値は非負であるため、強い帰納法によって、 n_0未満の整数、それぞれが勝者か敗者のどちらかです (両方ではない)。Pのいずれかの値が敗者である場合、定義により、n_0が勝者です (相手が負けた山を残すのに十分な数の石を取り除いたため)。そうでない場合、 Pのすべての値が勝者であるため、n_0は敗者です (何個の石を取っても、対戦相手には勝者の山が残っているため)。したがって、n_0は勝者か敗者のどちらかですが、両方ではありません。
強い帰納法により、すべての非負の整数は勝者または敗者のいずれかであり、両方ではないという結論に達します。
QED
わかりました、あなたが誘導に慣れているなら、それはかなり簡単でした. しかし、私たちが示したのは、私たちの非常に直感的な定義が実際に理にかなっており、得られるすべての山は勝者 (正しくプレイした場合) または敗者 (対戦相手が正しくプレイした場合) のいずれかであるということだけです。どちらがどれであるかをどのように判断しますか？
さて、誘導は再帰につながります。2 つの定義の再帰関数を書きましょう: nは勝者か敗者か? エラー チェックを行わない C ライクな擬似コードを次に示します。
bool is_winner(int n) {
// check all valid numbers of stones to remove (k)
for (int k = 1; k <= sqrt(n); k++) {
if (is_loser(n-k)) {
// I can force the loser n-k on my opponent, so n is a winner
return true;
}
}
// I didn't find a way to force a loser on my opponent, so this must be a loser.
return false;
}
bool is_loser(int n) {
if (n == 0) { // this is our base case
return true;
}
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we found a way to give them a pile that ISN'T a winner, so this isn't a loser
return false;
}
}
// Nope: every pile we can give our opponent is a winner, so this pile is a loser
return true;
}
もちろん、すべての数字が勝者か敗者のどちらかであることは既に示したので、上記のコードはやや冗長です。is_loserしたがって、ただ返すだけ、!is_winnerまたはその逆として実装する方が理にかなっています。おそらくis_winner、スタンドアロンの実装として行うだけです。
bool is_winner(int n) {
if (n < 0) {
// raise error
} else if (n == 0) {
return false; // 0 is a loser
} else {
for (int k = 1; k <= sqrt(n); k++) {
if (!is_winner(n-k)) {
// we can give opponent a loser, this is a winner
return true;
}
}
// all choices give our opponent a winner, this is a loser
return false;
}
}
この関数を使用して質問に答えるには、ゲームがn 個のストーンで始まり、プレイヤー A が最初にプレイし、両方のプレイヤーが最適なプレイをした場合、プレイヤー A が の場合に勝利is_winner(n)し、プレイヤー B が の場合に勝利します!is_winner(n)。彼らのプレイがどうあるべきかを理解するために、勝っているパイルがある場合、 nkが敗者になるような有効なkを選択する必要があります(どれでも問題ありませんが、最大の値がゲームを最速で終了させます)。負け山が与えられます。何を選んでも問題ありません。これが敗者のポイントですが、繰り返しますが、kの最大値を選択すると、ゲームが早く終了します。
これは実際にはパフォーマンスを考慮していません。nは非常に大きくなる可能性があるため、考慮できることがいくつかあります。たとえば、考慮しようとしているnの一般的な小さな値を事前に計算するか、少なくとも単一の再帰呼び出し内でMemoizationを使用します。さらに、前に提案したように、kの最大値を削除すると、ゲームはより少ないターンで終了します。同様に、ループを逆にしてkの最大許容値を最初に確認すると、再帰呼び出しの数を減らすことができるはずです。
もちろん、これを行うための本当に手っ取り早い方法は、もう少し計算をして、勝者か敗者かを決定するnの簡単なプロパティを確認することです。