Рубрики

Треугольник Паскаля

Треугольник Паскаля представляет собой треугольный массив биномиальных коэффициентов. Напишите функцию, которая принимает целочисленное значение n в качестве входных данных и печатает первые n строк треугольника Паскаля. Ниже приведены первые 6 рядов треугольника Паскаля.

1  
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 

Способ 1 (O (n ^ 3) сложность времени)
Количество записей в каждой строке равно номеру строки. Например, в первой строке указано «1», во второй строке — «1 1», в третьей строке — «1 2 1», … и т. Д. Каждая запись в строке является значением биномиального коэффициента . Значение i- й записи в строке номера строки равно C (line, i) . Значение можно рассчитать по следующей формуле.

C(line, i)   = line! / ( (line-i)! * i! ) 

Простой метод — запустить два цикла и вычислить значение биномиального коэффициента во внутреннем цикле.

C ++

// C ++ код для треугольника Паскаля
#include <stdio.h>

  
// См. Https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/amp/
// для деталей этой функции

int binomialCoeff(int n, int k);

  
// Функция для печати первой
// n строк Паскаля
// Треугольник

void printPascal(int n)

{

    // перебираем каждую строку и

    // печатаем записи в нем

    for (int line = 0; line < n; line++)

    {

        // Каждая строка имеет номер

        // целые числа равны строке

        // число

        for (int i = 0; i <= line; i++)

            printf("%d ",

                    binomialCoeff(line, i));

        printf("\n");

    }

}

  
// См. Https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/amp/
// для деталей этой функции

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;

}

  
// Драйвер программы

int main()

{

    int n = 7;

    printPascal(n);

    return 0;

}

Джава

// Java-код для треугольника Паскаля

import java.io.*;

  

class GFG {

      

    // Функция для печати первой

    // n линий треугольника Паскаля

    static void printPascal(int n)

    {

          

    // перебираем каждую строку

    // и печатаем записи в нем

    for (int line = 0; line < n; line++)

    {

        // Каждая строка имеет номер

        // целые числа равны номеру строки

        for (int i = 0; i <= line; i++)

        System.out.print(binomialCoeff

                        (line, i)+" ");

                          

        System.out.println();

    }

    }

      

    // Ссылка на детали этой функции

    // https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/amp/

    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;

    }

      

    // Код драйвера

    public static void main(String args[])

    {

    int n = 7;

    printPascal(n);

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Python 3 код для треугольника Паскаля
# Простая O (n ^ 3)
# программа для
# Треугольник Паскаля

  
# Функция для печати
# первые n строк
# Треугольник Паскаля

def printPascal(n) :

      

    # Перебирать каждую строку

    # и распечатать записи в нем

    for line in range(0, n) :

          

        # Каждая строка имеет номер

        # целые числа равны строке

        # число

        for i in range(0, line + 1) :

            print(binomialCoeff(line, i),

                " ", end = "")

        print()

      

  
# См. Https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/amp/
# для деталей этой функции

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

  
# Драйверная программа

n = 7

printPascal(n)

  

  
# Этот код предоставлен Никитой Тивари.

C #

// код C # для треугольника Паскаля

using System;

  

class GFG {

      

    // Функция для печати первой

    // n линий треугольника Паскаля

    static void printPascal(int n)

    {

          

    // перебираем каждую строку

    // и печатаем записи в нем

    for (int line = 0; line < n; line++)

    {

        // Каждая строка имеет номер

        // целые числа равны номеру строки

        for (int i = 0; i <= line; i++)

        Console.Write(binomialCoeff

                        (line, i)+" ");

                          

        Console.WriteLine();

    }

    }

      

    // Ссылка на детали этой функции

    // https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/amp/

    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;

    }

      

    // Код драйвера

    public static void Main()

    {

    int n = 7;

    printPascal(n);

    }

}

  
/ * Этот код предоставлен vt_m. * /

PHP

<?php
// Реализация PHP для
// Треугольник Паскаля

  
// для деталей этой функции

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;

}

  
// Функция для печати первой
// n строк Паскаля
// Треугольник

function printPascal($n)

{

    // перебираем каждую строку и

    // печатаем записи в нем

    for ($line = 0; $line < $n; $line++)

    {

        // Каждая строка имеет номер

        // целые числа равны строке

        // число

        for ($i = 0; $i <= $line; $i++)

                echo "".binomialCoeff($line, $i)." ";

                  

        echo "\n";

    }

}

  
// Код драйвера

$n=7;

printPascal($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 

Временная сложность этого метода O (n ^ 3). Ниже приведены оптимизированные методы.

Метод 2 (O (n ^ 2) время и O (n ^ 2) дополнительное пространство)
Если мы подойдем ближе к треугольнику, мы увидим, что каждая запись является суммой двух значений над ней. Таким образом, мы можем создать 2D-массив, в котором хранятся ранее сгенерированные значения. Чтобы сгенерировать значение в строке, мы можем использовать ранее сохраненные значения из массива.

C ++

// C ++ программа для треугольника Паскаля
// AO (n ^ 2) время и O (n ^ 2) дополнительное пространство
// метод для треугольника Паскаля
#include <bits/stdc++.h>

using namespace std;

  

void printPascal(int n)

{

      

    // Вспомогательный массив для хранения

    // генерируемые значения треугольника пскала

    int arr[n][n]; 

  

    // перебираем каждую строку и

    // напечатать в нем целое число

    for (int line = 0; line < n; line++)

    {

        // Каждая строка имеет количество целых чисел

        // равно номеру строки

        for (int i = 0; i <= line; i++)

        {

        // Первое и последнее значения в каждой строке равны 1

        if (line == i || i == 0)

            arr[line][i] = 1;

        // Другие значения являются просто суммой значений

        // вверху и слева вверху

        else

            arr[line][i] = arr[line - 1][i - 1] + 

                            arr[line - 1][i];

        cout << arr[line][i] << " ";

        }

        cout << "\n";

    }

}

  
// Код драйвера

int main()

{

    int n = 5;

    printPascal(n);

    return 0;

}

  
// Этот код предоставлен Code_Mech.

С

// C программа для треугольника Паскаля
// AO (n ^ 2) время и O (n ^ 2) дополнительное пространство
// метод для треугольника Паскаля

void printPascal(int n)

{
// Вспомогательный массив для хранения
// генерируемые значения треугольника пскала

int arr[n][n]; 

  
// Перебираем каждую строку и печатаем в ней целые числа

for (int line = 0; line < n; line++)

{

    // Каждая строка имеет количество целых чисел

    // равно номеру строки

    for (int i = 0; i <= line; i++)

    {

    // Первое и последнее значения в каждой строке равны 1

    if (line == i || i == 0)

        arr[line][i] = 1;

    // Другие значения являются просто суммой значений

    // вверху и слева вверху

    else 

        arr[line][i] = arr[line-1][i-1] + arr[line-1][i];

    printf("%d ", arr[line][i]);

    }

    printf("\n");

}
}
// Код драйвера

int main()

{

int n = 5;

    printPascal(n);

    return 0;

}

Джава

// Java-программа для треугольника Паскаля
// AO (n ^ 2) время и O (n ^ 2) дополнительно
// космический метод для треугольника Паскаля

import java.io.*;

  

class GFG {

    public static void main (String[] args) {

        int n = 5;

        printPascal(n);

    }

  

public static void printPascal(int n)

{
// Вспомогательный массив для хранения сгенерированных значений треугольника Паскаля

int[][] arr = new int[n][n]; 

  
// Перебираем каждую строку и печатаем в ней целые числа

for (int line = 0; line < n; line++)

{

    // Каждая строка имеет число целых чисел, равное номеру строки

    for (int i = 0; i <= line; i++)

    {

    // Первое и последнее значения в каждой строке равны 1

    if (line == i || i == 0)

        arr[line][i] = 1;

    else // Другие значения являются суммой значений чуть выше и выше слева

        arr[line][i] = arr[line-1][i-1] + arr[line-1][i];

    System.out.print(arr[line][i]);

    }

    System.out.println("");

}
}
}

python3

# Python3 программа для треугольника Паскаля

  
# AO (n ^ 2) время и O (n ^ 2) дополнительно
# космический метод для треугольника Паскаля

def printPascal(n:int):

  

    # Вспомогательный массив для хранения

    # генерируемые значения треугольника Паскаля

    arr = [[0 for x in range(n)] 

              for y in range(n)] 

  

    # Перебирать каждую строку

    # и выведите в нем целое число

    for line in range (0, n):

  

        # Каждая строка имеет номер

        # целые числа, равные номеру строки

        for i in range (0, line + 1):

  

            # Первое и последнее значения

            # в каждом ряду 1

            if(i is 0 or i is line):

                arr[line][i] = 1

                print(arr[line][i], end = " "

  

            # Другие значения являются суммой значений

            # чуть выше и выше слева

            else:

                arr[line][i] = (arr[line - 1][i - 1] + 

                                arr[line - 1][i])

                print(arr[line][i], end = " ")             

        print("\n", end = "")

  
Код водителя

n = 5

printPascal(n)

  
# Этот код добавлен
# Санджу Мадерна

C #

// C # программа для треугольника Паскаля
// AO (n ^ 2) время и O (n ^ 2) дополнительно
// космический метод для треугольника Паскаля

using System;

  

class GFG 

{

public static void printPascal(int n)

{

      
// Вспомогательный массив для хранения
// сгенерированные значения треугольника Паскаля

int[,] arr = new int[n, n]; 

  
// перебираем каждую строку
// и вывести в нем целое число

for (int line = 0; line < n; line++)

{

    // Каждая строка имеет номер

    // целые числа равны номеру строки

    for (int i = 0; i <= line; i++)

    {

          

    // Первые и последние значения

    // в каждом ряду 1

    if (line == i || i == 0)

        arr[line, i] = 1;

    else // Другие значения являются суммой значений

         // чуть выше и выше слева

        arr[line, i] = arr[line - 1, i - 1] + 

                       arr[line - 1, i];

    Console.Write(arr[line, i]);

    }

Console.WriteLine("");

}
}

  
// Код драйвера

public static void Main () 

{

    int n = 5;

    printPascal(n);

}
}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

<?php
// PHP программа для треугольника Паскаля
// AO (n ^ 2) время и O (n ^ 2) дополнительное пространство
// метод для треугольника Паскаля

function printPascal($n)

{

    // Вспомогательный массив для хранения

    // генерируемые значения треугольника пскала

    $arr = array(array()); 

      

    // перебираем каждую строку и

    // напечатать в нем целое число

    for ($line = 0; $line < $n; $line++)

    {

        // Каждая строка имеет количество целых чисел

        // равно номеру строки

        for ($i = 0; $i <= $line; $i++)

        {

            // Первое и последнее значения в каждой строке равны 1

            if ($line == $i || $i == 0)

                $arr[$line][$i] = 1;

                  

            // Другие значения являются просто суммой значений

            // вверху и слева вверху

            else

                $arr[$line][$i] = $arr[$line - 1][$i - 1] + 

                                $arr[$line - 1][$i];

            echo $arr[$line][$i] . " ";

        }

        echo "\n";

    }

}

  
// Код драйвера

$n = 5;

printPascal($n);

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 

Этот метод может быть оптимизирован для использования O (n) дополнительного пространства, так как нам нужны значения только из предыдущей строки. Таким образом, мы можем создать вспомогательный массив размера n и перезаписать значения. Ниже приведен другой метод, использующий только O (1) дополнительное пространство.

Метод 3 (O (n ^ 2) время и O (1) дополнительное пространство)
Этот метод основан на методе 1. Мы знаем, что i- я запись в строке номера строки является биномиальным коэффициентом C (line, i), и все строки начинаются со значения 1. Идея состоит в том, чтобы вычислить C (line, i), используя C ( линия, я-1) . Его можно рассчитать за время O (1), используя следующее.

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 ++ программа для треугольника Паскаля
// AO (n ^ 2) время и O (1) дополнительное пространство
// функция для треугольника Паскаля
#include <bits/stdc++.h>

  

using namespace std;

void printPascal(int n)

{

      

for (int line = 1; line <= n; line++)

{

    int C = 1; // используется для представления C (line, i)

    for (int i = 1; i <= line; i++) 

    {

          

        // Первое значение в строке всегда 1

        cout<< C<<" "

        C = C * (line - i) / i; 

    }

    cout<<"\n";

}
}

  
// Код драйвера

int main()

{

    int n = 5;

    printPascal(n);

    return 0;

}

  
// Этот код предоставлен Code_Mech

С

// C программа для треугольника Паскаля
// AO (n ^ 2) время и O (1) дополнительное пространство
// функция для треугольника Паскаля

void printPascal(int n)

{

for (int line = 1; line <= n; line++)

{

    int C = 1; // используется для представления C (line, i)

    for (int i = 1; i <= line; i++) 

    {

    printf("%d ", C); // Первое значение в строке всегда 1

    C = C * (line - i) / i; 

    }

    printf("\n");

}
}
// Код драйвера

int main()

{

int n = 5;

    printPascal(n);

    return 0;

}

Джава

// Java-программа для треугольника Паскаля
// AO (n ^ 2) время и O (1) дополнительно
// космический метод для треугольника Паскаля

import java.io.*;

class GFG {

  
// функция Паскаля

public static void printPascal(int n)

{

    for(int line = 1; line <= n; line++)

    {

          

    int C=1;// используется для представления C (line, i)

    for(int i = 1; i <= line; i++)

    

        // Первое значение в строке всегда 1

        System.out.print(C+" ");

        C = C * (line - i) / i; 

    }

    System.out.println();

    }

}

  
// Код драйвера

public static void main (String[] args) {

    int n = 5;

    printPascal(n);


}
// Этот код добавлен
// от Archit Puri

python3

# Python3 программа для треугольника Паскаля
# AO (n ^ 2) время и O (1) дополнительно
# космический метод для треугольника Паскаля

  
# Функция Паскаля

def printPascal(n): 

  

    for line in range(1, n + 1): 

        C = 1; # используется для представления C (строка, я)

        for i in range(1, line + 1): 

              

            # Первое значение в

            # строка всегда 1

            print(C, end = " "); 

            C = int(C * (line - i) / i); 

        print(""); 

  
# Код драйвера

n = 5

printPascal(n);

  
# Этот код предоставлен mits

C #

// C # программа для треугольника Паскаля
// AO (n ^ 2) время и O (1) дополнительно
// космический метод для треугольника Паскаля

using System;

class GFG 

  
// функция Паскаля

public static void printPascal(int n) 

    for(int line = 1; 

            line <= n; line++) 

    

          

    int C = 1;// используется для представления C (line, i)

    for(int i = 1; i <= line; i++) 

    

        // Первое значение в

        // строка всегда 1

        Console.Write(C + " "); 

        C = C * (line - i) / i; 

    

    Console.Write("\n") ;

    

  
// Код драйвера

public static void Main ()

    int n = 5; 

    printPascal(n); 


  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// PHP программа для треугольника Паскаля
// AO (n ^ 2) время и O (1) дополнительно
// космический метод для треугольника Паскаля

  
// функция Паскаля

function printPascal($n

    for($line = 1; $line <= $n; $line++) 

    

        $C = 1;// используется для представления C (line, i)

        for($i = 1; $i <= $line; $i++) 

        

            // Первое значение в

            // строка всегда 1

            print($C . " "); 

            $C = $C * ($line - $i) / $i

        

        print("\n"); 

    

  
// Код драйвера

$n = 5; 

printPascal($n);

  
// Этот код предоставлен mits
?>


Выход:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 

Таким образом, метод 3 является лучшим методом среди всех, но он может вызвать переполнение целых чисел для больших значений n, так как он умножает два целых числа для получения значений.

Эта статья составлена Rahul и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Треугольник Паскаля

0.00 (0%) 0 votes