~cpp
const int pas(const int &m,const int &n)
{
if(m==n || n==1) // 행과 열이 같거나(가장 오른쪽이거나) 열이 1일때는 1출력
return 1;
else
return pas(m-1,n-1)+pas(m-1,n); // 재귀호출
}
~cpp
unsigned long int P(int row, int col) {
/* 열의 값이 행보다 클 경우 종료 */
if(row < col)
exit(0);
/* 주어진 값을 검사하여, 첫번째 열이 1이거나 행과 열이 같은경우 1을 리턴 */
if(col == 1 || row == col)
return 1;
/* 그렇지 않은 경우 행과 열을 1씩 감소해서 재귀 호출한 값과
행만 1 감소시켜 재귀 호출한 값을 더해서 리턴 */
return P(--row, --col) + P(row, ++col);
}
~cpp
typedef unsigned long ulong;
ulong Pascal_Triangle(int m,int n)
{
ulong **Array=new ulong*[m]; // 2차원 동적 배열 할당
for(int i=0;i<m;i++)
Array[i]=new ulong[i+1]; // n행에는 n개의 열만 할당되게
for(i=0;i<m;i++)
{
for(int j=0;j<=i;j++)
{
if(i==j || j==0) // 행과 열이 같거나 열이 1일때
Array[i][j]=1; // (배열은 0부터 시작하므로 0이라했음) 1의 값을 줌
else
Array[i][j]=Array[i-1][j-1]+Array[i-1][j];
// 그 외의 경우에는 공식을 따른다.
}
}
ulong return_value=Array[m-1][n-1];
// 원하는 값 리턴(역시 배열은 0부터 시작하므로 하나씩 빼서)
if(Array) // Array 2차원 배열이 할당되었을때
{
for(i=0;i<m;i++)
{
if(Array[i])
delete [] Array[i]; // 지워 준다.(열)
}
}
delete [] Array; // 지워 준다.(행)
return return_value;
}
~cpp
int P(int row, int col) {
/* 변수 선언부 */
int i, j, temp;
/* 연산을 위해 이중 정수형 포인터 선언 */
int ** buffer;
/* 열이 행보다 클 경우 종료 */
if(col > row)
exit(0);
/* buffer에 행만큼의 정수포인터형을 할당받아 대입 */
buffer = malloc( row * sizeof(int *) );
for(i = 0; i < row; i++) {
/* 각각의 정수 포인터에 정수 배열을 할당한다 */
*(buffer + i) = (int *)malloc( (i + 1) * sizeof(int) );
/* 할당을 실패했을 때 */
if(*(buffer + i) == NULL) {
/* 먼저 여태까지 할당한 정수 배열을 반환 하고 */
for(j = 0; j <= i; j++) {
free(*(buffer + j));
}
/* 정수 포인터 배열을 반환 한 후 */
free(buffer);
/* 종료한다 */
exit(0);
}
}
/* 연산부 */
for(i = 0; i < row; i++) {
for(j = 0; j <= i; j++) {
/* 열이 1이거나 행과 열이 같은 경우, 1을 대입 한다 */
if(j == 0 || j == i) {
*(*(buffer + i) + j) = 1;
continue;
}
/* 그렇지 않은 경우 전 행(i - 1) 전 열(j - 1)의 값과,
전 행(i - 1) 동 열(j) 의 값을 더해서 대입한다 */
*(*(buffer + i) + j) =
*(*(buffer + i - 1) + j - 1) + *(*(buffer + i - 1) + j);
}
}
/* 계산한 결과값을 임시변수에 저장한다 */
temp = *(*(buffer + row - 1) + col - 1);
/* 먼저 정수 배열을 반환하고 */
for(i = 0; i < row; i++)
free(*(buffer + i));
/* 정수 포인터 배열을 반환한다 */
free(buffer);
/* 임시변수에 저장한 값을 리턴 */
return temp;
}
~cpp
// 첫행부터 n행까지 계산하는 방법을 통해
// 파스칼의 삼각형의 n행 m열의 값을 구하는 함수 (34행 까지 계산 가능)
unsigned long PascalTriangle1(int n, int m)
{
if(n<0 || n>35 || m<0 || m>n) // 행과 열의 값이 잘못된경우 0을 리턴
return 0;
if(n==1 || n==2) // 1행 또는 2행은 모두 1 이므로 1을 리턴
return 1;
// 2개의 배열을 사용하여 계산을 한다
// 하나의 배열에 2행을 저장한 후
// 그 배열을 사용해 3행을 계산해 나머지 배열에 저장하고
// 다시 3행이 저장된 배열을 사용해 4행을 계산해서
// 2행이 저장되어 있던 배열에 저장하고
// 계속 이와같은 식으로 n행 까지 계산한다
unsigned long *row[2]; // 2개의 배열의 포인터
row[0]=new unsigned long[40]; // 최대 40열까지 저장할 수 있도록 메모리 할당
row[1]=new unsigned long[40];
row[0][0]=row[0][1]=1; // 2행을 저장한다
int current=0; // 2개의 배열 중 계산중인 배열을 나타내는 변수
for(int i=3;i<=n;i++) // 3행부터 n행까지 계산
{
current=!current; // 계산할 배열을 바꿈
row[current][0]=1; // 첫번째 열은 항상 1
row[current][i-1]=1; // 마지막 열도 항상 1
for(int j=1;j<i-1;j++) // 나머지 열을 계산
row[current][j]=row[!current][j-1]+row[!current][j];
}
// n행 m열의 값을 보관
unsigned long temp=row[current][m-1];
delete[] row[0]; // 할당했던 메모리 해제
delete[] row[1];
return temp; // 보관해둔 n행 m열의 값을 리턴
}
~cpp
// 조합의 수를 계산하는 방법을 통해
// 파스칼의 삼각형의 n행 m열의 값을 구하는 함수 (17행까지 계산 가능)
unsigned long PascalTriangle2(int n, int m)
{
if(n<0 || n>18 || m<0 || m>n) // 행과 열의 값이 잘못된 경우 0을 리턴
return 0;
if(n==1 || n==2) // 1행 또는 2행은 모두 1 이므로 1을 리턴
return 1;
// 5행 1열과 5행 5열, 5행 2열과 5행 4열 등은
// 값이 같지만 5행 1열이나, 5행 2열이 계산이 간단하여
// 계산중에 오버플로우가 일어나는 경우를 줄일수 있어
// 더욱 많은 행을 계산할 수 있다
// 5행 5열이나, 5행 4열과 같은 것을 5행 1열이나, 5행 2열로
// 바꿔서 다시 호출해주는 부분이다
if(m>n/2+n%2)
return PascalTriangle2(n,n-m+1);
unsigned long x=1,y=1, p;
// (n-1)!/((n-1)-(m-1))! 을 계산
p=n-1;
for(int i=0;i<m-1;i++)
{
x*=p;
p--;
}
// (m-1)! 을 계산
for(p=m-1;p>=2;p--)
y*=p;
return x/y; // (n-1)!/(((n-1)-(m-1))!*(m-1)!) 을 리턴
}