এই ধারণাটি ভালোভাবে বুঝতে হলে আসুন প্রথমে প্রয়োজনীয় সব বেসিক বিষয়গুলো সংক্ষেপে জানি।
লিংকড লিস্ট একটি ডেটা স্ট্রাকচার যা প্রতিটি এলিমেন্টকে লিস্টের একটি নোডে অবজেক্ট হিসেবে সংরক্ষণ করে। প্রতিটি নোডে দুটি অংশ থাকে: ডেটা এবং পরবর্তী নোডের লিংক।
পলিনোমিয়াল হল একটি গাণিতিক এক্সপ্রেশন যাতে ভেরিয়েবল এবং কোইফিশিয়েন্ট থাকে। উদাহরণস্বরূপ x² - 4x + 7।
পলিনোমিয়াল লিংকড লিস্ট-এ, পলিনোমিয়ালের কোইফিশিয়েন্ট এবং এক্সপোনেন্ট লিস্টের ডেটা নোড হিসেবে সংজ্ঞায়িত হয়।
লিংকড লিস্ট হিসেবে সংরক্ষিত দুটি পলিনোমিয়াল যোগ করতে হলে, একই পাওয়ারের ভেরিয়েবলগুলোর কোইফিশিয়েন্ট যোগ করতে হয়। একটি লিংকড লিস্ট নোডে তিনটি মেম্বার থাকে: কোইফিশিয়েন্ট মান, এক্সপোনেন্ট, এবং পরবর্তী নোডের লিংক।
পলিনোমিয়াল সংরক্ষণ করতে ব্যবহৃত একটি লিংকড লিস্ট নিচের মতো দেখায়:
পলিনোমিয়াল: 4x⁷ + 12x² + 45
এই ছবিটি কীভাবে একটি লিংকড লিস্ট পলিনোমিয়ালকে প্রতিনিধিত্ব করে তা দেখাচ্ছে।
লিংকড লিস্ট হিসেবে প্রতিনিধিত্ব করা দুটি পলিনোমিয়াল যোগ করতে হলে, আমরা নোডের এক্সপোনেন্ট মান চেক করি। একই এক্সপোনেন্ট মান 가진 নোডের কোইফিশিয়েন্টগুলো যোগ করা হয়।
উদাহরণ,
ইনপুট: p1 = 13x⁸ + 7x⁵ + 32x² + 54, p2 = 3x¹² + 17x⁵ + 3x³ + 98 আউটপুট: 3x¹² + 13x⁸ + 24x⁵ + 3x³ + 32x² + 152
ব্যাখ্যা − সব পাওয়ারের জন্য, আমরা একই এক্সপোনেন্ট মান সম্পন্ন কোইফিশিয়েন্টগুলো চেক করি এবং সেগুলো যোগ করি। তারপর ফাইনাল পলিনোমিয়ালটি রিটার্ন করি।
অ্যালগরিদম
ইনপুট − লিংকড লিস্ট হিসেবে প্রতিনিধিত্ব করা পলিনোমিয়াল p1 এবং p2।
স্টেপ 1: লিংকড লিস্টের সব মান দিয়ে লুপ চালান এবং স্টেপ ২ ও ৩ অনুসরণ করুন। স্টেপ 2: যদি একটি নোডের এক্সপোনেন্ট মান বড় হয়, তবে এই নোডটিকে রেজাল্ট নোডে কপি করুন এবং পরবর্তী নোডে যান। স্টেপ 3: যদি দুটি নোডের এক্সপোনেন্ট মান একই হয়, তবে কোইফিশিয়েন্টগুলো যোগ করুন এবং যোগফলকে নোডসহ রেজাল্টে কপি করুন। স্টেপ 4: রেজাল্টান্ট নোড প্রিন্ট করুন।
উদাহরণ
#include<bits/stdc++.h> using namespace std; struct Node{ int coeff; int pow; struct Node *next; }; void create_node(int x, int y, struct Node **temp){ struct Node *r, *z; z = *temp; if(z == NULL){ r =(struct Node*)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } void polyadd(struct Node *p1, struct Node *p2, struct Node *result){ while(p1->next && p2->next){ if(p1->pow > p2->pow){ result->pow = p1->pow; result->coeff = p1->coeff; p1 = p1->next; } else if(p1->pow < p2->pow){ result->pow = p2->pow; result->coeff = p2->coeff; p2 = p2->next; } else { result->pow = p1->pow; result->coeff = p1->coeff+p2->coeff; p1 = p1->next; p2 = p2->next; } result->next = (struct Node *)malloc(sizeof(struct Node)); result = result->next; result->next = NULL; } while(p1->next || p2->next){ if(p1->next){ result->pow = p1->pow; result->coeff = p1->coeff; p1 = p1->next; } if(p2->next){ result->pow = p2->pow; result->coeff = p2->coeff; p2 = p2->next; } result->next = (struct Node *)malloc(sizeof(struct Node)); result = result->next; result->next = NULL; } } void printpoly(struct Node *node){ while(node->next != NULL){ printf("%dx^%d", node->coeff, node->pow); node = node->next; if(node->next != NULL) printf(" + "); } } int main(){ struct Node *p1 = NULL, *p2 = NULL, *result = NULL; create_node(41,7,&p1); create_node(12,5,&p1); create_node(65,0,&p1); create_node(21,5,&p2); create_node(15,2,&p2); printf("polynomial 1: "); printpoly(p1); printf("\npolynomial 2: "); printpoly(p2); result = (struct Node *)malloc(sizeof(struct Node)); polyadd(p1, p2, result); printf("\npolynomial after adding p1 and p2 : "); printpoly(result); return 0; }
আউটপুট
polynomial 1: 41x^7 + 12x^5 + 65x^0 polynomial 2: 21x^5 + 15x^2 polynomial after adding p1 and p2 : 41x^7 + 33x^5 + 15x^2 + 65x^0
