ํ์ค์นผ์ ์ผ๊ฐํ ์๊ณ ๋ฆฌ์ฆ ¶
- ๋ฉฐ์น ์ ์ ๋ง๊ฐ๋ ์๋ฃ๊ตฌ์กฐ์ ์ฒซ๋ฒ์งธ ์์ ์์ฃ ? ๋ค๋ฅธ ๋ถ๋ค๋ ๋ค๋ฅด๊ฒ ์ง์ ๋ถ์ด ์์ผ์๋ค๋ฉด ์๋ก ์๊ฒฌ์ ๋๋ ๋ณด์์ผ๋ฉด ํฉ๋๋ค.
์ฌ๊ท ํธ์ถ์ ์ด์ฉํ ๋ฐฉ๋ฒ - by ์ธ์ ¶
~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); // ์ฌ๊ทํธ์ถ
}
- ๋ณด์๋ ๋ฐ์ ๊ฐ์ด.. ์กธ๋ผ ๊ฐ๋จํฉ๋๋ค.
- but.. ์ซ์๊ฐ ์กฐ๊ธ๋ง ์ปค์ ธ๋.. ๊ต์ฅํ ์ค๋ ๊ฑธ๋ฆฝ๋๋ค. 01ํ๋ฒ ์ด์ ํธ๊ตฐ์ด 32ํ ์ ๋๋ฅผ ๋ฃ์ด๋ดค์๋ ๊ฑธ๋ฆฐ ์๊ฐ์ 100์ด๊ฐ ๋์๋ค ํฉ๋๋ค. ์ฌ๊ทํธ์ถ.. ๋ ์ ์์ผ๋ฉด ์ฐ์ง ๋ง์๋ค.
- ์ด ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ์ ํฌ์ํ๋ฉด์ ๊ณต๊ฐ์ ์ค์ธ ์๊ณ ๋ฆฌ์ฆ์ด๊ฒ ์ฃ ?
- ๋ค๋ฅผ ๋ณผ๊ฒ๋ ์์ด ์ผ๊ด์ ์ธ ์๊ณ ๋ฆฌ์ฆ -- ์ ํธ.
recursive -zennith ¶
~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);
}
- ๋จ์ํ ํ๋ฆฐํธ๋ฌผ์ ๋ด์ฉ์ ์ฎ๊ฒผ์ ๋ฟ..
๋์ ๋ฐฐ์ด์ ์ด์ฉํ ๋ฐฉ๋ฒ - by ์ธ์ ¶
~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;
}
- ๋ฑ ๋ณด๊ธฐ์๋ ์ฌ๊ทํธ์ถ๋ณด๋ค๋ ๋ณต์กํ์ฃ ?
- ๊ทธ๋ฐ๋ฐ.. ์๋๋ ํ์คํ ๋น ๋ฆ
๋๋ค. ๋ช๋ฐฑ์ ๋ฃ์ด๋ ์ฆ์์ฆ์ ๋์ค๋..
- ์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ์ฐ๋ฉด์ ์๋๋ฅผ ์ด๋ฆฐ ๋ฐฉ๋ฒ์ด๊ฒ ์ฃ ?
- ์๋ฐ๋ก ์ง๋ฉด ์ข ๋ ์ฌ์ธ๊ฑฐ ๊ฐ๋ค์ฌ. ๋ฉ๋ชจ๋ฆฌ ์๋๊ฑธ ๊ฑฑ์ ํ์ง ์์๋ ๋๋..
- ๋ค๋ฅธ ์ข์ ๋ฐฉ๋ฒ์ด ์์ผ์๋ฉด ์ฌ๊ธฐ๋ค ์ ์ด์ฃผ์๊ธฐ ๋ฐ๋๋๋ค.
- ใ
ก.ใ
ก ๊ฐ..๊ฐ๋ค.. --์ ํธ
dynamic allocation -zennith ¶
~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;
}
- ์์ง ๊ฐ์ ํ ์ ์ด ํ ๋ ๊ตฐ๋ฐ ์๋๋ฐ.. ๊ตฌ์ง ์ฌ๊ธฐ์ ์ฌ๋ฆฐ ์ด์ ๋ ์ ๊ฒ Null pointer assignment ์๋ฌ๊ฐ ๋์.. ์๋ฌ๋๊ฑธ ์ ์ฌ๋ฆฌ๋๋ฐ. ๋ผ๊ณ ํ์๋ฉด ํ ๋ง ์์ง๋ง.. ํน์ ํ์์ผ๋ก ์์ํ๊ฒ ์ฐ๋ฌ์ฃผ์ค ๋ถ ์ง์ ํด์ฃผ์๋ฉด ๊ฐ์ฌํ๊ฒ ์ต๋๋ค.
- ํด๊ฒฐํ์ต๋๋ค. ๋ฌธ์ ์์ด ๋์๊ฐ๋๊ตฐ์.. ์ญ์ ํฌ์ธํฐ๋ ์ด๋ ต๊ณ ์ด๋ ค์๋ผ..
์ฒซ์ค๋ถํฐ ์ญ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ ¶
~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)!) ์ ๋ฆฌํด
}
