首页 > 代码库 > 方阵求值——上三角行列式、定义(康拓展开求值)

方阵求值——上三角行列式、定义(康拓展开求值)

Problem:求方阵A的值。

技术分享

 

 

设求n*n的矩阵:加法的操作次数为P(n),乘法的操作次数与为M(n)。

 

对于方法1:

j1~jn共有n!种选法:j1n种选法,j2n-1种选法,…,jn1种选法。

P(n)=n!-1

M(n)=n!*(n-1)

 

对于方法2:

P(1)=0

P(2)=2

P(n)=(n-1)+n*P(n-1)=(n-1)+(n-2)+n*(n-1)*P(n-2)=…=(n-1)+(n-2)+…+2+n*(n-1)*…*3*P(2)

=(n+1)*(n-2)/2+n!            (n>=3)

可以都写成P(n)= (n+1)*(n-2)/2+n!

 

M(1)=0

M(2)=2

M(n)=n+n*M(n-1)=n+(n-1)+n*(n-1)*M(n-2)=…=n+(n-1)+…+3+n*(n-1)*…*3*P(2)=

=(n+3)*(n-2)/2+n!            (n>=3)

 

方法1相比方法2乘法操作次数多了大概(n-1)倍,是因为

技术分享技术分享,除了前面两个数,其它数的乘积都一样,但是方法1对于技术分享的乘积重复计算。

而方法2的乘法操作次数仍然很多,是因为如技术分享技术分享,方法2对技术分享的乘积重复计算。

 

方法1通过全排列优化后:

序列从小到大排序,编号为1~n!。编号为(t+1)[t=1~n!-1]的序列,当最大能被r!整除时,需要修改的长度为r+1,寻找j需要r+1次,寻找k需要1,2,3,…,r次,然后a[j]和a[k]进行交换,a[n-r]~a[n]修改顺序,共进行(temp=x,x=y,y=temp)3*(1+(r+1)/2)次赋值语句操作。

 

r=n,n-1,…,1时

total=n*1+(n-1)*[n-1]+(n-2)*[n*(n-1)-n]+(n-3)*[n*(n-1)*(n-2)-n*(n-1)]+…+

???

12345

12354

12435

12453

12534

12543

13245

 

方法3:

化简为上三角行列式

并对所有对角线的数进行相乘得到方阵的值。

 

对于每列i化简:从行i开始,往下找,直到第j行a[j][i]<>0,然后行i和行j进行交换(如果i<>j),然后行i+1~行n通过对行i加/减某个倍数,使得a[k][i]=0。每列i化简最多对(n-i)行进行了处理,时间复杂度为O(n*n)。

总的时间复杂度:O(n^3)

 

 Code:

1.求方阵面积_n阶行列式的定义

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 //原来O(n!)
  5 //优化:
  6 //效率不高,但所用方法很巧妙
  7 //n=10 10!=3628800
  8 
  9 int main()
 10 {
 11     long n,i,j,k,p,g,temp,x,y,a[20];
 12     double mat[20][20],c[20],ans;
 13     scanf("%ld",&n);
 14     //posibility
 15     p=1;
 16     for (i=2;i<=n;i++)
 17         p=p*i;
 18     for (i=1;i<=n;i++)
 19         for (j=1;j<=n;j++)
 20             scanf("%lf",&mat[i][j]);
 21     c[0]=1.0;
 22     for (i=1;i<=n;i++)
 23     {
 24         a[i]=i;
 25         c[i]=c[i-1]*mat[i][i];
 26     }
 27     ans=c[n];
 28     g=0;
 29     for (i=1;i<p;i++)
 30     {
 31         //4 8 7 6 5 3 2 1
 32         //5 8 7 6 4 3 2 1
 33         //5 1 2 3 4 6 7 8
 34 
 35         //从尾到头,找到第一个下降的a[j]
 36         for (j=n-1;j>=1;j--)
 37             if (a[j]<a[j+1])
 38                 break;
 39         //a[j]:从尾到a[j],找到第一个比a[j]大的数a[k]
 40         for (k=n;k>j;k--)
 41             if (a[k]>a[j])
 42                 break;
 43         //交换a[j]和a[k]的值
 44         temp=a[j];
 45         a[j]=a[k];
 46         a[k]=temp;
 47         //数组:j+1~n reverse
 48         x=j+1;
 49         y=n;
 50         while (x<y)
 51         {
 52             temp=a[x];
 53             a[x]=a[y];
 54             a[y]=temp;
 55             x++;
 56             y--;
 57         }
 58         //1~j-1:not change
 59         for (k=j;k<=n;k++)
 60             c[k]=c[k-1]*mat[k][a[k]];
 61         g=g-(n-j-1)*(n-j)/2+1;
 62         //逆序对的数目跟上一次的差距
 63         //原来j+1~n降序,a[j+1]~a[n]中逆序对的数目为(n-j-1)*(n-j)/2
 64         //现在j+1~n升序,a[j]在a[j]~a[n]的大小排名上升了一位,即第j位所在的数的逆序对的个数增加了1
 65         if (g%2==0)
 66             ans+=c[n];
 67         else
 68             ans-=c[n];
 69     }
 70     if (fabs(ans)<0.000001)
 71         printf("%.2lf",0.0);
 72     else
 73         printf("%.2lf",ans);
 74     return 0;
 75 }
 76 /*
 77 Input:
 78 4
 79 2 -1 0 3
 80 -3 1 2 2
 81 1 0 -2 -1
 82 -4 3 2 2
 83 Output:
 84 24.00
 85 
 86 Input:
 87 3
 88 1 2 3
 89 2 3 4
 90 3 4 5
 91 Output:
 92 0.00
 93 
 94 Input:
 95 2
 96 1 2
 97 2 1
 98 Output:
 99 -3.00
100 */

 

2.求方阵面积_化简为上三角行列式

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define minv 0.000001
 4 #define maxn 100
 5 
 6 int main()
 7 {
 8     long n,i,j,k,l;
 9     double s,result=1.0;
10     double **matrix=(double **) malloc (sizeof(double *)*(maxn+1));
11     for (i=1;i<=maxn;i++)
12         matrix[i]=(double *) malloc (sizeof(double)*(maxn+1));
13     scanf("%ld",&n);
14     for (i=1;i<=n;i++)
15         for (j=1;j<=n;j++)
16             scanf("%lf",&matrix[i][j]);
17     //使第i列的主元下方的值变为0
18     for (i=1;i<=n;i++)
19     {
20         j=i;
21         while (j<=n && fabs(matrix[j][i])<minv)
22             j++;
23         //最后化简的上三角行列式有一个数为0,则矩阵的值为0
24         if (j==n+1)
25         {
26             printf("0.00\n");
27             return 0;
28         }
29         //交换两行位置,值取反
30         if (i!=j)
31         {
32             result*=-1.0;
33             //第i行和第j行进行交换(交换第i~n列的数即可)
34             for (k=i;k<=n;k++)
35             {
36                 s=matrix[i][k];
37                 matrix[i][k]=matrix[j][k];
38                 matrix[j][k]=s;
39             }
40         }
41         //对第j+1行~第n行进行处理(第i+1行到第j行a[][i]的值都为0)
42         //(第t行减去第i行的matrix[j][i]/matrix[i][i]倍,使matrix[j][i]=0)
43         for (k=j+1;k<=n;k++)
44         {
45             s=-matrix[k][i]/matrix[i][i];
46             matrix[k][i]=0;
47             //(修改第i+1~n列的数即可)
48             for (l=i+1;l<=n;l++)
49                 matrix[k][l]+=s*matrix[i][l];
50         }
51     }
52     for (i=1;i<=n;i++)
53         result*=matrix[i][i];
54     if (fabs(result)<0.000001)
55         printf("%.2lf",0.0);
56     else
57         printf("%.2lf",result);
58 
59     return 0;
60 }
61 /*
62 Input:
63 4
64 2 -1 0 3
65 -3 1 2 2
66 1 0 -2 -1
67 -4 3 2 2
68 Output:
69 24.00
70 
71 Input:
72 3
73 1 2 3
74 2 3 4
75 3 4 5
76 Output:
77 0.00
78 
79 Input:
80 2
81 1 2
82 2 1
83 Output:
84 -3.00
85 */

 

3.行简化行列式

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <math.h>
  4 #define maxn 100
  5 #define minv 0.000001
  6 
  7 int main()
  8 {
  9     long n,m,i,j,k,l,pos;
 10     double s;
 11     double matrix[100][100];
 12 //    double **matrix=(double **) malloc (sizeof(double *)*(maxn+1));
 13 //    for (i=1;i<=maxn;i++)
 14 //        matrix[i]=(double *) malloc (sizeof(double)*(maxn+1));
 15     scanf("%ld%ld",&n,&m);
 16     for (i=1;i<=n;i++)
 17         for (j=1;j<=m;j++)
 18             scanf("%lf",&matrix[i][j]);
 19 
 20     pos=1;
 21     //使第i列的主元下方的值变为0
 22     for (i=1;i<=m;i++)
 23     {
 24         j=pos;
 25         //从第pos行开始
 26         while (j<=n && fabs(matrix[j][i])<minv)
 27             j++;
 28         //从第pos行开始,第i列的值全为0,不用简化
 29         if (j==n+1)
 30             continue;
 31         if (pos!=j)
 32             //第pos行和第j行进行交换(交换第i~m列的数即可)
 33             for (k=i;k<=m;k++)
 34             {
 35                 s=matrix[pos][k];
 36                 matrix[pos][k]=matrix[j][k];
 37                 matrix[j][k]=s;
 38             }
 39         //对第pos+1行~第n行进行处理
 40         //(第t行减去第pos行的matrix[j][i]/matrix[pos][i]倍,使matrix[j][i]=0)
 41         for (j=pos+1;j<=n;j++)
 42         {
 43             s=-matrix[j][i]/matrix[pos][i];
 44             matrix[j][i]=0;
 45             //(修改第i+1~m列的数即可)
 46             for (k=i+1;k<=m;k++)
 47                 matrix[j][k]+=s*matrix[pos][k];
 48         }
 49         //若从第pos行开始,第i列的值全为0,则从下一行开始
 50         pos++;
 51     }
 52 
 53     printf("\n");
 54     printf("行阶梯型矩阵:\n");
 55     for (i=1;i<=n;i++)
 56     {
 57         for (j=1;j<=m;j++)
 58             if (fabs(matrix[i][j])<minv)
 59                 //左边的数5代表数输出5位,若位数不够则以空格填充
 60                 //右边的数2代表数保留2位小数
 61                 printf("%5.2lf ",0.0);
 62             else
 63                 printf("%5.2lf ",matrix[i][j]);
 64         printf("\n");
 65     }
 66     //第pos行~第n行的值全部为0,矩阵的秩为pos-1
 67     //对第pos-1行~第1行的内容进行修改
 68     for (i=pos-1;i>=1;i--)
 69     {
 70         for (j=1;j<=m;j++)
 71             //(i,j)即该行的第一个非零数,为主元
 72             if (fabs(matrix[i][j])>minv)
 73                 break;
 74         s=matrix[i][j];
 75         //把主元的值变为1,该行的数都除以matrix[i][j]
 76         for (k=j;k<=m;k++)
 77             matrix[i][k]/=s;
 78         //对第1行~第i-1行进行处理
 79         for (k=1;k<i;k++)
 80         {
 81             s=-matrix[k][j];
 82             matrix[k][j]=0;
 83             //(修改第j+1~m列的数即可)
 84             for (l=j+1;l<=m;l++)
 85                 matrix[k][l]+=s*matrix[i][l];
 86         }
 87     }
 88     printf("\n");
 89     printf("行简化阶梯型矩阵:\n");
 90     for (i=1;i<=n;i++)
 91     {
 92         for (j=1;j<=m;j++)
 93             if (fabs(matrix[i][j])<minv)
 94                 //左边的数5代表数输出5位,若位数不够则以空格填充
 95                 //右边的数2代表数保留2位小数
 96                 printf("%5.2lf ",0.0);
 97             else
 98                 printf("%5.2lf ",matrix[i][j]);
 99         printf("\n");
100     }
101     return 0;
102 }
103 /*
104 Input1:
105 3 4
106 1 2 1 3
107 0 0 0 0
108 0 0 0 1
109 Output:
110 行阶梯型矩阵:
111 1.00  2.00  1.00  3.00
112 0.00  0.00  0.00  1.00
113 0.00  0.00  0.00  0.00
114 
115 行简化阶梯型矩阵:
116 1.00  2.00  1.00  0.00
117 0.00  0.00  0.00  1.00
118 0.00  0.00  0.00  0.00
119 
120 Input2:
121 3 4
122 0 1 -1 2
123 0 0 1 -1
124 0 0 2 1
125 Output:
126 行阶梯型矩阵:
127  0.00  1.00 -1.00  2.00
128  0.00  0.00  1.00 -1.00
129  0.00  0.00  0.00  3.00
130 
131 行简化阶梯型矩阵:
132  0.00  1.00  0.00  0.00
133  0.00  0.00  1.00  0.00
134  0.00  0.00  0.00  1.00
135 
136 Input3:
137 3 3
138 1 2 1
139 2 1 1
140 0 0 0
141 Output:
142 行阶梯型矩阵:
143  1.00  2.00  1.00
144  0.00 -3.00 -1.00
145  0.00  0.00  0.00
146 
147 行简化阶梯型矩阵:
148  1.00  0.00  0.33
149  0.00  1.00  0.33
150  0.00  0.00  0.00
151 
152 Input4:
153 5 6
154 1 2 0 3 2 5
155 -1 1 -3 3 4 7
156 0 -2 2 -4 1 -3
157 2 0 4 -2 0 -2
158 1 0 2 -1 1 0
159 Output:
160 行阶梯型矩阵:
161  1.00  2.00  0.00  3.00  2.00  5.00
162  0.00  3.00 -3.00  6.00  6.00 12.00
163  0.00  0.00  0.00  0.00  5.00  5.00
164  0.00  0.00  0.00  0.00  0.00  0.00
165  0.00  0.00  0.00  0.00  0.00  0.00
166 
167 行简化阶梯型矩阵:
168  1.00  0.00  2.00 -1.00  0.00 -1.00
169  0.00  1.00 -1.00  2.00  0.00  2.00
170  0.00  0.00  0.00  0.00  1.00  1.00
171  0.00  0.00  0.00  0.00  0.00  0.00
172  0.00  0.00  0.00  0.00  0.00  0.00*/

 

方阵求值——上三角行列式、定义(康拓展开求值)