El triángulo de Pascal es una array triangular de los coeficientes binomiales. Escriba una función que tome un valor entero n como entrada e imprima las primeras n líneas del triángulo de Pascal. Las siguientes son las primeras 6 filas del Triángulo de Pascal.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Método 1 (complejidad de tiempo O(n^3))
El número de entradas en cada línea es igual al número de línea. Por ejemplo, la primera línea tiene «1», la segunda línea tiene «1 1», la tercera línea tiene «1 2 1»,… y así sucesivamente. Cada entrada en una línea es el valor de un coeficiente binomial . El valor de la i -ésima entrada en la línea numérica es C (línea, i) . El valor se puede calcular utilizando la siguiente fórmula.
C(line, i) = line! / ( (line-i)! * i! )
Un método simple es ejecutar dos bucles y calcular el valor del coeficiente binomial en el bucle interior.
C++
// C++ code for Pascal's Triangle
#include <iostream>
using namespace std;
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
// for details of this function
int binomialCoeff(int n, int k);
// Function to print first
// n lines of Pascal's
// Triangle
void printPascal(int n)
{
// Iterate through every line and
// print entries in it
for (int line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line
// number
for (int i = 0; i <= line; i++)
cout <<" "<< binomialCoeff(line, i);
cout <<"\n";
}
}
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
// for details of this function
int binomialCoeff(int n, int k)
{
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Driver program
int main()
{
int n = 7;
printPascal(n);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C++ code for Pascal's Triangle
#include <stdio.h>
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
// for details of this function
int binomialCoeff(int n, int k);
// Function to print first
// n lines of Pascal's
// Triangle
void printPascal(int n)
{
// Iterate through every line and
// print entries in it
for (int line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line
// number
for (int i = 0; i <= line; i++)
printf("%d ",
binomialCoeff(line, i));
printf("\n");
}
}
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
// for details of this function
int binomialCoeff(int n, int k)
{
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Driver program
int main()
{
int n = 7;
printPascal(n);
return 0;
}
Java
// Java code for Pascal's Triangle
import java.io.*;
class GFG {
// Function to print first
// n lines of Pascal's Triangle
static void printPascal(int n)
{
// Iterate through every line
// and print entries in it
for (int line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line number
for (int i = 0; i <= line; i++)
System.out.print(binomialCoeff
(line, i)+" ");
System.out.println();
}
}
// Link for details of this function
// https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
static int binomialCoeff(int n, int k)
{
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Driver code
public static void main(String args[])
{
int n = 7;
printPascal(n);
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python 3 code for Pascal's Triangle # A simple O(n^3) # program for # Pascal's Triangle # Function to print # first n lines of # Pascal's Triangle def printPascal(n) : # Iterate through every line # and print entries in it for line in range(0, n) : # Every line has number of # integers equal to line # number for i in range(0, line + 1) : print(binomialCoeff(line, i), " ", end = "") print() # See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/ # for details of this function def binomialCoeff(n, k) : res = 1 if (k > n - k) : k = n - k for i in range(0 , k) : res = res * (n - i) res = res // (i + 1) return res # Driver program n = 7 printPascal(n) # This code is contributed by Nikita Tiwari.
C#
// C# code for Pascal's Triangle
using System;
class GFG {
// Function to print first
// n lines of Pascal's Triangle
static void printPascal(int n)
{
// Iterate through every line
// and print entries in it
for (int line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line number
for (int i = 0; i <= line; i++)
Console.Write(binomialCoeff
(line, i)+" ");
Console.WriteLine();
}
}
// Link for details of this function
// https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
static int binomialCoeff(int n, int k)
{
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Driver code
public static void Main()
{
int n = 7;
printPascal(n);
}
}
/*This code is contributed by vt_m.*/
PHP
<?php
// PHP implementation for
// Pascal's Triangle
// for details of this function
function binomialCoeff($n, $k)
{
$res = 1;
if ($k > $n - $k)
$k = $n - $k;
for ($i = 0; $i < $k; ++$i)
{
$res *= ($n - $i);
$res /= ($i + 1);
}
return $res;
}
// Function to print first
// n lines of Pascal's
// Triangle
function printPascal($n)
{
// Iterate through every line and
// print entries in it
for ($line = 0; $line < $n; $line++)
{
// Every line has number of
// integers equal to line
// number
for ($i = 0; $i <= $line; $i++)
echo "".binomialCoeff($line, $i)." ";
echo "\n";
}
}
// Driver Code
$n=7;
printPascal($n);
// This code is contributed by Mithun Kumar
?>
Javascript
<script>
// Javascript code for Pascal's Triangle
// Function to print first
// n lines of Pascal's Triangle
function printPascal(n)
{
// Iterate through every line
// and print entries in it
for (let line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line number
for (let i = 0; i <= line; i++)
document.write(binomialCoeff
(line, i)+" ");
document.write("<br />");
}
}
// Link for details of this function
// https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
function binomialCoeff(n, k)
{
let res = 1;
if (k > n - k)
k = n - k;
for (let i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// Driver Code
let n = 7;
printPascal(n);
</script>
Producción :
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Espacio Auxiliar: O(1)
La complejidad temporal de este método es O(n^3). Los siguientes son métodos optimizados.
Método 2 (O (n ^ 2) tiempo y O (n ^ 2) espacio adicional)
Si nos acercamos al triángulo, observamos que cada entrada es la suma de los dos valores por encima. Entonces podemos crear una array 2D que almacene valores generados previamente. Para generar un valor en una línea, podemos usar los valores almacenados previamente de la array.
C++
// C++ program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space
// method for Pascal's Triangle
#include <bits/stdc++.h>
using namespace std;
void printPascal(int n)
{
// An auxiliary array to store
// generated pascal triangle values
int arr[n][n];
// Iterate through every line and
// print integer(s) in it
for (int line = 0; line < n; line++)
{
// Every line has number of integers
// equal to line number
for (int i = 0; i <= line; i++)
{
// First and last values in every row are 1
if (line == i || i == 0)
arr[line][i] = 1;
// Other values are sum of values just
// above and left of above
else
arr[line][i] = arr[line - 1][i - 1] +
arr[line - 1][i];
cout << arr[line][i] << " ";
}
cout << "\n";
}
}
// Driver code
int main()
{
int n = 5;
printPascal(n);
return 0;
}
// This code is Contributed by Code_Mech.
C
// C program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space
// method for Pascal's Triangle
void printPascal(int n)
{
// An auxiliary array to store
// generated pascal triangle values
int arr[n][n];
// Iterate through every line and print integer(s) in it
for (int line = 0; line < n; line++)
{
// Every line has number of integers
// equal to line number
for (int i = 0; i <= line; i++)
{
// First and last values in every row are 1
if (line == i || i == 0)
arr[line][i] = 1;
// Other values are sum of values just
// above and left of above
else
arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
printf("%d ", arr[line][i]);
}
printf("\n");
}
}
// Driver code
int main()
{
int n = 5;
printPascal(n);
return 0;
}
Java
// java program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra
// space method for Pascal's Triangle
import java.io.*;
class GFG {
public static void main (String[] args) {
int n = 5;
printPascal(n);
}
public static void printPascal(int n)
{
// An auxiliary array to store generated pascal triangle values
int[][] arr = new int[n][n];
// Iterate through every line and print integer(s) in it
for (int line = 0; line < n; line++)
{
// Every line has number of integers equal to line number
for (int i = 0; i <= line; i++)
{
// First and last values in every row are 1
if (line == i || i == 0)
arr[line][i] = 1;
else // Other values are sum of values just above and left of above
arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
System.out.print(arr[line][i]);
}
System.out.println("");
}
}
}
Python3
# Python3 program for Pascal's Triangle
# A O(n^2) time and O(n^2) extra
# space method for Pascal's Triangle
def printPascal(n:int):
# An auxiliary array to store
# generated pascal triangle values
arr = [[0 for x in range(n)]
for y in range(n)]
# Iterate through every line
# and print integer(s) in it
for line in range (0, n):
# Every line has number of
# integers equal to line number
for i in range (0, line + 1):
# First and last values
# in every row are 1
if(i is 0 or i is line):
arr[line][i] = 1
print(arr[line][i], end = " ")
# Other values are sum of values
# just above and left of above
else:
arr[line][i] = (arr[line - 1][i - 1] +
arr[line - 1][i])
print(arr[line][i], end = " ")
print("\n", end = "")
# Driver Code
n = 5
printPascal(n)
# This code is contributed
# by Sanju Maderna
C#
// C# program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra
// space method for Pascal's Triangle
using System;
class GFG
{
public static void printPascal(int n)
{
// An auxiliary array to store
// generated pascal triangle values
int[,] arr = new int[n, n];
// Iterate through every line
// and print integer(s) in it
for (int line = 0; line < n; line++)
{
// Every line has number of
// integers equal to line number
for (int i = 0; i <= line; i++)
{
// First and last values
// in every row are 1
if (line == i || i == 0)
arr[line, i] = 1;
else // Other values are sum of values
// just above and left of above
arr[line, i] = arr[line - 1, i - 1] +
arr[line - 1, i];
Console.Write(arr[line, i]);
}
Console.WriteLine("");
}
}
// Driver Code
public static void Main ()
{
int n = 5;
printPascal(n);
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program for Pascal’s Triangle
// A O(n^2) time and O(n^2) extra space
// method for Pascal's Triangle
function printPascal($n)
{
// An auxiliary array to store
// generated pascal triangle values
$arr = array(array());
// Iterate through every line and
// print integer(s) in it
for ($line = 0; $line < $n; $line++)
{
// Every line has number of integers
// equal to line number
for ($i = 0; $i <= $line; $i++)
{
// First and last values in every row are 1
if ($line == $i || $i == 0)
$arr[$line][$i] = 1;
// Other values are sum of values just
// above and left of above
else
$arr[$line][$i] = $arr[$line - 1][$i - 1] +
$arr[$line - 1][$i];
echo $arr[$line][$i] . " ";
}
echo "\n";
}
}
// Driver code
$n = 5;
printPascal($n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// javascript program for Pascal's Triangle
// A O(n^2) time and O(n^2) extra
// space method for Pascal's Triangle
var n = 5;
printPascal(n);
function printPascal(n)
{
// An auxiliary array to store generated pascal triangle values
arr = a = Array(n).fill(0).map(x => Array(n).fill(0));
// Iterate through every line and print integer(s) in it
for (line = 0; line < n; line++)
{
// Every line has number of integers equal to line number
for (i = 0; i <= line; i++)
{
// First and last values in every row are 1
if (line == i || i == 0)
arr[line][i] = 1;
else
// Other values are sum of values just above and left of above
arr[line][i] = arr[line-1][i-1] + arr[line-1][i];
document.write(arr[line][i]);
}
document.write("<br>");
}
}
// This code is contributed by 29AjayKumar
</script>
Producción:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Este método se puede optimizar para usar O(n) espacio adicional ya que solo necesitamos valores de la fila anterior. Entonces podemos crear una array auxiliar de tamaño n y sobrescribir valores. El siguiente es otro método que usa solo O (1) espacio adicional.
Método 3 (O(n^2) tiempo y O(1) espacio extra)
Este método se basa en el método 1. Sabemos que la i -ésima entrada en una línea numérica es el coeficiente binomial C(línea, i) y todas las líneas comienzan con valor 1. La idea es calcular C(línea, i) usando C(línea, i-1) . Se puede calcular en tiempo O(1) usando lo siguiente.
C(line, i) = line! / ( (line-i)! * i! ) C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! ) We can derive following expression from above two expressions. C(line, i) = C(line, i-1) * (line - i + 1) / i So C(line, i) can be calculated from C(line, i-1) in O(1) time
C++
// C++ program for Pascal’s Triangle
// A O(n^2) time and O(1) extra space
// function for Pascal's Triangle
#include <bits/stdc++.h>
using namespace std;
void printPascal(int n)
{
for (int line = 1; line <= n; line++)
{
int C = 1; // used to represent C(line, i)
for (int i = 1; i <= line; i++)
{
// The first value in a line is always 1
cout<< C<<" ";
C = C * (line - i) / i;
}
cout<<"\n";
}
}
// Driver code
int main()
{
int n = 5;
printPascal(n);
return 0;
}
// This code is contributed by Code_Mech
C
// C program for Pascal’s Triangle
// A O(n^2) time and O(1) extra space
// function for Pascal's Triangle
void printPascal(int n)
{
for (int line = 1; line <= n; line++)
{
int C = 1; // used to represent C(line, i)
for (int i = 1; i <= line; i++)
{
printf("%d ", C); // The first value in a line is always 1
C = C * (line - i) / i;
}
printf("\n");
}
}
// Driver code
int main()
{
int n = 5;
printPascal(n);
return 0;
}
Java
// Java program for Pascal's Triangle
// A O(n^2) time and O(1) extra
// space method for Pascal's Triangle
import java.io.*;
class GFG {
//Pascal function
public static void printPascal(int n)
{
for(int line = 1; line <= n; line++)
{
int C=1;// used to represent C(line, i)
for(int i = 1; i <= line; i++)
{
// The first value in a line is always 1
System.out.print(C+" ");
C = C * (line - i) / i;
}
System.out.println();
}
}
// Driver code
public static void main (String[] args) {
int n = 5;
printPascal(n);
}
}
// This code is contributed
// by Archit Puri
Python3
# Python3 program for Pascal's Triangle
# A O(n^2) time and O(1) extra
# space method for Pascal's Triangle
# Pascal function
def printPascal(n):
for line in range(1, n + 1):
C = 1; # used to represent C(line, i)
for i in range(1, line + 1):
# The first value in a
# line is always 1
print(C, end = " ");
C = int(C * (line - i) / i);
print("");
# Driver code
n = 5;
printPascal(n);
# This code is contributed by mits
C#
// C# program for Pascal's Triangle
// A O(n^2) time and O(1) extra
// space method for Pascal's Triangle
using System;
class GFG
{
// Pascal function
public static void printPascal(int n)
{
for(int line = 1;
line <= n; line++)
{
int C = 1;// used to represent C(line, i)
for(int i = 1; i <= line; i++)
{
// The first value in a
// line is always 1
Console.Write(C + " ");
C = C * (line - i) / i;
}
Console.Write("\n") ;
}
}
// Driver code
public static void Main ()
{
int n = 5;
printPascal(n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program for Pascal's Triangle
// A O(n^2) time and O(1) extra
// space method for Pascal's Triangle
// Pascal function
function printPascal($n)
{
for($line = 1; $line <= $n; $line++)
{
$C = 1;// used to represent C(line, i)
for($i = 1; $i <= $line; $i++)
{
// The first value in a
// line is always 1
print($C . " ");
$C = $C * ($line - $i) / $i;
}
print("\n");
}
}
// Driver code
$n = 5;
printPascal($n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program for Pascal's Triangle
// A O(n^2) time and O(1) extra
// space method for Pascal's Triangle
//Pascal function
function printPascal(n)
{
for(line = 1; line <= n; line++)
{
var C=1;// used to represent C(line, i)
for(i = 1; i <= line; i++)
{
// The first value in a line is always 1
document.write(C+" ");
C = C * (line - i) / i;
}
document.write("<br>");
}
}
// Driver code
var n = 5;
printPascal(n);
// This code is contributed by 29AjayKumar
</script>
Producción:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Entonces, el método 3 es el mejor método entre todos, pero puede causar un desbordamiento de enteros para valores grandes de n, ya que multiplica dos enteros para obtener valores.
Este artículo fue compilado por Rahul y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA