2212.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2212 on 2006-04-18 at 12:05:26 */ 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

typedef long long int64;
const int L = 512;
const int PN = 10;

int coe[PN];

void analyze(char*);
void derivative();
void print(int, bool);
int64 comp(int);
int64 pow(int, int);

int main()
{
	char poly[L];
	int t, T;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		int x; scanf("%d\n", &x);
		printf("POLYNOMIAL %d\n", t);
		printf("%s\n", gets(poly));
		analyze(poly);
		derivative(); print(0, true); print(x, false);
		printf("%lld\n", comp(x));
	}
	
	return 0;
}

void analyze(char* p)
{
	memset(coe, 0, sizeof(coe));
	int sgn = 1;
	while(*p != 0)
		if(*p == '+' || *p == '-') sgn = (*(p++) == '+') ? 1 : -1;
		else {
			int k = 1, cof = 0;
			if(isdigit(*p)) k = *(p++) - '0';
			if(*p == 'x') { 
				cof = 1; p++;
				if(*p == '^') { p++; cof = *(p++) - '0'; }
			}
			coe[cof] += sgn * k;
		}
}
void derivative()
{
	int i;
	for(i = 1; i < 10; i++) coe[i-1] = coe[i] * i;
	coe[9] = 0;
}
void print(int x, bool var)
{
	bool pr = false;
	int i;
	for(i = 9; i >= 0; i--) {
		if(coe[i] == 0) continue;
		if(pr && coe[i] > 0) putchar('+');
		if(coe[i] != 1 || i == 0) printf("%d", coe[i]);
		if(i != 0)
			if(var) putchar('x');
			else printf("(%d)", x);
		if(i > 1) printf("^%d", i);
		pr = true;
	}
	if(!pr) putchar('0');
	putchar('\n');
}
int64 comp(int x)
{
	bool pr = false;
	int64 i, v = 0;
	for(i = 9; i >= 0; i--) {
		if(coe[i] == 0) continue;
		int64 cv = coe[i] * pow(x, i);
		if(pr && cv >= 0) putchar('+');
		printf("%lld", cv);
		pr = true; v += cv;
	}
	if(!pr) putchar('0');
	putchar('\n');
	return v;
}
int64 pow(int x, int p)
{
	int i; int64 v = 1;
	for(i = 0; i < p; i++) v *= x;
	return v;
}