C++で勝者がプレイする最大ゲーム

問題の説明

トーナメントをしているN人のプレーヤーがいます。勝者がプレイできるゲームの最大数を見つける必要があります。このトーナメントでは、2人のプレーヤーがプレイするゲームの差が1つ以下の場合にのみ、2人のプレーヤーがお互いに対戦することが許可されます

例

3人のプレーヤーがいる場合、次のように勝者を決定するには2つのゲームが必要です-

ゲーム– 1：プレーヤー1とプレーヤー2

ゲーム-2：プレーヤー2対ゲーム-1の勝者

アルゴリズム

• この問題は、勝者がxゲームをプレイするために必要な最小プレーヤー数を最初に計算することで解決できます。これが計算されると、実際の問題はこれの逆になります。ここで、dp[i]が勝者がiゲームをプレイするために必要な最小プレーヤー数を示していると仮定します
• 次点者が（i – 1）ゲームをプレイし、勝者がiゲームをプレイした場合、dp値間の漸化式はdp [i + 1] =dp [i] + dp [i –1]と書くことができます。試合に出場したすべてのプレーヤーは互いに素であり、勝者がプレイしたゲームの合計には、これら2セットのプレーヤーが追加されます。
• 上記の漸化式は、dp [i] =dp [i – 1] + dp [i – 2]と書くことができます。これは、フィボナッチ数列の関係と同じであるため、最終的な答えは、最大フィボナッチ数のインデックスになります。これは、入力内の指定されたプレーヤー数以下です

例

#include <bits/stdc++.h>
using namespace std;
int getMaxGamesToDecideWinner(int n) {
   int dp[n];
   dp[0] = 1;
   dp[1] = 2;
   int idx = 2;
   do {
      dp[idx] = dp[idx - 1] + dp[idx - 2];
   } while(dp[idx++] <= n);
      return (idx - 2);
}
int main() {
   int players = 3;
   cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Maximum games required to decide winner = 2