파스칼의 삼각형 – 공식, 패턴 및 예
사라 첸
파스칼의 삼각형은 무엇입니까?
파스칼의 삼각형은 숫자의 삼각형 배열이며, 그 뒤에 특정 패턴과 그 앞의 행과의 연결이 있습니다. 블레즈 파스칼이 발명했습니다. 이 삼각형은 첫 번째 행의 한 요소로 시작합니다. 그 후, 각 행은 "1"로 시작하고 끝납니다.
파스칼의 삼각형 역사
중국 책 "수학 예술의 XNUMX장"에는 파스칼의 삼각형의 첫 번째 예 중 하나가 포함되어 있습니다. 게다가, 그것은 오늘날 삼각형에서 볼 수 있는 것과 동일한 패턴과 특성을 일부 포함하고 있습니다.
파스칼은 유럽에서 삼각형을 연구한 여러 사람 중 한 명이었습니다. 다른 수학자들은 그 전에도 비슷한 삼각형 숫자 배열을 조사했습니다.
파스칼의 삼각형 만들기
파스칼 삼각형을 만드는 것은 간단합니다. 기억해야 할 것은 행이 1로 시작하고 끝난다는 것입니다. 나머지 숫자에 대한 규칙은 다음과 같습니다.
임의의 행 r과 열 c에 대해 숫자는 행 r-1의 열 c-1과 c의 합이 됩니다.
여기
- r = 3,4,5…
- n 및 c = 2,3,4,…r-1.
파스칼의 삼각형을 만드는 단계는 다음과 같습니다.
단계 1) 두 행을 채우는 것부터 시작해 보겠습니다.
단계 2) 세 번째 줄의 두 번째 요소는 두 번째 행의 첫 번째 숫자와 두 번째 숫자의 합입니다.
단계 3) 네 번째 행은 "1."으로 시작됩니다. 두 번째 숫자는 3으로, 1과 2의 합입니다(파란색으로 강조 표시됨).
아래 이미지는 네 번째 행을 채우는 방법을 보여줍니다.
단계 4) 다섯 번째 행은 다섯 개의 숫자로 구성됩니다. 우리는 이미 이전 단계에서 행을 채우는 패턴을 알고 있습니다.
파스칼의 삼각형 공식 - 이항 계수
이항 계수는 n개 요소 집합에서 k개 요소의 하위 집합을 선택하는 다양한 방법을 나타내는 숫자입니다. 흔히 “C(n,k)” 또는 “n choose k”로 표기됩니다.
이항 계수는 다음과 같이 정의됩니다.
“!” 는 "계승"을 나타냅니다.
N! = n.(n-1). (n-2)…3.2.1
예를 들어,
5! = 5.4.3.2.1
= 120
따라서 C(5,3) 또는 5가 3 = 5를 선택한다고 가정해 보겠습니다. / 3!(5-3)!
= 120/(12)
= 10
방법 1: 이전 행으로 파스칼의 삼각형 만들기
이 절차의 단계는 파스칼의 삼각형 단계와 동일합니다. 최대 XNUMX개의 행으로 구성된 파스칼의 삼각형을 만들고 싶다고 가정해 보겠습니다.
이를 수행하는 단계는 다음과 같습니다.
단계 1) "1"로 맨 위 행을 시작합니다.
단계 2) “r” 행의 경우 “c” 항목은 “c-1”과 “c”는 “r-1” 행의 번호를 곱한 값이 됩니다.
단계 3) 행의 첫 번째 숫자와 마지막 숫자는 항상 "1"입니다.
파스칼의 삼각형을 만들려면 다음 세 가지 쉬운 단계를 따라야 합니다.
C++ 이전 행의 파스칼 삼각형 코드
#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
int numbers[n][n];
for (int row = 0; row < n; row++)
{
for (int col = 0; col <= row; col++)
{
if (col == 0 || col == row)
{
numbers[row][col] = 1;
}
else
{
numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
}
cout << numbers[row][col] << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printRow(n);
}
출력:
How many rows: 7 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
Python 이전 행의 파스칼 삼각형 공식 코드
def printRow(n):
numbers = [[0 for row in range(n)]
for col in range(n)
]
for row in range(len(numbers)):
for col in range(0, row+1):
if row == col or col == 0:
numbers[row][col] = 1
else:
numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]
print(numbers[row][col],end="\t")
print("\n")
n = int(input("How many rows: "))
printRow(n)
Pascal의 삼각형 예제 출력:
How many rows: 7 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
복잡성 분석
A XNUMX차원 배열 구현에 사용되었습니다. N은 파스칼 삼각형의 행 수라고 가정합니다. 이를 위해서는 N이 필요합니다.2 단위 공간입니다. 따라서 O는 공간 복잡도(N)가 됩니다.2).
함수에 두 개의 루프가 있으며 각 루프는 "N"번 실행됩니다. 따라서 시간 복잡도도 다음과 같습니다. 의 위에2) 또는 제곱 시간 복잡도.
방법 2: 이항 계수를 계산하여 파스칼의 삼각형 만들기
우리는 이항 계수를 사용하여 파스칼 삼각형의 숫자를 간단히 유도할 수 있습니다. 다이어그램은 다음과 같습니다.
이항식을 계산하여 파스칼의 삼각형을 만드는 단계는 다음과 같습니다.
단계 1) 최상위 행은 C(0,0)입니다. 위의 이항 계수 공식을 사용하면 C(0,0) = 1입니다. 왜냐면 0! = 1.
단계 2) 행 “i”에는 총 “i” 요소가 있습니다. 각 항목은 C(n,r)로 계산됩니다. 여기서 n은 i-1입니다.
단계 3) 파스칼의 삼각형에 원하는 행 수에 대해 2단계를 반복합니다.
C++ 이항 계수에 의한 코드 파스칼의 삼각형
#include <iostream>
using namespace std;
int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}
int binomialCoefficient(int n, int r)
{
int result = 1;
if (r > n)
{
return -1;
}
result = factorial(n) / (factorial(r) * factorial(n - r));
return result;
}
void printPascalTriangle(int row)
{
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= i; j++)
{
cout << binomialCoefficient(i, j) << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "Enter row number: ";
cin >> n;
printPascalTriangle(n);
}
출력:
Enter row number: 9 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 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Python 이항 계수에 의한 코드 파스칼의 삼각형
def factorial(n):
result = 1
for i in range(1,n+1):
result*=i
return result
def binomialCoefficient(n,r):
result =1
if r>n:
return None
result = factorial(n) / (factorial(r) * factorial(n - r))
return int(result)
def printPascalTriangle(row):
for i in range(row+1):
for j in range(i+1):
print(binomialCoefficient(i, j), end="\t")
print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)
Pascal의 삼각형 예제 출력:
Enter row number: 8 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 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1
복잡성 분석
구현에는 세 개의 루프가 사용되었습니다. 한 루프는 이항 계수를 계산하는 데 사용되고 다른 두 개는 모든 행에 대한 숫자를 만드는 데 사용됩니다. 행의 수와 관련하여 "n"번 실행되는 세 개의 루프가 있습니다. 결과적으로 전체 시간 복잡도는 0(n3).
이제 공간 복잡도는 저장소에 데이터를 보관하지 않기 때문에 일정합니다. 프로그램은 요소를 계산하고 행에 인쇄합니다. 그런 다음 공간 복잡도는 0(1)로 감소합니다.
방법 3: 수정된 이항 계수로 파스칼의 삼각형 만들기
이전 기술에서 우리는 이항 계수를 사용하여 파스칼 삼각형의 각 요소를 계산하는 방법을 이미 살펴보았습니다. 이 접근법은 C(n, r-1)로부터 C(n,r)을 결정합니다. 한 가지 순서로 모든 것을 단순화할 것입니다.
다음은 수정된 이항 계수로 파스칼의 삼각형을 만드는 단계입니다.
단계 1) "1"로 첫 번째 행을 시작합니다.
단계 2) C(n,r)를 계산합니다. 여기서 "n"은 행 번호이고 "r"은 열 또는 요소입니다. 변수 C에 값을 할당합니다.
단계 3) C(n,k)를 계산하려면 C*(nk)/k가 됩니다. 이제 이 값을 C에 할당합니다.
단계 4) "k"가 행 끝에 도달할 때까지 3단계를 계속합니다. 각 반복 후에 K 값을 XNUMX씩 증가시킵니다.
C++ 수정된 이항 계수를 사용한 파스칼의 삼각형 코드
#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
for (int row = 1; row <= n; row++)
{
int previous_coef = 1;
for (int col = 1; col <= row; col++)
{
cout << previous_coef << "\t";
previous_coef = previous_coef * (row - col) / col;
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printpascalTriangle(n);
}
출력:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python 수정된 이항 계수를 사용한 파스칼의 삼각형 코드
def printpascalTriangle(n):
for row in range(1, n+1):
previous_coef = 1
for col in range(1, row+1):
print(previous_coef, end="\t")
previous_coef = int(previous_coef*(row-col)/col)
print()
n = int(input("How many rows: "))
printpascalTriangle(n)
Pascal의 삼각형 패턴 출력:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
복잡성 분석
구현에는 두 개의 루프가 있습니다. 각 루프는 최대 "n"번 실행되며, 여기서 "n"은 파스칼 삼각형의 행 수를 의미합니다. 따라서 시간 복잡도는 다음과 같습니다. 의 위에2), 시간의 제곱.
공간 복잡도에 관해서는 저장할 배열이 필요하지 않았습니다. 이전 이항 계수를 유지하기 위해 변수 하나만 사용했습니다. 따라서 여분의 공간 하나만 필요했습니다. 공간 복잡도는 다음과 같습니다. O (1).
파스칼의 삼각형 응용
파스칼의 삼각형을 적용한 예는 다음과 같습니다.
이항 확장: 파스칼의 삼각형으로부터 이항 확장 계수를 결정할 수 있습니다. 예는 다음과 같습니다.
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2XY + 1y2 |
| (x + y)3 | 1x3 + 3x2그리고 + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3그리고 + 6x2y2 + 4xy3 + 1y4 |
조합 계산: 우리는 파스칼 삼각형의 요소가 이항 계수와 동일하다는 것을 보았습니다. 예를 들어, 6개의 공이 있고 3개의 공을 선택하라는 요청을 받았다면 다음과 같습니다. 6C3. 또는 파스칼의 삼각형에서 여섯 번째 행의 세 번째 요소에서 숫자를 찾을 수 있습니다.
파스칼의 삼각형에 관한 흥미로운 사실
파스칼의 삼각형에 관해 흥미로운 사실은 다음과 같습니다.
- 연속된 모든 요소의 합은 항상 2의 거듭제곱입니다.
- 행 요소의 대각선 합은 피보나치 수열을 생성합니다.
요약
- 파스칼의 삼각형은 이항 확장에 대한 계수를 제공합니다.
- 파스칼의 삼각형의 각 행은 "1"로 시작하고 끝납니다. 중간 값은 이전 행의 두 요소의 합입니다.
- 파스칼의 삼각형의 모든 요소를 대각선으로 더하면 다음이 됩니다. 피보나치 수열.
- 파스칼의 삼각형은 이항 계수를 사용하여 생성할 수도 있습니다.
