Re: [問題] 降階法
以下有個前提是：
確定必須是 N x N，否則會有問題。
colIndex
r 0 1 2 3
o 0 2 2 3 4
w 1 4 5 6 7
I 2 7 8 9 1
d 3 2 3 4 5
e
x
call det() ────────────────────────────────┐
call det({0,1,2,3},0)──────────────────────────┐│
call det({1,2,3},1)──────────────────────────┐││
call det({2,3},2)──────────────────┐ │││
call det({3},3) ret (3,3)─┐ │ │││
call det({2},3) ret (2,3)─┼────┐ │ │││
ret (2,2) * (3,3)←────┘ │ │ │││
│-(3,2) * (2,3)←─────────┘ │ │││
│←────────────────────────┘ │││
└────────────────────────────┐ │││
call det({1,3},2)──────────────────┐ │ │││
call det({3},3) ret (3,3)─┐ │ │ │││
call det({1},3) ret (1,3)─┼────┐ │ │ │││
ret (1,2) * (3,3)←────┘ │ │ │ │││
│-(3,2) * (1,3)←─────────┘ │ │ │││
│←────────────────────────┘ │ │││
└───────────────────────────┐│ │││
call det({1,2},2)──────────────────┐ ││ │││
call det({2},3) ret (2,3)─┐ │ ││ │││
call det({1},3) ret (1,3)─┼────┐ │ ││ │││
ret (1,2) * (2,3)←────┘ │ │ ││ │││
│-(2,2) * (1,3)←─────────┘ │ ││ │││
│←────────────────────────┘ ││ │││
└──────────────────────────┐││ │││
ret (1,1) *[(2,2) * (3,3) - (3,2) * (2,3)] ←─────┼┼┘ │││
│-(2,1) *[(1,2) * (3,3) - (3,2) * (1,3)] ←─────┼┘ │││
│+(3,1) *[(1,2) * (2,3) - (2,2) * (1,3)] ←─────┘ │││
│←─────────────────────────────────┘││
└──────────────────────────────────┐││
after loop 1 at det({0,1,2,3},0) │││
│sum = │││
└→(0,0) * { │││
(1,1) *[(2,2) * (3,3) - (3,2) * (2,3)] ←─────────────┘││
-(2,1) *[(1,2) * (3,3) - (3,2) * (1,3)] ││
+(3,1) *[(1,2) * (2,3) - (2,2) * (1,3)]} ││
↓↓
in loop 2 at det({0,1,2,3},0)
call det({0,2,3},1}
and as so on.
after loop 2 at det({0,1,2,3},0)
sum =
(0,0) * {...}
-(0,1) * {...}
after loop 3 at det({0,1,2,3},0)
sum =
(0,0) * {...}
-(0,1) * {...}
+(0,2) * {...}
after loop 4 at det({0,1,2,3},0)
sum =
(0,0) * {...}
-(0,1) * {...}
+(0,2) * {...}
-(0,3) * {...}
EX:
{2,2,3,4},
{4,5,6,7},
{7,8,9,1},
{2,3,4,5}
sum =
2 * {
5 * [9 * 5 - 4 * 1]
-8 * [6 * 5 - 4 * 7]
+3 * [6 * 1 - 9 * 7]}
-4 * {
2 * [9 * 5 - 4 * 1]
-8 * [3 * 5 - 4 * 4]
+3 * [3 * 1 - 9 * 4]}
+7 * {
2 * [6 * 5 - 4 * 7]
-5 * [3 * 5 - 4 * 4]
+3 * [3 * 7 - 6 * 4]}
-2 * {
2 * [6 * 1 - 9 * 7]
-5 * [3 * 1 - 9 * 4]
+8 * [3 * 7 - 6 * 4]}
※ 引述《csihcs (非天夜翔)》之銘言：
: class Matrix {
: public:
: long det() {
: if(data.size() != data.at(0).size())
: return 0;
: vector<int> rows;
: for(int i = 0 ; i < data.size() ; i++)
: rows->push_back(i);
: return det(rows,0);
: }
: private:
: vector<vector<int>> data;
: long det(vector<int> rows,int colIndex) {
: long sum = 0;
: int sig = 1;
增加 :
if(rows.size() == 1)
return data.at(rows.at(0)).at(colIndex);
: for(int i = 0 ; i < rows.size() ; i++) {
: vector<int> newRows(rows);
: newRows.erase(newRows.begin()+i);
: sum += sig * data[rows.at(i)][colIndex] * det(newRows,colIndex+1);
改成 :
sum += sig * data.at(rows.at(i)).at(colIndex) * det(newRows,colIndex+1);
: sig *= -1;
: }
: return sum;
: }
: };
: ※ 引述《tyc5116 (累人啊....)》之銘言：
: : 不好意思,這個問題還是沒解決...@@
: : 附上我目前的進度
: : http://tinyurl.com/yjrabx4
: : 用vector寫的,降階的部份大致都弄好了
: : 只是在做運算的部份迴圈不知道怎麼設計
: : 主要用遞迴的方式寫(實際上我也只想到這個方法...@@)
: : 可是因為平常很少用遞迴寫程式,所以卡了這麼久
: : 主要的程式在這部份
: : vector<vector<int> > Matrix::Reduce(vector<vector<int> > submatrix,
: : int column,int& value){
: : vector<vector<int> > smallmatrix(submatrix.size()-1,vector<int>(
: : submatrix.size()-1));
: : vector<vector<int> > tmpmatrix;
: : vector<int> tmprow;
: : static int sum=0;
: : int r=1,c=0;
: : int s=1;
: : int col=0;
: : int cons=0;
: : int ans=0;
: : int rr=0;
: : //降階
: : for (int i=0;i<smallmatrix.size();++i){
: : for (int j=0;j<smallmatrix[0].size();++j){
: : if (j==column){++c;}
: : smallmatrix[i][j]=submatrix[r][c++];
: : }
: : c=0;
: : ++r;
: : }
: : cout<<"降階後的陣列"<<endl;
: : for (int j=0;j<smallmatrix.size();++j){
: : for (int k=0;k<smallmatrix[0].size();++k){
: : cout<<smallmatrix[j][k]<<" ";
: : }
: : cout<<endl;
: : }
: : if (smallmatrix.size()>1){
: : tmpmatrix=smallmatrix;
: : tmprow.resize(smallmatrix.size());
: : tmprow[0]=smallmatrix[0][0];
: : tmprow[1]=smallmatrix[0][1];
: : for (int i=0;i<smallmatrix.size();++i){
: : tmpmatrix=Reduce(smallmatrix,i,value);//若階數>1便再降階
: : cons=tmprow[rr++];
: : sum+=cons*s*tmpmatrix[0][0];
: : s*=-1;
: : }
: : }
: : return smallmatrix;
: : 個人認為應該把這裡解決掉就好.....可是我想好久了....@@
: : 再麻煩大大們解答一下,謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.9.2
→
10/17 23:54, , 1F
10/17 23:54, 1F
推
10/19 12:23, , 2F
10/19 12:23, 2F
討論串 (同標題文章)