UVALive 6184 - One-Dimensional Cellular Automaton 高斯消元模板题 (2012 Tokyo)

                  题意:

                           设f(x)多项式的最大幂为d...现在告诉f(0)~f(d+2)的值..其中有一个是错的..问哪个是错的...

                  题解:

                           直接枚举+高斯消元暴力..

Program:

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#define ll long long
#define MAXN 15
using namespace std;
//----------------gauss消元,从0开始矩阵为matrix--------
double matrix[MAXN][MAXN+1],ans[MAXN];
void exchange_col(int p1,int p2,int n)
{
for (int i=0;i<=n;i++) swap(matrix[p1][i],matrix[p2][i]);
}
bool gauss(int n)
{
int i,j,k,p;
double r;
for (i=0;i<n-1;i++)
{
p=i;
// output(n);
for (j=i+1;j<n;j++)
if (abs(matrix[j][i])>abs(matrix[p][i])) p=j;
if (p!=i) exchange_col(i,p,n);
if (abs(matrix[i][i])<1e-3) return false;
for (j=i+1;j<n;j++)
{
r=matrix[j][i]/matrix[i][i];
for (k=i;k<=n;k++) matrix[j][k]-=r*matrix[i][k];
}
}
for (i=n-1;i>=0;i--)
{
ans[i]=matrix[i][n];
for (j=n-1;j>i;j--) ans[i]-=matrix[i][j]*ans[j];
if (abs(matrix[i][i])<1e-3) return false;
ans[i]/=matrix[i][i];
}
return true;
}
//---------------------gauss消元模板--------------------------
double data[MAXN];
int main()
{
int d,i,j,t,m,p;
// freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
while (~scanf("%d",&d) && d)
{
for (i=0;i<=d+2;i++) scanf("%lf",&data[i]);
for (t=0;t<=d+2;t++)
{
// t=2;
m=0;
for (i=0;i<=d+2;i++)
{
if (i==t) continue;
p=1;
for (j=0;j<=d;j++) matrix[m][j]=p,p*=i;
matrix[m][d+1]=data[i];
m++;
}
if (!gauss(m)) break;
}
printf("%d\n",t);
}
return 0;
}