Dado un número entero no negativo N , la tarea es encontrar la N -ésima fila del Triángulo de Pascal .
Nota: El índice de fila comienza desde 0.
Triángulo de Pascal:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Ejemplos:
Entrada: N = 3
Salida: 1, 3, 3, 1
Explicación:
Los elementos en la 3ra fila son 1 3 3 1.Entrada: N = 0
Salida: 1
Enfoque ingenuo:
el enfoque más simple para resolver el problema es usar Recursion . Encuentre la fila del índice anterior primero usando recursividad y luego calcule los valores de la fila actual con la ayuda de la anterior. Repita este proceso hasta la fila N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Nth
// index row in Pascal's triangle
#include <bits/stdc++.h>
using namespace std;
// Function to find the elements
// of rowIndex in Pascal's Triangle
vector<int> getRow(int rowIndex)
{
vector<int> currow;
// 1st element of every row is 1
currow.push_back(1);
// Check if the row that has to
// be returned is the first row
if (rowIndex == 0)
{
return currow;
}
// Generate the previous row
vector<int> prev = getRow(rowIndex - 1);
for(int i = 1; i < prev.size(); i++)
{
// Generate the elements
// of the current row
// by the help of the
// previous row
int curr = prev[i - 1] + prev[i];
currow.push_back(curr);
}
currow.push_back(1);
// Return the row
return currow;
}
// Driver Code
int main()
{
int n = 3;
vector<int> arr = getRow(n);
for(int i = 0; i < arr.size(); i++)
{
if (i == arr.size() - 1)
cout << arr[i];
else
cout << arr[i] << ", ";
}
return 0;
}
// This code is contributed by divyesh072019
Java
// Java Program to find the Nth
// index row in Pascal's triangle
import java.util.ArrayList;
public class geeks {
// Function to find the elements
// of rowIndex in Pascal's Triangle
public static ArrayList<Integer> getRow(
int rowIndex)
{
ArrayList<Integer> currow
= new ArrayList<Integer>();
// 1st element of every row is 1
currow.add(1);
// Check if the row that has to
// be returned is the first row
if (rowIndex == 0) {
return currow;
}
// Generate the previous row
ArrayList<Integer> prev = getRow(rowIndex
- 1);
for (int i = 1; i < prev.size(); i++) {
// Generate the elements
// of the current row
// by the help of the
// previous row
int curr = prev.get(i - 1)
+ prev.get(i);
currow.add(curr);
}
currow.add(1);
// Return the row
return currow;
}
// Driver Program
public static void main(String[] args)
{
int n = 3;
ArrayList<Integer> arr = getRow(n);
for (int i = 0; i < arr.size(); i++) {
if (i == arr.size() - 1)
System.out.print(arr.get(i));
else
System.out.print(arr.get(i)
+ ", ");
}
}
}
Python3
# Python3 program to find the Nth # index row in Pascal's triangle # Function to find the elements # of rowIndex in Pascal's Triangle def getRow(rowIndex) : currow = [] # 1st element of every row is 1 currow.append(1) # Check if the row that has to # be returned is the first row if (rowIndex == 0) : return currow # Generate the previous row prev = getRow(rowIndex - 1) for i in range(1, len(prev)) : # Generate the elements # of the current row # by the help of the # previous row curr = prev[i - 1] + prev[i] currow.append(curr) currow.append(1) # Return the row return currow n = 3 arr = getRow(n) for i in range(len(arr)) : if (i == (len(arr) - 1)) : print(arr[i]) else : print(arr[i] , end = ", ") # This code is contributed by divyeshrabadiya07
C#
// C# program to find the Nth
// index row in Pascal's triangle
using System;
using System.Collections.Generic;
class GFG{
// Function to find the elements
// of rowIndex in Pascal's Triangle
public static List<int> getRow(int rowIndex)
{
List<int> currow = new List<int>();
// 1st element of every row is 1
currow.Add(1);
// Check if the row that has to
// be returned is the first row
if (rowIndex == 0)
{
return currow;
}
// Generate the previous row
List<int> prev = getRow(rowIndex - 1);
for(int i = 1; i < prev.Count; i++)
{
// Generate the elements
// of the current row
// by the help of the
// previous row
int curr = prev[i - 1] + prev[i];
currow.Add(curr);
}
currow.Add(1);
// Return the row
return currow;
}
// Driver code
public static void Main(String[] args)
{
int n = 3;
List<int> arr = getRow(n);
for(int i = 0; i < arr.Count; i++)
{
if (i == arr.Count - 1)
Console.Write(arr[i]);
else
Console.Write(arr[i] + ", ");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the Nth
// index row in Pascal's triangle
// Function to find the elements
// of rowIndex in Pascal's Triangle
function getRow(rowIndex)
{
let currow = [];
// 1st element of every row is 1
currow.push(1);
// Check if the row that has to
// be returned is the first row
if (rowIndex == 0)
{
return currow;
}
// Generate the previous row
let prev = getRow(rowIndex - 1);
for(let i = 1; i < prev.length; i++)
{
// Generate the elements
// of the current row
// by the help of the
// previous row
let curr = prev[i - 1] + prev[i];
currow.push(curr);
}
currow.push(1);
// Return the row
return currow;
}
let n = 3;
let arr = getRow(n);
for(let i = 0; i < arr.length; i++)
{
if (i == arr.length - 1)
document.write(arr[i]);
else
document.write(arr[i] + ", ");
}
</script>
Producción:
1, 3, 3, 1
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Enfoque eficiente:
siga los pasos a continuación para optimizar el enfoque anterior:
- A diferencia del enfoque anterior, solo generaremos los números de la fila N.
- Podemos observar que la fila N del triángulo de Pascal consta de la siguiente secuencia:
NC0, NC1, ......, NCN - 1, NCN
- Dado que N C 0 = 1 , los siguientes valores de la secuencia pueden generarse mediante la siguiente ecuación:
NCr = (NCr - 1 * (N - r + 1)) / r where 1 ≤ r ≤ 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;
// Print the N-th row of the Pascal's Triangle
void generateNthrow(int N)
{
// nC0 = 1
int prev = 1;
cout << prev;
for (int i = 1; i <= N; i++) {
// nCr = (nCr-1 * (n - r + 1))/r
int curr = (prev * (N - i + 1)) / i;
cout << ", " << curr;
prev = curr;
}
}
// Driver Program
int main()
{
int N = 5;
generateNthrow(N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to implement the above approach
#include <stdio.h>
// Print the N-th row of the Pascal's Triangle
void generateNthrow(int N)
{
// nC0 = 1
int prev = 1;
printf("%d", prev);
for (int i = 1; i <= N; i++) {
// nCr = (nCr-1 * (n - r + 1))/r
int curr = (prev * (N - i + 1)) / i;
printf(",%d ", curr);
prev = curr;
}
}
// Driver Program
int main()
{
int N = 5;
generateNthrow(N);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to implement the above approach
import java.io.*;
class GFG{
// Print the N-th row of the
// Pascal's Triangle
static void generateNthrow(int N)
{
// nC0 = 1
int prev = 1;
System.out.print(prev);
for(int i = 1; i <= N; i++)
{
// nCr = (nCr-1 * (n - r + 1))/r
int curr = (prev * (N - i + 1)) / i;
System.out.print(", " + curr);
prev = curr;
}
}
// Driver code
public static void main (String[] args)
{
int N = 5;
generateNthrow(N);
}
}
// This code is contributed by shubhamsingh10
Python3
# Python3 program to implement the above approach
# Print the N-th row of the
# Pascal's Triangle
def generateNthRow (N):
# nC0 = 1
prev = 1
print(prev, end = '')
for i in range(1, N + 1):
# nCr = (nCr-1 * (n - r + 1))/r
curr = (prev * (N - i + 1)) // i
print(",", curr, end = '')
prev = curr
# Driver code
N = 5
# Function calling
generateNthRow(N)
# This code is contributed by himanshu77
C#
// C# program to implement the above approach
using System;
using System.Collections.Generic;
class GFG{
// Print the N-th row of the
// Pascal's Triangle
static void generateNthrow(int N)
{
// nC0 = 1
int prev = 1;
Console.Write(prev);
for(int i = 1; i <= N; i++)
{
// nCr = (nCr-1 * (n - r + 1))/r
int curr = (prev * (N - i + 1)) / i;
Console.Write(", " + curr);
prev = curr;
}
}
// Driver code
public static void Main(String[] args)
{
int N = 5;
generateNthrow(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement the above approach
// Print the N-th row of the
// Pascal's Triangle
function generateNthrow(N)
{
// nC0 = 1
let prev = 1;
document.write(prev);
for(let i = 1; i <= N; i++)
{
// nCr = (nCr-1 * (n - r + 1))/r
let curr = (prev * (N - i + 1)) / i;
document.write(", " + curr);
prev = curr;
}
}
let N = 5;
generateNthrow(N);
// This code is contributed by suresh07.
</script>
Producción:
1, 5, 10, 10, 5, 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aditya23083211 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA