Dados N contenedores que consisten en N copias del número A y N copias del número B. Necesitamos ordenar los números en los N contenedores de tal manera que la probabilidad de elegir un contenedor al azar y sacar una copia del número A sea máxima.
Ejemplos:
Input : N = 1 Output : 0.5, Input : N = 2 Output : 0.667
Necesitamos buscar un arreglo óptimo de las N copias del número A y las N copias del número B en N contenedores.
Pi = (Favorable Outcomes) / (Total Outcomes) where Pi denotes the probability of an event i.
Entonces, para maximizar esto, minimizamos el denominador (es decir, los resultados totales) o maximizamos el numerador (es decir, los resultados favorables totales) manteniendo el otro constante.
Considere un arreglo posible donde en los primeros (N-1) contenedores ponemos solo copias del Número A, tal que los primeros (N-1) contenedores contienen (N-1) copias del Número A y ninguna copia del número B. El La copia dejada fuera del número A y las N copias del número B se colocan en el último contenedor.
Probabilidad (copia de A de cualquiera de los primeros (N-1) contenedores) = P n-1 contenedores = 1
Probabilidad (copia de A de N -ésimo contenedor) = P N = 1 ⁄ (N+1)
P max = P N-1 contenedores * (N – 1) + P N
∴ P máx = N / (N + 1)
C++
// CPP program to find maximum probability of
// getting a copy 'A' from N
#include <bits/stdc++.h>
using namespace std;
// Returns the Maximum probability for Drawing
// 1 copy of number A from N containers with N
// copies each of numbers A and B
double calculateProbability(int N)
{
// Pmax = N/(N+1)
double probability = (double)N / (N + 1);
return probability;
}
int main()
{
int N;
double probabilityMax;
// 1. N = 1
N = 1;
probabilityMax = calculateProbability(N);
cout << "Maximum Probability for N = "
<< N << " is, " << setprecision(4)
<< fixed << probabilityMax << endl;
// 2. N = 2
N = 2;
probabilityMax = calculateProbability(N);
cout << "Maximum Probability for N = "
<< N << " is, " << setprecision(4)
<< fixed << probabilityMax << endl;
// 3. N = 10
N = 10;
probabilityMax = calculateProbability(N);
cout << "Maximum Probability for N = "
<< N << " is, " << setprecision(4)
<< fixed << probabilityMax << endl;
return 0;
}
Java
// Java program to find maximum probability of
// getting a copy 'A' from N
class GFG {
// Returns the Maximum probability for Drawing
// 1 copy of number A from N containers with N
// copies each of numbers A and B
static double calculateProbability(int N)
{
// Pmax = N/(N+1)
double probability = (double)N / (N + 1);
return probability;
}
// Driver code
public static void main(String[] args)
{
int N;
double probabilityMax;
// 1. N = 1
N = 1;
probabilityMax = calculateProbability(N);
System.out.println("Maximum Probability for"
+ " N = " + N + " is, " + Math.round(
probabilityMax * 10000.0) / 10000.0);
// 2. N = 2
N = 2;
probabilityMax = calculateProbability(N);
System.out.println("Maximum Probability for N = "
+ N + " is, " + Math.round(
probabilityMax * 10000.0) / 10000.0);
// 3. N = 10
N = 10;
probabilityMax = calculateProbability(N);
System.out.println("Maximum Probability for N = "
+ N + " is, " + Math.round(
probabilityMax * 10000.0) / 10000.0);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find maximum
# probability of getting a copy 'A' from N
# Returns the Maximum probability for
# Drawing 1 copy of number A from N
# containers with N copies each of
# numbers A and B
def calculateProbability(N):
# Pmax = N / (N+1)
probability = N / (N + 1)
return probability
# Driver code
# 1. N = 1
N = 1
probabilityMax = calculateProbability(N)
print("Maximum Probability for N = ",
N , "is, %.4f" %probabilityMax)
# 2. N = 2
N = 2
probabilityMax = calculateProbability(N);
print("Maximum Probability for N =",
N, "is, %.4f" %probabilityMax)
# 3. N = 10
N = 10
probabilityMax = calculateProbability(N);
print("Maximum Probability for N =",
N,"is, %.4f" %probabilityMax)
# This code is contributed by Anant Agarwal.
C#
// C# program to find maximum probability of
// getting a copy 'A' from N
using System;
class GFG {
// Returns the Maximum probability for Drawing
// 1 copy of number A from N containers with N
// copies each of numbers A and B
static double calculateProbability(int N)
{
// Pmax = N/(N+1)
double probability = (double)N / (N + 1);
return probability;
}
//Driver code
public static void Main ()
{
int N;
double probabilityMax;
// 1. N = 1
N = 1;
probabilityMax = calculateProbability(N);
Console.WriteLine("Maximum Probability for N = "
+ N + " is, " +
Math.Round(probabilityMax * 10000.0) / 10000.0);
// 2. N = 2
N = 2;
probabilityMax = calculateProbability(N);
Console.WriteLine("Maximum Probability for N = "
+ N + " is, " +
Math.Round(probabilityMax * 10000.0) / 10000.0);
// 3. N = 10
N = 10;
probabilityMax = calculateProbability(N);
Console.WriteLine("Maximum Probability for N = "
+ N + " is, " +
Math.Round(probabilityMax * 10000.0) / 10000.0);
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to find maximum
// probability of getting a
// copy 'A' from N
// Returns the Maximum probability
// for Drawing 1 copy of number A
// from N containers with N
// copies each of numbers A and B
function calculateProbability($N)
{
// Pmax = N/(N+1)
$probability = $N / ($N + 1);
return $probability;
}
// 1. N = 1
$N = 1;
$probabilityMax = calculateProbability($N);
echo ("Maximum Probability for N = ".
$N . " is, ".
round($probabilityMax, 4). "\n");
// 2. N = 2
$N = 2;
$probabilityMax = calculateProbability($N);
echo ("Maximum Probability for N = " .
$N. " is, " .
round($probabilityMax, 4) . "\n");
// 3. N = 10
$N = 10;
$probabilityMax = calculateProbability($N);
echo ("Maximum Probability for N = " .
$N . " is, " .
round($probabilityMax, 4) . "\n");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program to find maximum probability of
// getting a copy 'A' from N
// Returns the Maximum probability for Drawing
// 1 copy of number A from N containers with N
// copies each of numbers A and B
function calculateProbability(N)
{
// Pmax = N/(N+1)
let probability = N / (N + 1);
return probability;
}
// Driver Code
let N;
let probabilityMax;
// 1. N = 1
N = 1;
probabilityMax = calculateProbability(N);
document.write("Maximum Probability for" +
" N = " + N + " is, " + Math.round(
probabilityMax * 10000.0) / 10000.0 + "<br/>");
// 2. N = 2
N = 2;
probabilityMax = calculateProbability(N);
document.write("Maximum Probability for N = " + N +
" is, " + Math.round(
probabilityMax * 10000.0) / 10000.0 + "<br/>");
// 3. N = 10
N = 10;
probabilityMax = calculateProbability(N);
document.write("Maximum Probability for N = " +
N + " is, " + Math.round(
probabilityMax * 10000.0) / 10000.0 + "<br/>");
// This code is contributed by avijitmondal1998
</script>
Producción:
Maximum Probability for N = 1 is, 0.5000 Maximum Probability for N = 2 is, 0.6667 Maximum Probability for N = 10 is, 0.9091
La Complejidad de Tiempo del programa anterior es O(1).