Polynomial representation using Arrays



A polynomial is a mathematical expression that contains more than two algebraic terms. It is a sum of several terms that contain different powers of the same variable. $p(x)$ is the representation of a polynomial. A polynomial expression representation consists of at least one variable, and typically includes constants and positive constants as well. It is represented as $a_nx^n+ a_{n-1}x^{n−1}+a_{n-2}x^{n−2}+.............+a_0x^0$, where $x$ is the variable, $(a_0,a_1,a_2,....................,a_n)$, are the coefficients and $n$ is the degree of the polynomial. The coefficients must be a real number.It is necessary for the polynomial expression that each expression consists of two parts:

Coefficient part
Exponent part

Example:

$p(x) = 21x^3 + 3x^2 + 14x^1 + 21x^0$.
Here, 21, 3, 14, and 21 are the coefficients, and 3,2,1 and 0 are the exponential values.

Representation of polynomial with single variable -

Consider a polynomial $−4+7x+6x^2$ then we can write as: $−4x^0+7x^1+6x^2$

For the one-dimensional array, store the coefficients in the index given by the coefficient of the polynomial.

In the array representation, the array first the first element stores the coefficient of the term with the lowest exponent and the last element contains the coefficient of the term with the highest exponent.

In general the polynomial

 $P(x)= a_0x^0+a_1x^1+\ldots+ a_{n-1}x^{n−1}+a_nx^n$
can be represented as


Polynomial Addition using Array

Consider two different polynomials 
$ P_1 = 3x^1+5x^2+7x^3$ and $P_2= 7x^0+3x^1+4x^2$. The degree of $p_1$ is 3 and the degree of $P_2$ is 2. The steps to add the polynomials are listed below.

1.First identify the highest degree polynomial. The degree of the resultant polynomial is same as the polynomial with the highest degree.
2.Store the coefficient in the index specified by the exponents of the polynomial.
3.Add the coefficients stored in one array with the corresponding index positions in the other array and store the result in the same index position in the resultant array.


C program to add two polynomials  
/*******************************************************************************/
#include <stdio.h>
// Function to add two polynomials and store the result in a third array
void addPolynomials(int poly1[], int degree1, int poly2[], int degree2, int result[]) {
    int maxDegree = (degree1 > degree2) ? degree1 : degree2;

    for (int i = 0; i <= maxDegree; i++) {
        int coef1 = (i <= degree1) ? poly1[i] : 0;
        int coef2 = (i <= degree2) ? poly2[i] : 0;

        result[i] = coef1 + coef2;
    }
}

// Function to print a polynomial
void printPolynomial(int poly[], int degree) {
    for (int i = degree; i >= 0; i--) {
        if (poly[i] != 0) {
            if (i < degree) {
                if (poly[i] > 0) {
                    printf(" + ");
                } else {
                    printf(" - ");
                }
            }
            printf("%d", (poly[i] < 0) ? -poly[i] : poly[i]);
            if (i > 0) {
                printf("x^%d", i);
            }
        }
    }
    printf("\n");
}

int main() {
    // Define the coefficients and degrees of two polynomials
    int poly1[] = {-7, 5, -2, 3}; // P(x) = -7 + 5x - 2x^2 + 3x^3
    int degree1 = 3;

    int poly2[] = {-1, 4, 2}; // Q(x) = -1 + 4x + 2x^2
    int degree2 = 2;

    // Determine the maximum degree among the two polynomials
    int maxDegree = (degree1 > degree2) ? degree1 : degree2;

    // Create an array to store the result polynomial
    int result[maxDegree + 1];

    // Add the two polynomials
    addPolynomials(poly1, degree1, poly2, degree2, result);

    // Print the polynomials and the result
    printf("Polynomial 1: ");
    printPolynomial(poly1, degree1);

    printf("Polynomial 2: ");
    printPolynomial(poly2, degree2);

    printf("Sum: ");
    printPolynomial(result, maxDegree);

    return 0;
}


Note that in this representation we assume that the polynomial is single variable and the exponents are positive.

here is the more general representation of a polynomial with array of structures.
We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents. So let us prepare a list of 2 things that is coefficients and exponent,

consider the polynomial
$p(x)=3x^5+2x^4+5x^2+2x+7$
Its represented like this

C program to add two polynomials  using structure representation
/*******************************************************************************/

#include <stdio.h>
#include <stdbool.h>

// Structure to represent a single term in the polynomial
typedef struct {
    int coefficient;
    int exponent;
} Term;

// Function to add two polynomials and store the result in a third array
void addPolynomials(Term poly1[], int degree1, Term poly2[], int degree2, Term result[], int *resultDegree) {
    int maxDegree = (degree1 > degree2) ? degree1 : degree2;
    *resultDegree = maxDegree;

    for (int i = 0; i <= maxDegree; i++) {
        int coef1 = 0, coef2 = 0;

        // Find the coefficients for poly1 and poly2 at exponent i
        for (int j = 0; j <= degree1; j++) {
            if (poly1[j].exponent == i) {
                coef1 = poly1[j].coefficient;
                break;
            }
        }

        for (int j = 0; j <= degree2; j++) {
            if (poly2[j].exponent == i) {
                coef2 = poly2[j].coefficient;
                break;
            }
        }

        result[i].coefficient = coef1 + coef2;
        result[i].exponent = i;
    }
}

// Function to print a polynomial
void printPolynomial(Term poly[], int degree) {
    bool firstTerm = true;

    for (int i = degree; i >= 0; i--) {
        int coef = poly[i].coefficient;
        int exponent = poly[i].exponent;

        if (coef != 0) {
            if (!firstTerm) {
                if (coef > 0) {
                    printf(" + ");
                } else {
                    printf(" - ");
                }
            }

            printf("%d", (coef < 0) ? -coef : coef);

            if (exponent != 0) {
                printf("x");

                if (exponent != 1) {
                    printf("^%d", exponent);
                }
            }

            firstTerm = false;
        }
    }

    if (firstTerm) {
        printf("0"); // Print "0" for the zero polynomial
    }

    printf("\n");
}

int main() {
    // Define the coefficients and exponents of two polynomials
    Term poly1[] = {{-7, 0}, {5, 1}, {-2, 2}, {3, 3}}; // P(x) = -7 + 5x - 2x^2 + 3x^3
    int degree1 = 3;

    Term poly2[] = {{-1, 0}, {4, 1}, {2, 2}}; // Q(x) = -1 + 4x + 2x^2
    int degree2 = 2;

    // Determine the maximum degree among the two polynomials
    int maxDegree = (degree1 > degree2) ? degree1 : degree2;

    // Create an array to store the result polynomial
    Term result[maxDegree + 1];

    int resultDegree;

    // Add the two polynomials
    addPolynomials(poly1, degree1, poly2, degree2, result, &resultDegree);

    // Print the polynomials and the result
    printf("Polynomial 1: ");
    printPolynomial(poly1, degree1);

    printf("Polynomial 2: ");
    printPolynomial(poly2, degree2);

    printf("Sum: ");
    printPolynomial(result, resultDegree);

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more