Problem Set 4(Polynomial Addition)

Polynomial Addition

Q.Write an algorithm and the subsequent Python program to add the two given polynomials. Assume that the coefficients of each polynomial are stored in a separate list.

Eg: 4x3 + 3x + 1 can be stored as [4,0,3,1]

2x2 - 3x - 4 can be stored as [2,-3,-4]

Output is [4, 2, 0, -3]

Input Format:

First line contains the degree of the first polynomial

Next line contains the coefficient of xˆn

Next line contains the coefficient of xˆn-1

...

Next line contains the coefficient of xˆ0

Next line contains the degree of the second equation

Next line contains the coefficient of xˆn

Next line contains the coefficient of xˆn-1

...

Next line contains the coefficient of xˆ0

Output Format:

Coefficients as a list from the highest degree to the lowest degree

Input:

Degree of first polynomial, the coefficients of the 1^st polynomial, degree of the second polynomial, the coefficients of the 2^nd polynomial

Processing:

polynomial1 = []

for i in range(num1):

    polynomial1.insert(i,eval(input()))

polynomial2 = []

for i in range(num2):

    polynomial2.insert(i,eval(input()))

if num1 < num2:

    for i in range(num2-num1):

        polynomial1.insert(0,0)

else:

    for i in range(num1-num2):

        polynomial2.insert(0,0)

maxi = num1 if num1 >= num2 else num2

total = []

for i in range(maxi):

    total.insert(i,polynomial1[i]+polynomial2[i])

Output:

The added polynomial coefficients as a list(total)

 

Program:

num1 = int(input())

polynomial1 = []

for i in range(num1+1):

    polynomial1.insert(i,eval(input()))

num2 = int(input())

polynomial2 = []

for i in range(num2+1):

    polynomial2.insert(i,eval(input()))

if num1 < num2:

    for i in range(num2-num1):

        polynomial1.insert(0,0)

elif num1 > num2:

    for i in range(num1-num2):

        polynomial2.insert(0,0)

maxi = num1+1 if num1 >= num2 else num2+1

total = []

for i in range(maxi):

    total.insert(i,polynomial1[i]+polynomial2[i])

print(total)

Pseudocode:

Step1. Get the degree of the first polynomial(num1)

Step2. assign polynomial1 as an empty list

Step3. initialize i as 0

Step4. Repeat till i is less than num1

Step4.1 get coefficient of the (n-i)th of the first polynomial and the insert it in the ith position of polynomial1 list

Step5. assign polynomial2 as an empty list and reinitialize i as 0

Step6. Repeat till i is less than num2

Step6.1 get coefficient of the (n-i)th of the second polynomial and the insert it in the ith position of polynomial2 list

Step7. If num1 is greater than num2 then proceed to Step9 else to Step10 after proceeding to Step8

Step8. initialize i as 0

Step9. repeat till i is less than num2 - num1 insert 0 at the 0th position of polynomial1 list

Step10. repeat till i is less than num1 - num2 insert 0 at the 0th position of polynomial2 list

Step11. assign maxi as num1 if num1 is greater than or equal to num2 else num2

Step12. assign total as an empty list

Step13. reinitialize i as 0

Step14. repeat until i is less than maxi

Step14.1. insert the sum of ith of polynomial1 and ith of polynomial2 into the ith position of total

Step15. display total    

Step16. End

Flowchart:

To edit this flowchart click on this