注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

高斯消元初学  

2014-05-06 07:51:55|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给你N个N元一次方程,用计算机编程求出N元的解。

用代码实现如下:A[I]表示第i个方程,A[I][J]表示i个方程的第j个系数。

for (i=1;i<=n;i++)
    {k=i;
    while (fabs(b[k][i])<=0.000001)k++;
    if (i!=k)
     for (j=1;j<=n+1;j++)
            {t=b[i][j];b[i][j]=b[k][j];b[k][j]=t;}
    for (j=n+1;j>=i;j--)b[i][j]=b[i][j]*1.0/b[i][i];
    for (j=1;j<=n;j++)if (i!=j)
      for (jj=n+1;jj>=i;jj--)
       b[j][jj]=b[j][jj]-b[j][i]*b[i][jj]; 
    }
printf("%.3lf",b[1][n+1]);
for (i=2;i<=n;i++)printf(" %.3lf",b[i][n+1]);

或者下面这份模板:
 
for (i=1;i<=n-1;i++)
 for (j=i+1;j<=n;j++){
                        tem=a[j][i]/a[i][i];
  for (k=i+1;k<=n-1;k++)a[j][k]-=a[i][k]*tem;
  a[j][n+1]-=tem*a[i][n+1];
                       
for (i=n-1;i;i--){
 for (j=i+1;j<=n-1;j++)a[i][n+1]-=a[j][n+1]*a[i][j];
 a[i][n+1]/=a[i][i];want[i]=a[i][n+1];               
                 }
高斯消元还能解异或方程

异或方程组就是形如这个样子的方程组:

M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-1]=B[0]
M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N-1]=B[1]

M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N-1]x[N-1]=B[N-1]

其中“^”表示异或(XOR, exclusive or),M[i][j]表示第i个式子中x[j]的系数,是1或者0。B[i]是第i个方程右端的常数,是1或者0。

解这种方程可以套用高斯消元法,只须将原来的加减操作替换成异或操作就可以了,两个方程的左边异或之后,它们的公共项就没有了。

具体的操作方法是这样的:对于k=0..N-1,找到一个M[i][k]不为0的行i,把它与第k行交换,用第k行去异或下面所有M[i][j]不为0的行i,消去它们的第k个系数,这样就将原矩阵化成了上三角矩阵;最后一行只有一个未知数,这个未知数就已经求出来了,用它跟上面所有含有这个未知数的方程异或,就小觑了所有的着个未知数,此时倒数第二行也只有一个未知数,它就被求出来了,用这样的方法可以自下而上求出所有未知数。(转载)

如bzoj2466开关灯,由于每个灯多按无益,故每个灯只有两种情况按和不按用高斯消元+DFS枚举变元 然后贴下代码:
#include<cstdio>
#include<algorithm>
#include<cstring> 
#define nn 105
#define INF 20000000
using namespace std;
int ans,sum,i,c,d,n,a[nn][nn],x[nn];
void dfs(int w,int sum)
 {int i;
  if (sum>=ans)return;
  if (!w){
         if (sum<ans)ans=sum;
         return;
         }
  if (a[w][w]){int p=a[w][n+1];
              for (i=w+1;i<=n;i++)if (a[w][i])
                  p^=x[i];
              x[w]=p;
              if (p) dfs(w-1,sum+1);
                 else dfs(w-1,sum);
              }else
              {x[w]=1;
               dfs(w-1,sum+1);
               x[w]=0;
               dfs(w-1,sum);
              }
 }
void guess()
 {int i,j,k,f=0;
  for (i=1;i<=n;i++)
             {
    for (j=i;j<=n;j++)if (a[j][i])
                 {
      for (k=1;k<=n+1;k++)swap(a[i][k],a[j][k]);
                f=1;break;
                 }
      if (!f)continue;//自由变元
      for (j=i+1;j<=n;j++)if (a[j][i])   
       for (k=i;k<=n+1;k++)a[j][k]^=a[i][k];          
             }
 ans=INF;
 dfs(n,0);//枚举变元
 printf("%d\n",ans); 
 }
int main()
{
 while (1)
        {
    scanf("%d",&n);
    if (!n)break;
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    for (i=1;i<n;i++){
    scanf("%d%d",&c,&d);
    a[c][d]=a[d][c]=1;
                     }
    for (i=1;i<=n;i++)a[i][i]=a[i][n+1]=1;
    guess(); 
        }
return 0;
}
  评论这张
 
阅读(15737)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018