Máximo de juegos jugados por ganador

Hay N jugadores que están jugando un torneo. Necesitamos encontrar el número máximo de juegos que puede jugar el ganador. En este torneo, dos jugadores pueden jugar uno contra el otro solo si la diferencia entre los juegos jugados por ellos no es más de uno.
Ejemplos: 
 

Input  : N = 3
Output : 2
Maximum games winner can play = 2
Assume that player are P1, P2 and P3
First, two players will play let (P1, P2)
Now winner will play against P3, 
making total games played by winner = 2

Input  : N = 4
Output : 2
Maximum games winner can play = 2
Assume that player are P1, P2, P3 and P4
First two pairs will play lets (P1, P2) and 
(P3, P4). Now winner of these two games will 
play against each other, making total games
played by winner = 2

Podemos resolver este problema calculando primero el número mínimo de jugadores necesarios para que el ganador juegue x juegos. Una vez que esto se calcula, el problema real es simplemente el inverso de esto. Ahora suponga que dp[i] denota el número mínimo de jugadores necesarios para que el ganador juegue i juegos. Podemos escribir una relación recursiva entre los valores de dp como, 
dp[i + 1] = dp[i] + dp[i – 1] porque si el finalista ha jugado (i – 1) juegos y el ganador ha jugado i juegos y todos los jugadores contra los que han jugado el partido son disjuntos, el total de juegos jugados por el ganador será la suma de esos dos grupos de jugadores. 
La relación recursiva anterior se puede escribir como dp[i] = dp[i – 1] + dp[i – 2] 
Que es lo mismo que la relación de la serie de Fibonacci, por lo que nuestra respuesta final será el índice del número máximo de Fibonacci que es menor o igual que el número dado de jugadores en la entrada.
 

// C/C++ program to find maximum number of
// games played by winner
#include <bits/stdc++.h>
using namespace std;
 
// method returns maximum games a winner needs
// to play in N-player tournament
int maxGameByWinner(int N)
{
    int dp[N];
 
    // for 0 games, 1 player is needed
    // for 1 game, 2 players are required
    dp[0] = 1;   
    dp[1] = 2;
     
    // loop until i-th Fibonacci number is 
    // less than or equal to N
    int i = 2;
    do {
        dp[i] = dp[i - 1] + dp[i - 2];
    } while (dp[i++] <= N);
 
    // result is (i - 2) because i will be
    // incremented one extra in while loop
    // and we want the last value which is
    // smaller than N, so one more decrement
    return (i - 2);
}
 
// Driver code to test above methods
int main()
{
    int N = 10;
    cout << maxGameByWinner(N) << endl;
    return 0;
}

// Java program to find maximum number of
// games played by winner
class Max_game_winner {
 
    // method returns maximum games a winner needs
    // to play in N-player tournament
    static int maxGameByWinner(int N)
    {
        int[] dp = new int[N];
      
        // for 0 games, 1 player is needed
        // for 1 game, 2 players are required
        dp[0] = 1;   
        dp[1] = 2;
          
        // loop until i-th Fibonacci number is 
        // less than or equal to N
        int i = 2;
        do {
            dp[i] = dp[i - 1] + dp[i - 2];
        } while (dp[i++] <= N);
      
        // result is (i - 2) because i will be
        // incremented one extra in while loop
        // and we want the last value which is
        // smaller than N, so one more decrement
        return (i - 2);
    }
      
    // Driver code to test above methods
    public static void main(String args[])
    {
        int N = 10;
        System.out.println(maxGameByWinner(N));
    }
}
//This code is contributed by Sumit Ghosh

# Python3 program to find maximum
# number of games played by winner
 
# method returns maximum games
# a winner needs to play in
# N-player tournament
 
def maxGameByWinner(N):
    dp = [0 for i in range(N)]
     
    # for 0 games, 1 player is needed
    # for 1 game, 2 players are required
    dp[0] = 1
    dp[1] = 2
     
    # loop until i-th Fibonacci
    # number is less than or
    # equal to N
    i = 1
    while dp[i] <= N:
        i = i + 1
        dp[i] = dp[i - 1] + dp[i - 2]
         
    # result is (i - 1) because i will be
    # incremented one extra in while loop
    # and we want the last value which is
    # smaller than N, so
    return (i - 1)
 
# Driver code
N = 10
print(maxGameByWinner(N))
 
# This code is contributed
# by sahilshelangia

// C# program to find maximum number
// of games played by winner
using System;
 
class GFG {
     
    // method returns maximum games a
    // winner needs to play in N-player
    // tournament
    static int maxGameByWinner(int N)
    {
        int[] dp = new int[N];
     
        // for 0 games, 1 player is needed
        // for 1 game, 2 players are required
        dp[0] = 1;
        dp[1] = 2;
         
        // loop until i-th Fibonacci number
        // is less than or equal to N
        int i = 2;
         
        do {
            dp[i] = dp[i - 1] + dp[i - 2];
        } while (dp[i++] <= N);
     
        // result is (i - 2) because i will be
        // incremented one extra in while loop
        // and we want the last value which is
        // smaller than N, so one more decrement
        return (i - 2);
    }
     
    // Driver code
    public static void Main()
    {
        int N = 10;
        Console.Write(maxGameByWinner(N));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find maximum number
// of games played by winner
 
// Method returns maximum games
// a winner needs to play in
// N-player tournament
function maxGameByWinner($N)
{
    $dp[$N]=0;
 
    // for 0 games, 1 player is needed
    // for 1 game, 2 players are required
    $dp[0] = 1;
    $dp[1] = 2;
     
    // loop until i-th Fibonacci number is
    // less than or equal to N
    $i = 2;
    do
    {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    } while ($dp[$i++] <= $N);
 
    // result is (i - 2) because i will be
    // incremented one extra in while loop
    // and we want the last value which is
    // smaller than N, so one more decrement
    return ($i - 2);
}
 
    // Driver Code
    $N = 10;
    echo maxGameByWinner($N);
 
// This code is contributed by nitin mittal
?>

<script>
 
// Javascript program to find maximum number of
// games played by winner
 
    // method returns maximum games a winner needs
    // to play in N-player tournament
    function maxGameByWinner(N)
    {
        let dp = new Array(N).fill(0);
        
        // for 0 games, 1 player is needed
        // for 1 game, 2 players are required
        dp[0] = 1;   
        dp[1] = 2;
            
        // loop until i-th Fibonacci number is 
        // less than or equal to N
        let i = 2;
        do {
            dp[i] = dp[i - 1] + dp[i - 2];
        } while (dp[i++] <= N);
        
        // result is (i - 2) because i will be
        // incremented one extra in while loop
        // and we want the last value which is
        // smaller than N, so one more decrement
        return (i - 2);
    }
 
// driver program
     
        let N = 10;
        document.write(maxGameByWinner(N));
 
// This code is contributed by code_hunt.
</script>

Producción : 
 

4

Complejidad temporal : O(N) donde N representa el número total de jugadores.

Espacio Auxiliar: O(N)

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.