用直接计算法和秦九韶算法求解一元n次多项式

一、实验目的

1. 掌握秦九韶算法求解多项式的基本原理；
2. 分别编程实现用直接计算法和秦九韶算法求解一元n次多项式 f(x)=3x⁶+4x⁴-2x³-7x²+x-8在x=2.5时的值；
3. 比较两种算法求解多项式的时间。

二、实验设备

1. 编程语言：C；
2. 实验环境：已安装相关编程环境的计算机1台。

三、算法实现及结果分析

#include<stdio.h>
#include<math.h>
#include<time.h>
#define max 10
#define maxt 1e6
clock_t start, stop;
double duration;
//直接法
double f(double x,double a[],int n) {
	int i;
	double y=0;
	for (i = 0;i < n;i++) {
		y += a[i] * pow(x, n - i-1);
	}
	return y;
}
//秦九韶算法
double q(double x, double a[],int n) {
	int i;
	double y=0;
	for (i = 0;i <n;i++) {
		y = y * x + a[i];
	}
	return y;
}
//比较两种算法求解多项式的时间
void run(double(*f)(double, double*, int), double a[], int case_n,int n,int x) {
	int i;
	start = clock();
	for (i = 0;i < maxt;i++) {
		(*f)(x, a, n);
	}
	stop = clock();
	duration = ((double)(stop - start)) / CLK_TCK;
	printf("第%d种算法打点次数 =%f\n", case_n, (double)(stop - start));
	printf("时间为 =%6.2e\n", duration);
}
int main() {
	double x;
	int n;
	double a[max];
	printf("输入x的值\n");
	scanf_s("%lf", &x);
	printf("输入多项式的最高项的次数\n");
	scanf_s("%d", &n);
	for (int i = 0;i < n+1;i++) {
		printf("第%d项多项式系数为：",i + 1);
		scanf_s("%lf", &a[i]);
	}
	double t1=f(x, a,n+1);
	double t2=q(x, a,n+1);
	printf("直接计算：%lf\n",t1);
	printf("秦九韶算法：%lf\n", t2);
	run(f, a, 1,n+1,x);
	run(q, a, 2,n+1,x);
	return 0;
}

maxt=1e5

maxt=1e6

maxt=1e7

由运行结果我们可知，直接法与秦九韶算法的时间差距在10倍左右。