ํ์ค์นผ์ ์ผ๊ฐํ ์๊ณ ๋ฆฌ์ฆ ¶
- ๋ฉฐ์น ์ ์ ๋ง๊ฐ๋ ์๋ฃ๊ตฌ์กฐ์ ์ฒซ๋ฒ์งธ ์์ ์์ฃ ? ๋ค๋ฅธ ๋ถ๋ค๋ ๋ค๋ฅด๊ฒ ์ง์ ๋ถ์ด ์์ผ์๋ค๋ฉด ์๋ก ์๊ฒฌ์ ๋๋ ๋ณด์์ผ๋ฉด ํฉ๋๋ค.
์ฌ๊ท ํธ์ถ์ ์ด์ฉํ ๋ฐฉ๋ฒ - 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)!) ์ ๋ฆฌํด }