新题--多项式类的题目

佚名 6年前 (2019-05-13) 随笔 625人围观抢沙发百度已收录

第一题：poj 1060

题目介绍：给你三个多项式，分别为a,b,c，求(a*b)%c，其中还有一些特定的规则，比较难懂！！！

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解题链接：https://blog.csdn.net/xiamusansan/article/details/90175793

解决的问题：对多项式P_n(x)= a_nxⁿ ＋a_n_－１xⁿ^－１＋…＋a_１x＋a_０求值

递推的关系P_i(x)= xP_i_－₁(x)＋a_n_－_i，递推的临界值P₀(x)= a_n，其中i=1…n。

关键代码：

1 for(int i=n-1;i>=0;i--)
2 ans=x*ans+a[i];

问题代码：

 1 #include <iostream>
 2 using namespace std;
 3 int Horner_rule(int arr[],int n,int x)
 4 {
 5     int i,ans = 0;;
 6     for(i =n-1;i>=0;i--)
 7     {
 8         ans =arr[i]+x*ans;
 9     }
10     return ans;
11 }
12 int main()
13 {
14     int n,x,i,t,arr[1000];
15     cout<<"请输入需要测试的案例数目：" <<endl;
16     cin>>t;//案例数 
17     while(t--)
18     {
19         cout<<"输入:n和x : ";
20         cin>>n>>x;
21         cout<<"请输入 "<<n <<" 个系数: ";
22         for(i = 0;i<n;i++)//求值是从 an 开始，所以倒着存
23         cin>>arr[i];
24         for(i = 0;i<n-1;i++)
25         cout<<arr[i]<<"*x"<<"^"<<i<<"+";
26         cout<<arr[i]<<"*x"<<"^"<<i<<" = ";
27         cout<<Horner_rule(arr,n,x)<<endl;
28     }
29     return 0;
30 }