多项式求值

题目:

输入格式

输入的第一行为一个整数 mm（1 \leq m < 181≤m<18），表示多项式共有 mm 项。之后输入 mm 行，每行有两个元素，分别表示多项式各项的系数 cc 与次数 ee（1 \leq c_i < 1001≤ci​<100，1 \leq n < 251≤n<25）。最后一行为待求多项式的变量值 x_0x0​（1 \leq x_0 < 51≤x0​<5）。

输出格式

输出只有一行，即多项式的计算结果。结果保证在int范围内。

样例输入

3
1 2
2 1
1 0
3

样例输出

16

#include<iostream>
#include<cmath>
using namespace std;


typedef struct Vector {
	int size;
	int length;
	int *c;
	int *e;
}Vector;


void inint(Vector *vector, int size) {
	vector->size = size;
	vector->length = 0;
	vector->c = (int*)malloc(sizeof(int)*size);
	vector->e = (int*)malloc(sizeof(int)*size);
}
//用两个数组分别存放系数和指数


void expand(Vector *vector) {
	int *old_c = vector->c;
	int *old_e = vector->e;
	vector->size = vector->size + 1;
	vector->c = (int*)malloc(sizeof(int)*vector->size);
	vector->e = (int*)malloc(sizeof(int)*vector->size);
	for (int i = 0; i<vector->length; i++) {
		vector->c[i] = old_c[i];
		vector->e[i] = old_e[i];
	}
	free(old_c);
	free(old_e);
}


Vector *insert(Vector *vector, int loc, int coef, int expon) {
	if (loc<0 || loc>vector->length) {
		return vector;
	}
	if (vector->length >= vector->size) {
		expand(vector);
	}
	for (int i = vector->length; i>loc; i--) {
		vector->c[i] = vector->c[i - 1];
		vector->e[i] = vector->e[i - 1];
	}
	vector->c[loc] = coef;
	vector->e[loc] = expon;
	vector->length++;
	return vector;
}
//按照题目要求，插入的函数可以少一个loc参数。
//此处将程序写得更完整，虽然会在使用时稍显麻烦，但利于维护和修改。


int main()
{
	Vector *vector = (Vector*)malloc(sizeof(Vector));
	inint(vector, 18);
	int m;
	cin >> m;
	int coef, expon;
	for (int i = 0; i<m; i++) {
		cin >> coef >> expon;
		vector = insert(vector, vector->length, coef, expon);
	}


	int x;
	cin >> x;
	int answer = 0;
	for (int i = 0; i<vector->length; i++) {
		answer = answer + vector->c[i] * pow(x, vector->e[i]);
	}
	//这里求值采用的是直接一项一项地暴力求值，仍然测试通过，但理论上有更优算法。
	cout << answer << endl;


	/*for(int i=0;i<vector->length;i++){
	printf("c[%d]=%d e[%d]=%d\n",i,vector->c[i],i,vector->e[i]);
	}*/




	return 0;
}