UVa 472 - Simultaneous Equations

#数学 #高斯消元
Published on 2016-03-15

题目地址

描述

请你求解含有 n(1≤n≤100)n(1\le n\le 100) 个未知数，nn 个方程的方程组。数均属于复数域。

样例输入

(1,0) (2,0) (3,0) (14,0)
(2,0) (3,0) (4,0) (20,0)
(3,0) (4,0) (4,0) (23,0)

(1,0) (2,0) (3,0) (4,0)
(2,0) (4,0) (6,0) (8,0)
(3,0) (4,0) (5,0) (26,0)

样例输出

(1.0,0.0)
(2.0,0.0)
(3.0,0.0)

No solution

分析

这题分为两个部分来说：
输入 & 输出：输入的话，弄个 stringstream 搞一搞就行了。输出的话，注意两组数据之间有空格。还有就是题目要求输出一位小数点，而且四舍五入，千万不能用 %.1lf，会有问题，正确的写法是：printf("%.1lf", floor(x * 10 + 0.5) / 10);
算法：由于是复数范围内，有实部和虚部，需要两个未知数。对于复数 a+bia + bi 和 c+dic + di，乘法定义为：

(a+bi)(c+di)=(ac−bd)+(ad+bc)i(a + bi)(c + di) = (ac - bd) + (ad + bc)i

按照这个，我们可以构造出一个 2n∗2n2n * 2n 的方程组，是可解的！

代码

//  Created by Sengxian on 3/15/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 472 高斯消元
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int maxn = 100 + 3;
const double eps = 1e-10;
typedef double Matrix[maxn * 2][maxn * 2];
Matrix real, imag, A;
char str[maxn * maxn], absorber;
int n;

bool gauss_jordan(Matrix a, int n) {
    for (int i = 0; i < n; ++i) {
        int idx = i;
        for (int j = i + 1; j < n; ++j)
            if (fabs(a[j][i]) > fabs(a[idx][i]))
                idx = j;
        if (fabs(a[idx][i]) < eps) return false;
        if (idx != i) for (int j = 0; j <= n; ++j) swap(a[idx][j], a[i][j]);
        for (int j = 0; j < n; ++j) if(i != j)
            for (int k = n; k >= i; --k)
                a[j][k] -= a[i][k] / a[i][i] * a[j][i];
    }
    return true;
}

int main() {
    bool flag = false;
    while(gets(str) != NULL) {
        if(flag) putchar('\n'); else flag = true;
        n = 0;
        for(int i = 0; str[i]; ++i)
            if(str[i] == '(') n++;
        n--;
        for(int i = 0; i < n; ++i) {
            string s(str);
            stringstream ss(s);
            for(int j = 0; j <= n; ++j)
                ss >> absorber >> real[i][j] >> absorber >> imag[i][j] >> absorber;
            gets(str);
        }
        for(int i = 0; i < n; ++i) {
            //构造方程
            for(int j = 0; j < n; ++j)
                A[i * 2][j * 2] = real[i][j], A[i * 2][j * 2 + 1] = -imag[i][j]; 
            A[i * 2][n * 2] = real[i][n];
            for(int j = 0; j < n; ++j)
                A[i * 2 + 1][j * 2] = imag[i][j], A[i * 2 + 1][j * 2 + 1] = real[i][j];
            A[i * 2 + 1][n * 2] = imag[i][n];
        }
        if(gauss_jordan(A, n * 2)) {
            for(int i = 0; i < n; ++i) //注意四舍五入！
                printf("(%.1lf,%.1lf)\n", floor(A[i * 2][n * 2] / A[i * 2][i * 2] * 10 + 0.5) / 10, floor(A[i * 2 + 1][n * 2] / A[i * 2 + 1][i * 2 + 1] * 10 + 0.5) / 10);
        }else puts("No solution");
    }
    return 0;
}
UVa 684 - Integral Determinant