私はこの質問をされました: Google での同様の質問。フェイスブックのインタビューでも同様の質問がありました。
2/9ナンバーゲームの勝者を決定する
2 人のプレイヤーが次のゲームをプレイします。乱数 N (20 億未満) を選び、1 から始めて、前のターンの数字に 2 または 9 (選択) を掛けます。最初に N に達した人が勝ちます。
候補者は、指定された N によって誰が勝つかを決定する関数を作成する必要があります (最初のプレーヤーか 2 番目のプレーヤーか)。
乗算作業のための 2/9 の基本的なランダムな選択でしょうか、それとも動きを作る際に知性を追加することを望んでいるのでしょうか。例: 2 の掛け算から始めて 9 の掛け算をするのは、他の人が自分よりも早く N に到達できないことがわかったときだけですか?
この種の質問にアプローチする最善の方法は何ですか?
このタイプの質問への最良のアプローチ。
まず、ゲーム理論の基本を理解する必要があります。本当に基本的です。つまり、与えられた数Nに対して、開始したプレーヤーの勝利戦略または対戦相手の勝利戦略のいずれかがあるという事実を意識しています。したがって、彼らは両方とも戦略を知っており、可能な限り最高の動きをしていると想定する必要があります。
次に、ゲームに慣れ始めます。あなたは低レベルで練習します。2-9の場合はスターターが勝ち、10-18の場合は負けなければならないことにすぐに気付きます。したがって、関数はの場合の準備ができていますN<=18。
次に、一般的な勝利戦略について考え始めます。戦略を知ることはあなたにアルゴリズムを与えるでしょう。5分後（早ければ早いほど良い）、勝利戦略を見つけるのに間に合わないことを理解します。その場合は明らかではないからです。それで、あなたはコンピュータにいくつかの基本的な原則を与えて、それがあなたのためにパズルを解くようにすることに決めます。再帰を使用することを知っています。
再帰のルールを見つけようとします。あなたは最後から、または最初から始めたいと思うかもしれません。最後からアプローチを説明します。
ゲームの目的は、対戦相手をゾーンにプッシュすることです。ゾーンでは、対戦相手が勝利を与える必要があります。そして、自分でそのゾーンにプッシュされないでください。N / 9からNまで、勝つためのゾーンがあります。N/9/2とN/9の間からプレイするようにプッシュされた場合、彼は負けなければなりません。（彼の両方の動きが相手を勝利ゾーンに押しやるからです。）それであなたはあなたの関数を書きます：
wins(n) {
// returns 1, if starting player is able to reach
// the range [n, 2*n) with his move
if (n<=18) {
if (n<=9)
return 1;
else
return 0;
} else {
// I must push him to the zone between N/9/2 and N/9
return wins(n/18);
}
その時点に達した場合、あなたは合格しました。floatとintのどちらを使用するか、intを使用して切り上げるか切り捨てるかなど、詳細が残っています。しかし、一般的に、あなたは正しい考え方を示し、インタビュアーと向き合う準備ができています:)
編集：実際には上記のコードに間違いがあります。「勝つ」は「範囲（n、2n）に到達できる」と同じではありません。たぶんここでは2つの機能が必要です：wins(n)とreaches_slightly_above(n)。後者は再帰的に呼び出され、18未満で返される値は異なり、PeterdeRivazのソリューションの値に似ている必要があります。ただし、以下の解決策と一般的なアプローチは問題ありません。
下から上に行く別のアプローチは、次の関数を使用することです。
wins(a,n) {
if (9*a >= n)
// I win easily
return 1;
else
// if one of my moves pushes the opponent to the zone
// where he's not able to win, then I win!
return !wins(2*a, n) || !wins(9*a, n);
}
彼らが求めた場合n、あなたはの値を返しますwin(1,n)。このアルゴリズムの複雑さは明らかではありませんが、対数であると思います。
それらは正確に到達する必要があるため、これはの形式でNある場合にのみ可能であり、そのうちの1つも0にすることができます。N2^a * 9^ba, b
a上記を検索b：の場合a + b = even、2番目のプレーヤーが勝ち、そうでない場合は最初のプレーヤーが勝ちます。
aこれは、各ステップで、プレーヤーがいずれかまたはb1つ、したがって1つに近づくためa + bです。したがって、問題は次のようになります。与えられkた場合、各ステップでプレーヤーがから1を引く必要がある場合k、どのプレーヤーが最初に0に到達しますか？
最適なプレイは、通常、開始時と終了時を除いて、対戦相手の動きの反対をプレイすることです。
再帰的な解法と比較すると、次のように、数値 1 の基数 18 表現の最上位桁に基づいて答えを計算できることがわかります。
def win29(n):
if n<=9: return True
n-=1
while n>=18:
n = n//18
return n==1 or 4<=n<=8
満たそうとするだけでなく、超えようとするだけNでも、さまざまな場合に必ず勝つ戦略を決定することで解決できます。すべてをカバーする 5 つのケース (または 2 つのケース、そのうちの 2 番目のケースには 4 つのサブケースがある) を提示しN、それぞれの勝利戦略を示します。
考えてみてくださいT = ceil( log(N)/log(18) )、それは満たすか超えるTような最小の力です。18^TN
その場合18^(T-1) * 9 < N、最初のプレーヤーは常に理想的な対戦相手に負けます。最初のプレイヤーが 2 を選ぶときはいつでも、2 番目のプレイヤーは 9 を選びます。そして、最初のプレイヤーが 9 を選ぶときはいつでも、2 番目のプレイヤーは 2 を選びますT。勝つ。最初のプレイヤーは前のラウンドで勝つことはできません。なぜなら、9 を掛けても超過するのに十分ではないからですN(つまり、どちらも 2 を掛けていません)。
それでは、そのような18^(T-1) * 9 >= N最小のものを検討して選択しましょう 。4 つの可能性があります。k18^(T-1) * 2^k > Nk = 1, 2, 3, or 4
(k = 1)最初のプレーヤーが勝ちます。最初のプレイヤーは 2 から始めて、2 番目のプレイヤーが上記と同じようにプレイし、最後のラウンドの次のラウンドまで、次の各ターンで他のプレイヤーと反対の数字をプレイします。2 番目のプレイヤーは、常に最初の 2 の 18 倍のパワーに直面します。18^(T-2) * 2 では、プレイヤー 2 はせいぜい18^(T-1)9 を掛けることで到達できますが、これは勝つには不十分であり、18^(T-2)*4で勝つために 9 を掛けることができるプレーヤーの最小値を返し18^(T-1)*2ます。
(k = 3)最初のプレーヤーも勝ちます。今回はプレーヤー 1 が 9 で開始し、以前と同じようにプレーします。2 番目のプレイヤーは、常に最初の 9 の 18 倍のパワーに直面します。18^(T-2) * 9 では、プレイヤー 2 はせいぜい に到達できる18^(T-2) * 9 * 9 < 18^(T-2) * 18 * 8 = 18^(T-1) * 2^3ため、勝つには不十分であり、少なくとも 18^ を返すことができます。 (T-1) 2 を掛けると、どちらのプレイヤーが 9 を掛けて勝ちますか。
(k = 2 or 4)2 番目のプレイヤーが勝ちます。ここで、2 番目のプレーヤーは前と同じように反対の数字を最後までプレイし、各ラウンドのプレーヤー 1 が 18 のパワーで開始する18^(T-2)よう18^(T-2)* 9 < 18^(T-1)にする必要があります。彼が 18^(T-2)*9 を返した場合、プレーヤー 2 は で勝ち、18^(T-2)*9*9 > 18^(T-2)*18*4 = 18^(T-1)*2^2代わりにプレーヤー 1 が を返した場合18^(T-2)*2、プレーヤー 2 は を返し18^(T-2)*4ました。プレーヤー 1 は最大18^(T-2)*4*9 = 18^(T-1)*2で を作ることができますが、それでも十分ではありません。そして、プレイヤー 1 は少なくとも を返すことができます18^(T-2)*8。これは、プレイヤー 2 が18^(T-2)*8*9 = 18^(T-1)*4.
はい、両方のプレーヤーから最適なプレーを考えて、どちらが勝つかを決定することになっています。
ここでは、単純な再帰的思考が解決策につながる可能性があります。
プレーヤーが番号nを持っている場合n*9 >= N、現在のプレーヤーがゲームに勝ちます。
それ以外の場合、彼は または のいずれ2*nか9*nを 2 番目のプレーヤーに渡します。2*n現在、第 1 プレーヤーは、第 2 プレーヤーに提供された両方のオプション9*nが第 2 プレーヤーの当選番号につながる場合にのみゲームに負けます。そうでない場合、彼は再び当選番号を選ぶ可能性があります。
したがって、次のように再帰的なアプローチを書くことができます:
ゲーム内のすべての数値は形式になるため:次の2^i * 9^jように書くことができます:
F(i, j) = true; if (2^i * 9^j * 9) >= N
!(F(i+1, j) && F(i, j+1)); otherwise
F(0, 0)最初のプレーヤーが勝つかどうかに関係なく、解決策は にあります。
There are great answers if N can be divided by 2 and 9, and some good game theory approaches. Here is a simple dynamic programming approach in Javascript to provide the answer for any possible N.
function getWhoWins(n) {
if(getWhichPlayerWins(0, 1, n) === 0) {
console.log("First player wins for " + n);
} else {
console.log("Second player wins for " + n);
}
}
// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
if(currentNumber * 9 >= targetNumber) {
return currentPlayer;
}
var nextPlayer = (currentPlayer + 1) % 2;
if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
return currentPlayer;
}
return nextPlayer;
}
The time complexity of this solution is O(2*logN) = O(logN).
答え（100％確信はありません）：
r = N mod 18
if r belongs to (1,9] player 1 wins
if r belongs to (9,18) or is =1 then player 2 wins.
私は完全な数学的デモンストレーションを持っていないので、間違っている可能性があります。
両方のプレイヤー (または少なくとも 1 人) がプレイ方法を知っている場合、これは正しい答えです。
私は仕事を得ますか？:)
このような 2 人用の決定論的ゲームは、組み合わせゲーム理論によって研究されています。この軽薄なゲーム理論は、経済学で人気のあるノイマンとナッシュのより有用なゲーム理論とは何の関係もありません。影響力のある作品は、Conway、Berlekamp & Guy による Winning Ways という楽しい本です。
考えてみてください。どのゲームでも、次のいずれかです。
あなたのゲームは特別なケースであり、公平なゲームであり、ゲームの状態が両方のプレーヤーに同じように見えます。最良の例は、Nim と呼ばれる単純なマッチ棒ゲームです。すべての公平なゲームは Nim と同等であることが起こります (これは Sprague Grundy の定理です)。したがって、すべての公平なゲームは完全に解決できます。
あなたのゲームを解決しましょう。ゲームの可能な状態は正の整数です。各状態を、2 番目のプレーヤーの勝利 (このようなゲームにはゼロ「0」ゲームとラベルを付ける)、または最初のプレーヤーの勝利 (そのようなゲームにはスター「*」ゲームとラベルを付ける) として分類します。
この時点でゲームは終了しているため、N 以上の整数はすべてゼロ ゲームです。誰が動いたとしても、すでに負けています。
今のターンのプレーヤーが上のゼロ位置に移動できる状態はスター ゲームです。したがって、整数 nN/9 <= n < Nはすべてスター ゲームです。勝利の手は 9 を掛けることです。
やむを得ずスターポジションに移動するしかない状態は、再びゼロポジション。したがって、整数 nN/9/2 <= n < N/9はゼロ位置です。私たちのプレーヤーは負けました。
等々。同様の引数を使用して、最終的にすべての整数を 1 に分類します。
N=1000 の場合、
ピーターの結論に到達する一般化https://stackoverflow.com/a/13367642/284795
興味深い投稿と回答。N <= 2X10^12 (または可能な限り近い) の 2/9 因子を使用してすべての組み合わせパスを列挙する理論的なブルート フォース関数を提案したいと思います。私が「理論的」と言うのは、そのような計算能力が FB を超えていると想定しているからですか?