P1067[NOIP2009 普及组]多项式输出 递归题解

· · 题解

题目
这道题可以用递归的方法来解决。
我们可以让函数每次输出一个项，然后让它调用自身输出下一项，直到最后一个项。

大致流程：
 1.输入n和n个系数，并把n个数存入vector<int>a中.
 2.将存储项数的容器a,当前项的系数a[xishu]对应的xishu,
   当前项的次数i,表示当前项是否为首项的flag
   传入函数f.
 3.如果i<0,函数f终止.
 4.否则,函数f输出多项式中的一项,
   并返回
   f(a,xishu+1,i-1,false/*(下一项一定不是首项)*/).

明显地，第一次传入f的参数为(a,0,n,true)。
根据这些，我们能列出以下代码： 

#include<bits/stdc++.h>
using namespace std;
int n;
void f(vector<int>a,int xishu,int i,bool flag){
    if(i<0) return;
    /*输出一个项*/
    f(a,xishu+1,i-1,false);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    cin>>n;
    vector<int>a(n+1,0);
    for(int i=0;i<n+1;i++) cin>>a[i];
    f(a,0,n,true);
    return 0;
}

接下来，我们来输出一个项(我在这跌了好几次)。
为了让逻辑更清晰(也为了让我写代码更容易)，我定义了这些bool变量和char变量：

//是否显示系数|项|符号|x|次数
bool xsxishu=true,xsxiang=true,xssign=true,xsx=true,xscishu=true;
//符号
char sign='+';

只要再做一次判断：

if(a[xishu]<0)/*系数为负*/sign='-';
if((a[xishu]*a[xishu]==1)&&(i))/*系数为1或-1且次数不为0*/xsxishu=false;
if(!a[xishu])/*系数为0*/xsxiang=false;
if((flag)&&(sign=='+'))/*是首项且符号为+*/xssign=false;
if(!i)/*次数为0*/xsx=false;
if(i==1||!i)/*次数为0或1*/xscishu=false;

就可以输出了：

//输出项
if(xsxiang){
    if(xssign) cout<<sign;
    if(xsxishu) cout<<abs(a[xishu]);
    if(xsx) cout<<"x";
    if(xscishu) cout<<"^"<<i;
}

最后，只要把这些代码和起来，代码就写好了！

AC Code:

#include<bits/stdc++.h>
using namespace std;
int n;
//递归函数
/*
vector<int>a:存储项数的容器.
int xishu:a[xishu]为当前函数处理的项的系数.
int i:当前函数处理的项的系数.
bool flag:当前函数处理的项是否为首项.
*/
void f(vector<int>a,int xishu,int i,bool flag){
    //终止条件
    if(i<0) return;
    //是否显示系数|项|符号|x|次数
    bool xsxishu=true,xsxiang=true,xssign=true,xsx=true,xscishu=true;
    //符号
    char sign='+';
    if(a[xishu]<0)/*系数为负*/sign='-';
    if((a[xishu]*a[xishu]==1)&&(i))/*系数为1或-1且次数不为0*/xsxishu=false;
    if(!a[xishu])/*系数为0*/xsxiang=false;
    if((flag)&&(sign=='+'))/*是首项且符号为+*/xssign=false;
    if(!i)/*次数为0*/xsx=false;
    if(i==1||!i)/*次数为0或1*/xscishu=false;
    //输出项
    if(xsxiang){
        if(xssign) cout<<sign;
        if(xsxishu) cout<<abs(a[xishu]);
        if(xsx) cout<<"x";
        if(xscishu) cout<<"^"<<i;
    }
    //调用自身，输出下一项
    f(a,xishu+1,i-1,false);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    cin>>n;
    vector<int>a(n+1,0);
    for(int i=0;i<n+1;i++) cin>>a[i];
    f(a,0,n,true);
    return 0;
}

END.