题目链接:uva 1397 - The Teacher's Side of Math
题目大意:给出一个方程的解x=a1/m+b1/n,求原方程(给出系数即可)
解题思路:因为方程肯定等于0,所以对于各个系数ax/mby/n都会等于0,于是可以根据这个列出方程,注意最高项的系数始终为1.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxc = 20;
const int maxn = 40;
typedef long long ll;
typedef double Mat[maxn][maxn];
ll A, M, B, N, C[maxc+5][maxc+5];
Mat G;
void getc (int n) {
for (int i = 0; i <= n; 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 init () {
memset(G, 0, sizeof(G));
int n = N * M;
for (int i = 0; i <= n; 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;
G[l*N+r][i] += tmp;
}
}
G[n][n] = 1;
G[n][n+1] = 1;
}
void gauss_elimin (int n) {
for (int i = 0; i < n; i++) {
int r = i;
for (int j = i + 1; j < n; j++)
if (fabs(G[j][i]) > fabs(G[r][i]))
r = j;
if (r != i) {
for (int j = 0; j <= n; j++)
swap(G[r][j], G[i][j]);
}
if (fabs(G[i][i]) < 1e-9)
continue;
for (int k = i + 1; k < n; k++) {
double f = G[k][i] / G[i][i];
for (int j = 0; j <= n; j++)
G[k][j] -= G[i][j] * f;
}
}
for (int i = n-1; i >= 0; i--) {
for (int j = i+1; j < n; j++)
G[i][n] -= G[j][j] * G[i][j];
G[i][i] = G[i][n] / G[i][i];
if (fabs(G[i][i]) < 1e-9)
G[i][i] = 0;
}
printf("%.0f", G[n-1][n-1]);
for (int i = n-2; i >= 0; i--)
printf(" %.0f", G[i][i]);
printf("\n");
}
int main () {
getc(maxc);
while (scanf("%lld%lld%lld%lld", &A, &M, &B, &N) == 4 && A + M + B + N) {
init();
gauss_elimin (N * M + 1);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC