برنامه محاسبه مثلث خیام پاسکال — راهنمای کاربردی

مثلث خیام پاسکال، آرایه مثلثی از ضرایب بسط دوجمله‌ای است. به این مثلث، «مثلث خیام»، «مثلث-پاسکال»، «مثلث خیام-پاسکال-نیوتن»، «مثلث تارتالیا» (در زبان ایتالیایی) و «مثلث یانگ هویی» (در زبان چینی) نیز گفته می‌شود. دلیل وجود نام‌های متعدد برای این مثلث آن است که دانشمندان گوناگون از نقاط مختلف جهان، شامل ایران، فرانسه، ایتالیا، چین، هند و آلمان، در برهه‌های مختلفی از تاریخ، مطالعاتی پیرامون این مثلث داشته‌اند. در این مطلب، به روش ساخت برنامه محاسبه مثلث خیام و همچنین، چگونگی پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) پرداخته شده است. سطرهای مثلث پاسکال معمولا با آغاز از بالاترین سطر، به عنوان سطر شماره صفر (یعنی n = ۰) شمارش می‌شوند. ورودی‌های هر سطر، از سمت چپ با آغاز از k = 0 شمارش می‌شوند و مقدار آن‌ها وابسته به اعداد موجود در سطرهای مجاور است. یک مثلث خیام پاسکال را می‌توان به صورت زیر ساخت.

در سطر صفر (بالاترین سطر)، یک ورودی یکتای غیر صفر یعنی یک (۱) وجود دارد. هر ورودی در سطرهای زیرین، با محاسبه مجموع عددهای بالایی از چپ به راست محاسبه می‌شود و موارد فاقد ورودی، صفر محسوب می‌شوند. برای مثال، مقدار اولیه در سطر اول (یا هر سطر دیگری) برابر با یک (۱) است (جاصل جمع صفر و یک). این در حالی است که به عنوان نمونه، در سطر سوم (n = 3)، یک و سه با یکدیگر جمع می‌شوند و مقدار ۴ را برای سطر بعدی (سطر چهارم) می‌سازند. در انیمیشن زیر، آنچه بیان شد را می‌توان مشاهده کرد.

فرمول مثلث خیام پاسکال

ورودی سطر nاُم و ستون kاُم به صورت $$\left(\begin{array}{c}n\\ k\end{array}\right)$$ مشخص می‌شود. برای مثال، ورودی یکتای غیر صفر بالاترین سطر (سطر صفر و ستون صفر)، به صورت $$\left(\begin{array}{c}0\\ 0\end{array}\right)=1$$ است. با توجه به این موضوع، می‌توان روش محاسبه بیان شده در پاراگراف پیشین را به صورت زیر نوشت:

$$\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n – 1\\ k – 1\end{array}\right)+\left(\begin{array}{c}n – 1\\ k\end{array}\right)$$

برای عدد صحیح غیر صفر n و عدد صحیح k بین ۰ تا n، رابطه بازگشتی بالا برای ضرایب چندجمله‌ای برقرار است. به این فرمول، اتحاد پاسکال گفته می‌شود. اتحاد پاسال دارای تعمیم برای ابعاد بالاتر است. نسخه سه‌بُعدی مثلث خیام پاسکال را «هرم پاسکال» (Pascal’s Pyramid) یا «چهار وجهی پاسکال» (Pascal’s Tetrahedron) می‌نامند. نسخه تعمیم یافته را نیز «ساده پاسکال» (Pascal’s Simplices) می‌نامند.

برنامه محاسبه مثلث خیام پاسکال

مثلث پاسکال یک آرایه مثلثی از ضرایب چندجمله‌ای است. هدف نوشتن تابعی است که یک مقدار صحیح n را به عنوان ورودی دریافت و اولین n سطر مثلث پاسکال را چاپ کند. در ادامه، ۶ سطر اول مثلث پاسکال نمایش داده شده‌اند.

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

روش اول با پیچیدگی زمانی از مرتبه (O(n³

با فرض آنکه سطرها از یک شروع می‌شوند (n = 1)، تعداد ورودی‌ها در هر سطر برابر با شماره آن سطر است. برای مثال، اولین سطر دارای یک ورودی (۱) است؛ دومین سطر دو ورودی (1 1) و سومین سطر سه ورودی (1 2 1) دارد و همین قاعده برای سایر سطرها نیز صادق است. هر ورودی در یک سطر، مقدار ضریب دو جمله‌ای (در بسط دو جمله‌ای) است. مقدار iاُمین ورودی در سطر شماره line، برابر با (C(line, i است. مقدار را می‌توان با استفاده از فرمول زیر محاسبه کرد.

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

یک راهکار ساده، اجرای دو حلقه و محاسبه مقدار ضریب چندجمله‌ای در حلقه داخلی است.

محاسبه مثلث خیام پاسکال در ++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 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.*/

محاسبه مثلث خیام پاسکال در پایتون

# 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 
?>

خروجی

خروجی قطعه کدهای بالا برای n = 5 به صورت زیر است.

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³ است. در ادامه، روش‌های بهینه شده نیز معرفی شده‌اند.

روش ۲ با پیچیدگی زمانی از مرتبه (O(n² و فضای اضافی (O(n²

با نگاهی دقیق‌تر به مثلث خیام، می‌توان مشاهده کرد که هر ورودی، مجموع دو مقدار بالایی خودش است. بنابراین، می‌توان آرایه دوبُعدی ساخت که مقادیر از پیش تولید شده را ذخیره می‌کند. برای تولید یک مقدار در یک خط، می‌توان از مقادیری که پیش‌تر در آرایه ذخیره شده‌اند استفاده کرد.

محاسبه مثلث خیام پاسکال در ++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 pscal 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 pscal 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 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(""); 
} 
} 
}

محاسبه مثلث خیام پاسکال در #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 pscal 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 
?>

خروجی

خروجی قطعه کد بالا برای n = 5 به صورت زیر است.

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

روش بیان شده را می‌توان به نوعی بهینه کرد که از فضای اضافی (O(n استفاده کند. این کار را می‌توان با توجه به این موضوع انجام داد که برای محاسبه مقادیر یک سطر، تنها نیاز به مقادیر سطر پیشین آن است. بنابراین، می‌توان یک آرایه با اندازه n را ساخت و مقادیر را بازنویسی کرد. در ادامه، راهکار دیگری ارائه شده که تنها از فضای اضافی (O(1 استفاده می‌کند.

روش ۳ با پیچیدگی زمانی (O(n² و فضای اضافی (O(1

این روش، بر مبنای روش اول است. چنانکه پیش‌تر بیان شد، ورودی‌های سطر iاُم در سطر شماره line، ضرایب چندجمله‌ای (C(line, i هستند و همه سطرها با مقدار ۱ شروع می‌شوند. هدف محاسبه (C(line, i با استفاده از (C(line, i-1 است. این مقدار را می‌توان در زمان (O(1 با استفاده از روش زیر محاسبه کرد.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )
می‌توان رابطه زیر را از دو رابطه بالا نتیجه گرفت.
C(line, i) = C(line, i-1) * (line - i + 1) / i

بنابراین، (C(line, i را می‌توان با استفاده از (C(line, i-1 در زمان (O(1 محاسبه کرد.

محاسبه مثلث خیام پاسکال در ++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 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(); 
    } 
} 
  
//Diver code 
public static void main (String[] args) { 
    int n = 5; 
    printPascal(n); 
}  
} 
// This code is contributed  
// by Archit Puri

محاسبه مثلث خیام پاسکال در پایتون ۳

# 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 
?>

خروجی

خروجی قطعه کد بالا برای n = 5 به صورت زیر است.

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

بنابراین، راهکار سوم، نسبت به سایر روش‌های ارائه شده در این مطلب بهتر است. اما ممکن است موجب «سرریز صحیح» (Integer Overflow) برای مقادیر بزرگ n شود؛ زیرا برای به دست آوردن مقادیر، دو عدد صحیح را ضرب می‌کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• برنامه تشخیص اعداد اول در پایتون — به زبان ساده
• برنامه تجزیه عدد به عوامل اول آن — به زبان ساده
• حل مساله رنگ‌آمیزی گراف با الگوریتم پس گرد — به زبان ساده

^^