（C++）给定各系数和变量x的值时计算多项式的值，要求时间尽可能少。

￡神魔★判官ぃ 2023-02-26 07:24 147阅读 0赞

编写算法以计算在给定各系数和变量x的值时的多项式![f\_n(x)][f_n_x]的值，要求时间尽可能少。

（提示：可将各系数存储在数组A中；      另外，**乘法运算的时间是加法运算时间的数倍**）

![f\_n(x)=a\_nx^n +a\_\{n-1\}x^\{n-1\}+a\_\{n-2\}x^\{n-2\}+...+a\_2x^2+a\_1x+a\_0][f_n_x_a_nx_n _a_n-1_x_n-1_a_n-2_x_n-2_..._a_2x_2_a_1x_a_0]

这题可以将![f\_n(x)][f_n_x]因式分解，减少计算的时间复杂度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

原来需要约![\\frac\{n(n+1)\}\{2\}][frac_n_n_1_2]次乘法，n次加法；

改进后需要约n次乘法、n次加法；

代码表示：

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main(int argc, char** argv) {
    	cout<<"逐个读入  an，an-1, an-2... ,以空格隔开"<<endl;
    	vector<int> a;
    	int i = 0;
    	do{
    		cin >> i;
    		a.push_back(i);
    	}while(getchar() !='\n');
    	
    	int x;
    	cout<<"x=?"<<endl;
    	cin>>x; 
    	
    	int value = a[0];
    	for(int i=0;i<a.size()-1;i++)
        {
            value = value*x+a[i+1];
        }
        
        cout<<"计算结果为： "<<value; 
    	return 0;
    }

>  逐个读入  an，an-1, an-2... ,以空格隔开  
> 1 2 3 4  
> x=?  
> 2  
> 计算结果为： 26  
> \--------------------------------

验算得：![1\*2^3+2\*2^2+3\*2+4=26][1_2_3_2_2_2_3_2_4_26]

[f_n_x]: https://private.codecogs.com/gif.latex?f_n%28x%29
[f_n_x_a_nx_n _a_n-1_x_n-1_a_n-2_x_n-2_..._a_2x_2_a_1x_a_0]: https://private.codecogs.com/gif.latex?f_n%28x%29%3Da_nx%5En%20&plus;a_%7Bn-1%7Dx%5E%7Bn-1%7D&plus;a_%7Bn-2%7Dx%5E%7Bn-2%7D&plus;...&plus;a_2x%5E2&plus;a_1x&plus;a_0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/126d5646783e440e9c0c6ba75f0813d8.png
[frac_n_n_1_2]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bn%28n&plus;1%29%7D%7B2%7D
[1_2_3_2_2_2_3_2_4_26]: https://private.codecogs.com/gif.latex?1*2%5E3&plus;2*2%5E2&plus;3*2&plus;4%3D26