파스칼 삼각형(C++)

n을 입력받고 파스칼 삼각형의 n번째 열의 수열을 출력하라. (n은 30 이하로 입력한다.)




파스칼 삼각형의 i번째열의 j번째 항을 p[i][j]라고 하면, p[i][j]는 다음과 같다.

p[i][j] = p[i-1][j-1] + p[i-1][j]

따라서, 재귀함수로 쉽게 구할 수 있다.


#include <iostream>
#include <windows.h>

using namespace std;

int pas(int i, int j){
   
    if(j==1||j==i) return 1;
   
    else return pas(i-1,j-1)+pas(i-1,j);
}
int main(){
   
    int n,j;
   
    cin >>n;
   
    for(j=1;j<=n;j++)cout<<pas(n,j)<<" ";
   
    cout << endl;
   
    system("PAUSE");
   
    return 0;
}
실행결과

8
1 7 21 35 35 21 7 1
Press any key to continue . . .


재귀함수를 사용하는 방법은 코드가 간결해서 좋지만 입력수가 높아질 수록 함수를 훨신 많이 호출하게 되며 그많큼 처리 속도도 느려지며 메모리를 많이 차지하게 된다. 따라서 좀더 메모리를 덜 사용하며 처리속도가 빠른 방법을 생각해보자.

2개의 int 배열을 이용해보자.
하나를 a 나머지를 b라고 해보자.

아래와 같은 방법을 쓰면 n열의 수열을 구할 수 있다.
1. 1열의 수열을 a에 대입한다.
2. a에 저장된 i열의 수열을 이용하여 i+1열의 수열을 b에다 구현한다.
3. b에 저장된 i+1열의 수열을 복사하여 a에 대입한다.
4. 2-3을 a에 n번째 열의 수열이 저장될때가지 n-1번 반복한다.

#include <iostream>
#include <windows.h>

using namespace std;
int main(){
   
    int a[30]={1},b[30]={1},n,i,j;//n은 30이하이기 때문에 한열에 들어갈 원소의 수는 30 이하이다.
    //b[0]은 항상 1이다. a를 파스칼 삼각형의 첫번째 열로 초기화 해준다.
   
    cin >> n;
   
    for(i=1;i<n;i++){//i열을 이용하여 i+1열을 구한다.
                     b[i]=1;
                     for(j=1;j<i;j++){
                                       b[j]=a[j-1]+a[j];
                     }
                    
                     for(j=0;j<=i;j++)a[j]=b[j];
    }
   
    for(j=0;j<n;j++){
                     cout<<a[j]<<" ";
    }
   
    cout << endl;
   
    system("PAUSE");
   
    return 0;
}

실행결과

15
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
Press any key to continue . . .