可以用高斯消元吗
查看原帖
可以用高斯消元吗
587428
1577698530a楼主2022/4/22 11:31
#pragma warning(disable:6031)
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<utility>
#include<list>
#include<numeric>
#include<bitset>`

using namespace std;
int infinity = 0x7fffffff, infinity2 = 0x3f3f3f3f;
const int maxn = 1000000;
//scanf_s("%d(int),%c(char),%s([]),%lf(double),%f(float),len,&p)
//printf("%..",p),cin.getline(&buf,255) char buf[200] or string buf;
// long long 可以存9万亿 9223372036854775807;
//memset(f, 0x3f, sizeof f);
typedef long long ll;
const long long mod = 2147483648;
double eps = 1e-6;
double a[20][20],x[20];int n,num,free_x[20],lp;
inline long long read()
{
    ll s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++)   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) {
            free_x[num++] = c;            
            continue;
        }

        for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i--) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i++)       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];

        r++;
    }

    if (r < n)
    {
        lp = r;
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}
vector<ll>ans;
void enum_freex(int var) {
   
    for (int i = 0; i < num; ++i) 
    {        
           x[free_x[i]] = 1;           
    }
    for (int i = n -1; i >= 0; i--)
    {
        for (int j = i + 1; j < n; j++)
        {
            a[i][n] -= a[i][j] * x[j];
        }
        x[i] = a[i][n];
    }
   
}
void print() {
    for (int i = n - 1; i >= 0; i--)ans.push_back(a[i][n]+0.5);
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)cout << ans[i]<<" ";
}
int main()
{
	
	n = read();
	for (int i = 0; i < n; i++)
	{		
        a[i][i] = 1;
        a[i][i + 1] = 1;
		a[i][n] = read();
	}
    
    
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            cout << a[i][j] << " ";
     
        }
        cout << endl;
    } */
   
  
       
        a[n - 1][0] = 1.0;
        int k = gauss();
        //cout << k << endl;
        if (k == 2)cout << "Impossible";
        else if (k == 0) {
            print();                    
        }
        else {
            enum_freex(n-lp);
            print();           
        }

	

}
2022/4/22 11:31
加载中...