Dado un número entero N que denota el tamaño de una array, la tarea es encontrar el número de formas posibles de llegar a la esquina inferior derecha desde la esquina superior izquierda de la array sin cruzar la diagonal de la array. Los posibles movimientos desde cualquier celda (i, j) de la array son (i, j + 1) (Derecha) o (i + 1, j) (Abajo).
Ejemplos:
Entrada: N = 4
Salida: 5Entrada: N = 3
Salida: 3
Planteamiento: El problema se puede resolver con base en la siguiente observación:
- Los movimientos permitidos en la array son una celda hacia abajo o hacia la derecha sin cruzar la diagonal.
- Por lo tanto, en cualquier punto, el número de movimientos hacia abajo siempre será mayor o igual que el número de movimientos hacia la derecha.
- Por lo tanto, esto sigue el patrón de los números catalanes .
Por lo tanto, en base a la observación, el problema se reduce a calcular el N Número Catalán . Se considera la ruta calculada solo para el triángulo superior porque no se permite el cruce de la diagonal. Si hay un movimiento de la celda (0, 0) a la (1, 0) resultará en cruce de diagonal.
N º Número Catalán (K n) = ( 2N C N )/(N + 1), donde 2n C n es el coeficiente binomial.
Número total de vías = K n
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// Binomial Coefficient C(n, r)
int binCoff(int n, int r)
{
int val = 1;
int i;
if (r > (n - r)) {
// C(n, r) = C(n, n-r)
r = (n - r);
}
for (i = 0; i < r; i++) {
// [n * (n-1) *---* (n-r+1)] /
// [r * (r-1) *----* 1]
val *= (n - i);
val /= (i + 1);
}
return val;
}
// Function to calculate
// the total possible paths
int findWays(int n)
{
// Update n to n - 1 as (N - 1)
// catalan number is the result
n--;
int a, b, ans;
// Stores 2nCn
a = binCoff(2 * n, n);
// Stores Nth Catalan
// number
b = a / (n + 1);
// Stores the required
// answer
ans = b;
return ans;
}
// Driver Code
int main()
{
int n = 4;
cout << findWays(n);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG {
// Function to calculate
// Binomial Coefficient C(n, r)
static int binCoff(int n, int r)
{
int val = 1;
int i;
if (r > (n - r)) {
// C(n, r) = C(n, n-r)
r = (n - r);
}
for (i = 0; i < r; i++) {
// [n * (n - 1) *---* (n - r + 1)] /
// [r * (r - 1) *----* 1]
val *= (n - i);
val /= (i + 1);
}
return val;
}
// Function to calculate
// the total possible paths
static int findWays(int n)
{
// Update n to n - 1 as (N - 1)
// catalan number is the result
n--;
int a, b, ans;
// Stores 2nCn
a = binCoff(2 * n, n);
// Stores Nth Catalan
// number
b = a / (n + 1);
// Stores the required
// answer
ans = b;
return ans;
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
System.out.print(findWays(n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 Program to implement # the above approach # Function to calculate # Binomial Coefficient C(n, r) def binCoff(n, r): val = 1 if (r > (n - r)): # C(n, r) = C(n, n-r) r = (n - r) for i in range (r): # [n * (n-1) *---* (n-r + 1)] / # [r * (r-1) *----* 1] val *= (n - i) val //= (i + 1) return val # Function to calculate # the total possible paths def findWays(n): # Update n to n - 1 n = n - 1 # Stores 2nCn a = binCoff(2 * n, n) # Stores Nth Catalan # number b = a // (n + 1) # Stores the required # answer ans = b return ans # Driver Code if __name__ == "__main__": n = 4 print(findWays(n)) # This code is contributed by Chitranayal
C#
// C# Program to implement
// the above approach
using System;
class GFG {
// Function to calculate
// Binomial Coefficient C(n, r)
static int binCoff(int n, int r)
{
int val = 1;
int i;
if (r > (n - r)) {
// C(n, r) = C(n, n-r)
r = (n - r);
}
for (i = 0; i < r; i++) {
// [n * (n - 1) *---* (n - r + 1)] /
// [r * (r - 1) *----* 1]
val *= (n - i);
val /= (i + 1);
}
return val;
}
// Function to calculate
// the total possible paths
static int findWays(int n)
{
// Update n to n - 1 as (N - 1)
// catalan number is the result
n--;
int a, b, ans;
// Stores 2nCn
a = binCoff(2 * n, n);
// Stores Nth Catalan
// number
b = a / (n + 1);
// Stores the required
// answer
ans = 2 * b;
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
Console.Write(findWays(n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to calculate
// Binomial Coefficient C(n, r)
function binCoff(n, r)
{
var val = 1;
var i;
if (r > (n - r)) {
// C(n, r) = C(n, n-r)
r = (n - r);
}
for (i = 0; i < r; i++) {
// [n * (n-1) *---* (n-r+1)] /
// [r * (r-1) *----* 1]
val *= (n - i);
val /= (i + 1);
}
return val;
}
// Function to calculate
// the total possible paths
function findWays(n)
{
// Update n to n - 1 as (N - 1)
// catalan number is the result
n--;
var a, b, ans;
// Stores 2nCn
a = binCoff(2 * n, n);
// Stores Nth Catalan
// number
b = a / (n + 1);
// Stores the required
// answer
ans = b;
return ans;
}
// Driver Code
var n = 4;
document.write( findWays(n));
</script>
5
Publicación traducida automáticamente
Artículo escrito por shashanktrivedi02 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA