Dado N que denota la posición inicial de la persona en la recta numérica. También dado L que es la probabilidad de que la persona vaya a la izquierda. Encuentra la probabilidad de llegar a todos los puntos en la recta numérica después de que N se mueva del punto N. Cada movimiento puede ser hacia la izquierda o hacia la derecha.
Ejemplos:
Entrada: n = 2, l = 0,5
Salida: 0,2500 0,0000 0,5000 0,0000 0,2500 La
persona no puede alcanzar la posición n-1 y n+1 en 2 pases, por lo que la probabilidad es 0. La persona puede alcanzar la posición 0 solo se mueven 2 pasos a la izquierda del índice 2, por lo tanto, la probabilidad de alcanzar el índice 0 es 05 * 0.5 = 0.25. De manera similar para el índice 2n, la probabilidad es 0.25.Entrada: n = 3, l = 0.1
Salida: 0.0010 0.0000 0.0270 0.0000 0.2430 0.0000 0.7290
La persona puede llegar a n-1 de tres maneras, es decir, (llr, lrl, rll) donde l denota izquierda y r denota derecha . Por lo tanto, la probabilidad del índice n-1 es 0,027 . De manera similar, también se calculan las probabilidades para todos los demás puntos.
Enfoque: construya una array arr[n+1][2n+1] donde cada fila representa un paso y las columnas representan los puntos en la línea. Lo máximo que una persona puede moverse del índice N es al índice 0 a la izquierda o al índice 2n a la derecha. Inicialmente, las probabilidades después de una pasada serán a la izquierda para arr[1][n-1] ya la derecha para arr[1][n+1]. Se realizarán los n-1 movimientos que quedan, por lo tanto, los dos movimientos posibles serán n pasos a la derecha o n pasos a la izquierda. Entonces, las relaciones de recurrencia para los movimientos a la derecha y a la izquierda para todos serán:
arr[i][j] += (arr[i – 1][j – 1] * derecha)
arr[i][j] += (arr[i – 1][j + 1] * izquierda)
La suma de probabilidades de todos los movimientos posibles para cualquier índice se almacenará en arr[n][i].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate the
// probability of reaching all points
// after N moves from point N
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the probabilities
void printProbabilities(int n, double left)
{
double right = 1 - left;
// Array where row represent the pass and the
// column represents the points on the line
double arr[n + 1][2 * n + 1] = {{0}};
// Initially the person can reach left
// or right with one move
arr[1][n + 1] = right;
arr[1][n - 1] = left;
// Calculate probabilities for N-1 moves
for (int i = 2; i <= n; i++)
{
// when the person moves from ith index in
// right direction when i moves has been done
for (int j = 1; j <= 2 * n; j++)
arr[i][j] += (arr[i - 1][j - 1] * right);
// when the person moves from ith index in
// left direction when i moves has been done
for (int j = 2 * n - 1; j >= 0; j--)
arr[i][j] += (arr[i - 1][j + 1] * left);
}
// Print the arr
for (int i = 0; i < 2*n+1; i++)
printf("%5.4f ", arr[n][i]);
}
// Driver Code
int main()
{
int n = 2;
double left = 0.5;
printProbabilities(n, left);
return 0;
}
/* This code is contributed by SujanDutta */
Java
// Java program to calculate the
// probability of reaching all points
// after N moves from point N
import java.util.*;
class GFG {
// Function to calculate the probabilities
static void printProbabilities(int n, double left)
{
double right = 1 - left;
// Array where row represent the pass and the
// column represents the points on the line
double[][] arr = new double[n + 1][2 * n + 1];
// Initially the person can reach left
// or right with one move
arr[1][n + 1] = right;
arr[1][n - 1] = left;
// Calculate probabilities for N-1 moves
for (int i = 2; i <= n; i++) {
// when the person moves from ith index in
// right direction when i moves has been done
for (int j = 1; j <= 2 * n; j++) {
arr[i][j] += (arr[i - 1][j - 1] * right);
}
// when the person moves from ith index in
// left direction when i moves has been done
for (int j = 2 * n - 1; j >= 0; j--) {
arr[i][j] += (arr[i - 1][j + 1] * left);
}
}
// Calling function to print the array with probabilities
printArray(arr, n);
}
// Function that prints the array
static void printArray(double[][] arr, int n)
{
for (int i = 0; i < arr[0].length; i++) {
System.out.printf("%5.4f ", arr[n][i]);
}
}
// Driver Code
public static void main(String[] args)
{
int n = 2;
double left = 0.5;
printProbabilities(n, left);
}
}
Python3
# Python3 program to calculate the
# probability of reaching all points
# after N moves from point N
# Function to calculate the probabilities
def printProbabilities(n, left):
right = 1 - left;
# Array where row represent the pass
# and the column represents the
# points on the line
arr = [[0 for j in range(2 * n + 1)]
for i in range(n + 1)]
# Initially the person can reach
# left or right with one move
arr[1][n + 1] = right;
arr[1][n - 1] = left;
# Calculate probabilities
# for N-1 moves
for i in range(2, n + 1):
# When the person moves from ith
# index in right direction when i
# moves has been done
for j in range(1, 2 * n + 1):
arr[i][j] += (arr[i - 1][j - 1] * right);
# When the person moves from ith
# index in left direction when i
# moves has been done
for j in range(2 * n - 1, -1, -1):
arr[i][j] += (arr[i - 1][j + 1] * left);
# Print the arr
for i in range(2 * n + 1):
print("{:5.4f} ".format(arr[n][i]), end = ' ');
# Driver code
if __name__=="__main__":
n = 2;
left = 0.5;
printProbabilities(n, left);
# This code is contributed by rutvik_56
C#
// C# program to calculate the
// probability of reaching all points
// after N moves from point N
using System;
class GFG
{
// Function to calculate the probabilities
static void printProbabilities(int n, double left)
{
double right = 1 - left;
// Array where row represent the pass and the
// column represents the points on the line
double[,] arr = new double[n + 1,2 * n + 1];
// Initially the person can reach left
// or right with one move
arr[1,n + 1] = right;
arr[1,n - 1] = left;
// Calculate probabilities for N-1 moves
for (int i = 2; i <= n; i++)
{
// when the person moves from ith index in
// right direction when i moves has been done
for (int j = 1; j <= 2 * n; j++)
{
arr[i, j] += (arr[i - 1, j - 1] * right);
}
// when the person moves from ith index in
// left direction when i moves has been done
for (int j = 2 * n - 1; j >= 0; j--)
{
arr[i, j] += (arr[i - 1, j + 1] * left);
}
}
// Calling function to print the array with probabilities
printArray(arr, n);
}
// Function that prints the array
static void printArray(double[,] arr, int n)
{
for (int i = 0; i < GetRow(arr,0).GetLength(0); i++)
{
Console.Write("{0:F4} ", arr[n,i]);
}
}
public static double[] GetRow(double[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new double[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
int n = 2;
double left = 0.5;
printProbabilities(n, left);
}
}
/* This code contributed by PrinciRaj1992 */
0.2500 0.0000 0.5000 0.0000 0.2500
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(N 2 )