洛谷P1067 [NOIP2009 普及组] 多项式输出

Tomorrowland 2024-07-28 10:39:00 阅读 69

题目链接:- P1067 [NOIP2009 普及组] 多项式输出

题目叙述:

[NOIP2009 普及组] 多项式输出

题目描述

一元 n 次多项式可用如下的表达式表示:

  1. 多项式中自变量为 x,从左到右按照次数递减顺序给出多项式。

  2. 多项式中只包含系数不为 0 的项。

  3. 如果多项式 n 次项系数为正,则多项式开头不出 <code>+ 号,如果多项式 n 次项系数为负,则多项式以 - 号开头。

  4. 对于不是最高次的项,以 + 号或者 - 号连接此项与前一项,分别表示此项系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于 0 次的项,其系数的绝对值为 1,则无需输出 1)。如果 x 的指数大于 1,则接下来紧跟的指数部分的形式为“x^b”,其中 b 为 x 的指数;如果 x 的指数为 1,则接下来紧跟的指数部分形式为 x;如果 x 的指数为 0,则仅需输出系数即可。

  5. 多项式中,多项式的开头、结尾不含多余的空格。

输入格式

输入共有 2 行

第一行 1 个整数,n,表示一元多项式的次数。

第二行有 n+1 个整数,其中第 i 个整数表示第 n-i+1 次项的系数,每两个整数之间用空格隔开。

输出格式

输出共 1 行,按题目所述格式输出多项式。

样例 #1

样例输入 #1

5

100 -1 1 -3 0 10

样例输出 #1

100x^5-x^4+x^3-3x^2+10

样例 #2

样例输入 #2

3

-50 0 0 1

样例输出 #2

-50x^3+1

提示

NOIP 2009 普及组 第一题

对于100%数据, 0<=n<=100, -100<= 系数<=100;

思路:

这题乍一看要分很多种情况,是不是第一位数字?,有没有符号?要不要输出指数上的那个数字?如果我们从这些角度出发的话,这道题就复杂无比,要细分很多种情况,我们不妨从结果的输出观察

结果的输出包括:

  1. 符号(如果系数不是负数的话,就得输出'+'(除掉第一项外),如果系数是负数的话,就看需不需要单独输出"-",系数是除-1以外的数字,我们就不用输出'-',否则要输出'-')
  2. 系数(只要系数不为正负1,或者后面x的指数为0,我们就得输出这个系数,不过正负1还得特殊处理一下)
  3. x的指数(如果为1,我们就输出'x',否则输出"x^i",i为指数,x的指数为0 ,我们就直接输出系数,所以说这里的系数为-1的情况需要特殊处理一下)

步骤讲解:

我们观察到,这个x的指数是从n一直递减到0的,如果输入的系数为0时,就不做任何处理,所以我们可以边输入边处理,如果输入的系数为0,就直接进入下一轮循环

  1. 首先,我们要先处理系数输出的问题,什么时候要输出'+',什么时候要输出'-'?

输出'+'的时候:不为第一项,并且系数要大于0(小于0的时候系数自带负号,直接输出即可)

输出'-'的时候:x的指数不为0,并且系数为-1(因为其它的负数自带负号,直接输出其它负数的系数就可以输出那个负号了,-1是一个例外)

代码如下:

//注意输出的顺序,我们应该是有符号就先输出符号,没有符号就考虑系数,有系数(系数不是正负1),就输出系数,最后输出x和x的指数

//输出+号

if (i != n && a > 0) cout << "+";

//输出-号,需要系数为-1,并且指数不为0

if (a == -1 && i != 0) cout << "-";

  1. 输出系数,我们要明确我们什么时候会输出系数?要系数的值不为正负1,或者是指数为0的情况,我们就需要将正负1的那个系数放出来了,对吧?代码如下:

<code>//输出系数,需要系数不为正负1,或者后面的指数为0,系数为-1,x的指数为0的情况在这里。

if (abs(a) > 1 || i == 0) cout << a;

  1. 输出x和它的指数,这一步是最简单的,我们只需要知道指数是不是为1即可(指数为0的情况在前面已经处理了)代码如下:

<code>//输出x,只有指数为1,这一种情况

if (i == 1) cout << "x";

//输出x^i这种形式,需要指数>1

if (i > 1) cout << "x^" << i;

完整的代码如下:

#include<iostream>

using namespace std;

int main()

{

int n; cin >> n;

for (int i = n; i >= 0; i--) {

int a; cin >> a;

//如果当前数字为0,就直接跳过

if (a != 0) {

//注意输出的顺序,我们应该是有符号就先输出符号,没有符号就考虑系数,有系数(系数不是正负1),就输出系数,最后输出x和x的指数

//输出+号

if (i != n && a > 0) cout << "+";

//输出-号,需要系数为-1,并且指数不为0

if (a == -1 && i != 0) cout << "-";

//输出系数,需要系数不为正负1,或者后面的指数为0,系数为-1,x的指数为0的情况在这里。

if (abs(a) > 1 || i == 0) cout << a;

//输出x,只有指数为1,这一种情况

if (i == 1) cout << "x";

//输出x^i这种形式,需要指数>1

if (i > 1) cout << "x^" << i;

}

}

return 0;

}

自己跑一遍流程

很多时候我们都不知道我们写的代码是否有bug,而且如果是竞赛中写题,部分竞赛会有罚时,这时候我们就需要自己模拟着去跑一遍流程了

首先,输入系数,如果系数为0,直接跳过,进入下一层循环,否则,就进入处理的逻辑

如果这是第一项的话,就进入处理系数的环节,执行if (abs(a) > 1 || i == 0) cout << a;这条语句

否则,进入第一条语句:if (i != n && a > 0) cout << "+";,输出+号,然后再进入上面那条语句,然后再处理系数

然后就是处理x和它的指数了,似乎没问题,我们把特殊的几种情况罗列一下,看看能不能正确处理,如果能,那就是对的

  1. 输入第一项,我们会进入处理系数的步骤,没问题
  2. 输入负的系数,并且不为正负1,我们会进入直接输出系数的步骤,没问题
  3. 输入系数为-1,但是指数为0,我们仍然会输出这个系数,没问题。
  4. 输入系数为1,但是指数也为0,我们也会输出这个系数,也没问题。

我们还可以列举多几种情况,检查一下,其实我们这个逻辑是没有问题的。

总结与反思

做题不要一上来就把所有的情况列举出来,有时候所有情况列举出来只会复杂度很,我们需要从大局上面观察



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。