파스칼의 삼각형

소개

수학에서 파스칼의 삼각형은 이항 계수의 삼각형 배열입니다.
아래에서 어떻게 생겼는지 볼 수 있습니다 ..

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

그것을 구축하는 방법?

우선 "1"로 시작하고 두 번째 행을 "1 1"로 ​​시작하면 위 행의 두 요소를 합하면 다음 행의 모든 ​​요소(1 제외)를 명확하게 볼 수 있습니다. (i.e., 1+1=2, 1+2=3, 1+3=4) 그리고 이 규칙으로 우리는 n 행의 파스칼 삼각형을 만들 수 있습니다.
아래는 어떻게 생겼는지 시각적으로 보여줍니다.

공식

[ ] n이 행 번호이고 k가 열 번호인 공식을 사용하여 각 값을 얻을 수 있도록 0번째 행을 첫 번째 행으로, 0번째 열을 첫 번째 열로 취하겠습니다. 따라서 두 번째 행에서 첫 번째(인덱스가 0인) 요소를 찾기 위해 2를 제공하는 2C1을 작성할 수 있습니다.

[ ] n번째 행에 대해 (x + y)^n을 풀어야 하는 또 다른 기술이 있습니다. (x +y)²를 풀면 x와 y의 계수로 두 번째 행을 얻게 됩니다. x² + 2xy + y²인 이 해결된 공식입니다. 계수는 파스칼의 삼각형에서 두 번째 행인 (1 ,2 , 1)입니다.

구현

이제 코드를 작성할 시간입니다. 몇 가지 다른 접근 방식을 구현하는 방법을 살펴보겠습니다.
접근법 1: nCr 공식

#include<iostream>
using namespace std;

// return Factorial of val
int fact(int val){
    int ans = 1;
    for(int i=1;i<=val;i++){
        ans = ans* i;
    }
    return ans;
}
// return next value in pascal triangle
int nextval(int row, int col){
    int result;
    result = fact(row) / (fact(col)* fact(row-col));
    return result;
}
int main(){
    int n = 5; // creating pascal's triangle of 5 rows
    for (int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cout << nextval(i,j) << " ";
        }
        cout << endl;
    }
    return 0;
}

접근법 2: 또 다른 공식

#include<iostream>
using namespace std;
int main(){
    int rows = 5;

    for (int i=1;i<=rows;i++){
        int nCr = 1;
        cout << 1 << " ";
        for(int j=1;j<i;j++){
            nCr = nCr *(i-j)/j;
            cout << nCr << " ";
        }
        cout << endl;
    }
    return 0;
}

접근법 3: 이전 행의 두 요소의 합을 저장하기 위해 Vector를 사용합니다.

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> pascal_triangle(int numRows) {
    vector<vector<int>> result(numRows);
    for(int i=0;i<numRows;i++){
        result[i].resize(i+1);
        result[i][0]=result[i][i]=1;

        for(int j=1;j<i;j++){
            result[i][j] = result[i-1][j] + result[i-1][j-1];
        }
    }
    return result;
}
void print(vector<vector<int>> result){
    for(int i=0;i<result.size();i++){
        for(int j=0;j<result[i].size();j++){
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
}
int main(){
    int n=10;
    vector<vector<int>> result = pascal_triangle(n);
    print(result);
    return 0;
}

접근법 4: Python3
[1] + [0]과 [0] + [1]처럼 [1]과 [0]을 연결하면 [1,0]과 [0,1]을 얻습니다. 이제 list1과 list2의 모든 요소의 합입니다. 파스칼 삼각형의 두 번째 행이 [1,1]과 같은 과정을 거치면 [1,1,0]과 [0,1,1], [1,2, 1] , 이 과정을 반복하면 n 행의 파스칼 삼각형을 얻을 수 있습니다.

def pascal_triangle(numRows):
    ans = [[1]]
    for _ in range(1,numRows):
        a = ans[-1] + [0]
        b = [0] + ans[-1]
        sum_ab = [x+y for (x,y) in zip(a,b)]
        ans.append(sum_ab)
    # print(ans)
    return ans

result = pascal_triangle(5)
for i in result:
    print(i)

파스칼의 삼각형에 대한 다른 구현이 아직 있습니다. 아는 경우 댓글 상자에 알려주세요.

몇 가지 놀라운 사실

[ ] 행의 요소를 합하면 2^n 이 됩니다. 여기서 n은 해당 파스칼 삼각형의 행 번호입니다. ( 1 = 2° , 1+1 = 2 , 1+2+1 = 2² )

[ ] 전체 행을 하나의 숫자로 취하면 11의 거듭제곱입니다( 11° = 1, 11 = 1 1, 11² = 1 2 1 ).

[ ] 또한 아래 이미지에서 볼 수 있는 파스칼의 삼각형에는 몇 가지 다른 패턴이 있습니다.

참조

[ ] https://www.mathsisfun.com/pascals-triangle.html

[ ] https://en.wikipedia.org/wiki/Pascal%27s_triangle

감사합니다 😊😊