UVA 1397 - The Teacher's Side of Math(高斯消元)

本文主要是介绍UVA 1397 - The Teacher's Side of Math(高斯消元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 1397 - The Teacher's Side of Math

题目链接

题意：给定一个x=a1/m+b1/n，求原方程组

思路：由于m*n最多20，所有最高项只有20，然后可以把每个此项拆分，之后得到n种不同无理数，每一项为0，就可以设系数为变元，构造方程进行高斯消元

一开始用longlong爆了，换成分数写法也爆了，又不想改高精度，最后是机智的用了double型过的，不过用double精度问题，所以高斯消元的姿势要正确，并且最后输出要注意-0的情况

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;typedef long long ll;const int N = 25;
const double eps = 1e-9;ll a, m, b, n, C[N][N];
int hash[N][N], tot;double A[N][N];void build() {memset(A, 0, sizeof(A));A[0][0] = 1;for (int i = 1; i <= tot; i++) {for (int j = 0; j <= i; j++) {int l = j, r = i - j;double tmp = C[i][l] * pow(a * 1.0, l / m) * pow(b * 1.0, r / n);l %= m; r %= n;A[hash[l][r]][i] += tmp;}}A[tot][tot] = 1;A[tot][tot + 1] = 1;tot++;
}void getC() {for (int i = 0; i <= 20; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++)C[i][j] = C[i - 1][j - 1] + C[i - 1][j];}
}void gethash() {tot = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {hash[i][j] = tot++;}}
}void print(double x) {char s[100];sprintf(s, "%.0lf", x);if (strcmp(s, "-0") == 0) printf(" %s", s + 1);else printf(" %s", s);
}void gauss() {for (int i = 0; i < tot; i++) {int r = i;for (int j = i + 1; j < tot; j++) {if (fabs(A[j][i]) > fabs(A[r][i]))r = j;}if (fabs(A[r][i]) < eps) continue;for (int j = i; j <= tot; j++)swap(A[r][j], A[i][j]);for (int j = 0; j < tot; j++) {if (i == j) continue;if (fabs(A[j][i]) >= eps) {double tmp = A[j][i] / A[i][i];for (int k = i; k <= tot; k++)A[j][k] -= tmp * A[i][k];}}}printf("1");for (int i = tot - 2; i >= 0; i--)print(A[i][tot] / A[i][i]);printf("\n");
}int main() {getC();while (~scanf("%lld%lld%lld%lld", &a, &m, &b, &n)) {if (!a && !m && !b && !n) break;gethash();build();gauss();}return 0;
}

这篇关于UVA 1397 - The Teacher's Side of Math(高斯消元)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---