imported>Unknown at 05:24, 7 February 2021

2021-02-07T05:24:00Z

New page

= 파스칼의 삼각형 알고리즘 =
* 며칠전에 마감된 자료구조의 첫번째 숙제였죠? 다른 분들도 다르게 짜신 분이 있으시다면 서로 의견을 나눠 보았으면 합니다.

== 재귀 호출을 이용한 방법 - by 인수 ==
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); // 재귀호출
}

* 보시는 바와 같이.. 졸라 간단합니다.
* but.. 숫자가 조금만 커져도.. 굉장히 오래 걸립니다. 01학번 이선호군이 32행 정도를 넣어봤을때 걸린 시간은 100초가 넘었다 합니다. 재귀호출.. 될수 있으면 쓰지 맙시다.
* 이 알고리즘은 시간을 희생하면서 공간을 줄인 알고리즘이겠죠?
* 뒤를 볼것도 없이 일관적인 알고리즘 -- 선호.

== recursive -zennith ==
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);
}

* 단순히 프린트물의 내용을 옮겼을 뿐..

== 동적 배열을 이용한 방법 - by 인수 ==
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;
}

* 딱 보기에도 재귀호출보다는 복잡하죠?
* 그런데.. 속도는 확실히 빠릅니다. 몇백을 넣어도 즉시즉시 나오는..
* 이 알고리즘은 메모리를 더 쓰면서 속도를 살린 방법이겠죠?
* 자바로 짜면 좀 더 쉬울거 같네여. 메모리 새는걸 걱정하지 않아도 되니..
* 다른 좋은 방법이 있으시면 여기다 적어주시기 바랍니다.
* ㅡ.ㅡ 가..같다.. --선호

== dynamic allocation -zennith ==
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;
}

* 아직 개선할점이 한 두 군데 있는데.. 구지 여기에 올린 이유는 저게 Null pointer assignment 에러가 나서.. 에러난걸 왜 올리는데. 라고 하시면 할말 없지만.. 혹시 혜안으로 시원하게 찔러주실 분 지적해주시면 감사하겠습니다.
* 해결했습니다. 문제 없이 돌아가는군요.. 역시 포인터는 어렵고 어려워라..

== 첫줄부터 쭉 계산하는 방법 ==
// 첫행부터 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열의 값을 리턴
}

== 조합의 수를 이용한 방법 ==
// 조합의 수를 계산하는 방법을 통해
// 파스칼의 삼각형의 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)!) 을 리턴
}
----
[[문제분류]]

PascalTriangle - Revision history

imported>Unknown at 05:24, 7 February 2021