暑期专题一 高斯消元法

一般来说,对于n个一次方程和n个未知数,可以通过高斯消元法来判断这个方程无解,有唯一解还是有多解。对于一个有唯一解的方程,我们可以通过程序实现加减消元和代入消元,以此来求得这个方程的解。

先贴一个解普通方程的模板:

void Gauss(int m, int n)
{
    int i = 0, j = 0;
    for (; i < m && j < n; i++, j++)
    {
        int mx = i;
        for (int k = i + 1; k < m; k++) if (fabs(a[k][j]) > fabs(a[mx][j])) mx = k;
        if (fabs(a[mx][i]) < eps) {i--; continue;}
        if (mx ^ i) swap(a[mx], a[i]);
        for (int k = 1; k < m; k++) if (k ^ i) 
        {
            double tmp = a[j][i] / a[i][i];
            for (int l = j; l <= n; l++) a[k][l] -= tmp * a[k][l];
        }
    } 
}

1. [JSOI2008 Round1] 球形空间产生器

问题描述

火星人不能忍受地球人对他们的歧视,终于发明了一种非常强大的武器:球形空间产生器。球形空间产生器能产生一个N维球体屏障,而且这个屏障是坚不可摧的,被困在球体内的地球人就被切断了与外界的联系。Js08现在就被困在了屏障中,情况十分危急,必须尽快找出并摧毁球形空间产生器。Js08经过摸索和碰壁,给出了球体上N+1个点的坐标,希望你能够帮Js08找出球形空间产生器的位置——它总是位于球形空间的球心。

输入格式

第一行为整数N,代表了空间的维度。
  接下来N+1行,每行N个实数代表一个坐标。输入数据精确到小数点后6位。
  输入数据保证输出结果唯一。

输出格式

输出一行N个实数,代表球心的坐标,精确到小数点后三位。相邻的数字之间用一个空格分开(行末无空格)。

数据规模:

对于40%的数据,1<=n<=3

对于100%的数据,1<=n<=10   思路:这个题其实就是一个高斯消元的板题。为什么呢?我们来看题。 首先,假设这个球心为 (X1, X2, X3, X4, ... , Xn) ,第i个球的坐标为(Xi1, Xi2, Xi3, Xi4, ... , Xin)
上一篇:map和json之间的转换


下一篇:人口最多的年份