线性方程组a[][]x[]=b[] ： Gauss算法

/*================================================================================================*\

|                                   线性方程组a[][]x[]=b[] ： Gauss算法   

\*================================================================================================*/

#define eps 1e-10                                // 定义精度

#define fabs(x) ((x)>0?(x):-(x))                 // 取绝对值

#define zero(x) (fabs(x)<eps)                  // 判定是否为0

const int maxn = 100;                            // 未知数的个数

double a[maxn][maxn+1]; int n;                   // 增广矩阵

void pmat() {                                    // 输出增广矩阵，默认为浮点型

      for (int i = 0, j; i < n; i++) {

             for (j = 0; j < n; j++)

                     printf("%lf ", a[i][j]);

             printf("%lf\n", a[i][j]);

      }

}

----------------------------------------------------------------------------------------

列主元消元法： 仅在一列当中选取绝对值最大的元素作为消去的主元素的Gauss算法。增广矩阵表示。

----------------------------------------------------------------------------------------

double getMaxRow(int k, int &row) {            // 输出矩阵第a[k..n-1][k]中最大元素和行

      double ret = 0;

      for (int i = k; i < n; i++)

             if (fabs(a[i][k]) > fabs(ret))

                     ret = a[row=i][k];

      return ret;

}

void swapRow(int k, int i) {                   // 交第k行和第i行： a[k] 和 a[i];

      for (int j = k; j <= n; j++)  

             swap(a[k][j], a[i][j]);

}

int gauss() {

      int i, j, k, row;

      double maxp;      // pmat();

      for (k = 0; k < n; k++) {

             maxp = getMaxRow(k, row);

             if (zero(maxp)) return 0;                 // 如果为奇异阵，则有无数解。

             if (row != k) swapRow(k, row);             // 需要交换两行

             for (j = k + 1; j  <= n; j++) {            // 加减法消元。

                     a[k][j] /= maxp;

                     for (i = k+1; i < n; i++)

                             a[i][j] -= a[i][k]*a[k][j];

             }

      }//pmat();

      for (i = n-1; i >= 0; i--)                       // 结果保留在a[0..n-1][n]中

             for (j = i+1; j < n; j++)

                     a[i][n] -= a[i][j]*a[j][n];

      return 1;

}// gauss

----------------------------------------------------------------------------------------

全主元消元法： 选取剩余的最大元素作为消去的主元素，交换行与列的Gauss算法。增广矩阵表示。

----------------------------------------------------------------------------------------

double getMax(int k, int &row, int &col) {          // 在a[k..n][k..n]中查找最大元素

      double ret = 0;                               // 并保留最大元所在的行与列

      for (int i = k; i < n; i++)

             for (int j = k; j < n; j++)

                     if (fabs(a[i][j]) > fabs(ret))

                             ret = a[row=i][col=i];

      return ret;

}

void swapCol(int k, int j) {                       // 交换第k列和第j列

      for (int i = 0; i < n; i++)

             swap(a[i][j], a[i][k]);

}

void swapRow(int k, int i) {                       // 交换第k行和第i行

      for (int j = k; j <= n; j++)

             swap(a[k][j], a[i][j]);

}

int index[maxn]; double t[maxn];                  // 两个辅助数组。

bool gauss() {

      int i, j, k, row, col;

      double maxp;

      for (i = 0; i < n; i++) index[i] = i;

      for (k = 0; k < n; k++) {

             maxp = getMax(k, row, col);

             if (zero(maxp)) return 0;

             if (col != k) {

                     swapCol(k, col);

                     swap(index[col], index[k]); // 这里要交换索引。

             }

             if (row != k) swapRow(k, row);

             for (j = k+1; j <= n; j++) {

                     a[k][j] /= maxp;

                     for (i = k+1; i < n; i++)

                             a[i][j] -= a[i][k]*a[k][j];

             }

      }

      for (i = n-1; i >= 0; i--)

             for (j = i+1; j < n; j++)

                     a[i][n] -= a[i][j]*a[j][n];

      for (k = 0; k < n; k++) t[index[k]] = a[k][n];

      for (k = 0; k < n; k++) a[k][n] = t[k];

      return 1;

}

 

比较： 全主元消元法 和 列主元消元法比较起来，其精度更高，如果要求精度较高的情况，选择全主元消元法，精度较低时，选择列主元消元法。

----------------------------------------------------------------------------------------

高斯-诺尔当消元法：除主对角线元素为1之外其余元素都为零的消元法。增广矩阵表示。

----------------------------------------------------------------------------------------

double getRow(int k, int &row) {            // 获得当前列的a[k..n][k]的第一个非零元

      for (int i = k; i < n; i++)

             if (!zero(a[i][k])) return a[row=i][k];

      return 0;

}

void swapRow(int k, int i) {               // 交行第k行和第i行

      for (int j = k; j <= n; j++)

             swap(a[k][j], a[i][j]);

}

bool gauss() {

      int i, j, k, row;

      double ret;

      for (k = 0; k < n; k++) {

             ret = getRow(k, row);//pmat();

             if (zero(ret)) return 0;

             if (row != k) swapRow(k, row);

             for (j = k; j <= n; j++)

                     a[k][j] /= ret;

             for (j = k+1; j <= n; j++) {

                     for (i = 0; i < k; i++)

                             a[i][j] -= a[i][k]*a[k][j];

                     for (i = k+1; i < n; i++)

                             a[i][j] -= a[i][k]*a[k][j];

             }

      }

      return 1;

}

 

 

 

 

 

 

 

/*================================================================================================*\

|                                   Gauss消元算法求解开关灯问题   

\*================================================================================================*/

----------------------------------------------------------------------------------------

开灯问题告诉N(N<=63)盏灯和M(M<=N)个开关,每个开关可以控制K(K<=N)盏灯，给定N盏灯的初始状态S和要求通过开关控制得到的目标状态E，求可以达到目标状态的方案数。

----------------------------------------------------------------------------------------

简单分析：对于每个开关，有按和不按两种选择（记为0/1）; 对于每盏灯有变和不变两种情况（0/1）,如果初态和终态不一样，那么这盏灯是一定要变化的。由此我们就可以得到一个0/1的矩阵：让N盏灯灯作为列向量，开关作为横向量，把每盏灯是否变化作为第M列（由0开始）这样就得到一个N*(M+1)的矩阵,该矩阵有如下性质：

1. 如果N = M ，那么矩阵为增广矩阵。

2. 该矩阵相当于方程组A * X = B,因此可以求其解。

   1. 若方程组有唯一解，那么，N = M (逆命题：如果M = N ,那么方程组有唯一解 不成立)

   2. 若方程组无实数解，那么，该方程不可以化成严格上三角形式（具体的证明见相关资料，这里不再证明）

   3. 若方程组有多接，即存在自由变元，因为每个自由变元可以取0/1两种情况，那么总共有2^m(m为变元数)解。

下面是经过验证的代码：

int getRow(int p, int q, int &row) {

      for (int i = p; i < n; i++)

             if (!zero(a[i][q])) return a[row=i][q];

      return row=0;

}

void swapRow(int p, int row, int q) {

      for (int k = q; k <= m; k++)

             swap(a[p][k], a[row][k]);

}

i64 gauss() {

      int i = -1, j = -1, k, p, q, ret, row;

      while(++i < n && ++j < m) {

             ret = getRow(i, j, row);

             if (zero(ret)) { i--; continue;}

             if (row != i) swapRow(i, row, j);

             for (p = i+1; p < n; p++) if (a[p][j])

                     for (q = j; q <= m; q++)

                             a[p][q] ^= a[i][q];

      }

      for (k = i; k < n; k++) if(a[k][m]) return -1;

      return (i64)1 << (m-i);

}    //link: hdu3364 http://acm.hdu.edu.cn/showproblem.php?pid=3364

----------------------------------------------------------------------------------------

开关问题：有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。

求： 1. 方案数（自由变元的数目）  2. 给定一个最少的开关方案

----------------------------------------------------------------------------------------

这类问题是上面问题的一种简化：

对于问题一、可以直接套用上面的公式（N=M）

对于问题二、如果构造得到的方程组只有一个解，那么问题解决，这里主要讨论一下多解，存在自由变元的情况。如果存在自由变元，我们就要枚举每个自由变元（0/1）然后比较选择最小。枚举时间复杂度为2^m(m为自由变元的个数)

下面是简单的枚举自由元的算法。

int gans(int a[][maxn+1]) {

      int i, j, ret = a[n-1][n];

      for (i = n-2; i >= 0; i--) {

             for (j = i+1; j < n; j++)

                     a[i][n] ^= a[i][j] && a[j][n];

             ret += b[i][n];

      }

      return ret;

}

void dfs(int p, int k) {

      if (p == k) {

             memcpy(b, a, sizeof(b));

             int ret = gans(b);

             if (ret < ans) ans = ret;

             return;

      }

      a[p][n] = 1; dfs(p-1, k);

      a[p][n] = 0; dfs(p-1, k);

}

int gauss() { //……代码见上（n=m）……//

      dfs(n-1, i-1);

      return ans;

}

Link: pku_1222 http://162.105.81.212/JudgeOnline/problem?id=1222

      pku_1681 http://162.105.81.212/JudgeOnline/problem?id=1681

pku_1753 http://162.105.81.212/JudgeOnline/problem?id=1753

pku_1830 http://162.105.81.212/JudgeOnline/problem?id=1830

      pku_3185 http://162.105.81.212/JudgeOnline/problem?id=3185

 

 

 

 

posted on 2010-08-06 22:57 小志 阅读(410) 评论(0)  编辑 收藏 引用