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

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

题意:

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

题解:

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

Program:

#include#include#include#include#include#include#define ll long long#define MAXN 15using 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;iabs(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=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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。