যেকোনো সংখ্যাকে কিছু পূর্ণ বর্গ সংখ্যার যোগফল হিসেবে প্রকাশ করা যায়। এই সমস্যায় আমাদের বের করতে হবে প্রদত্ত মানকে প্রকাশ করতে ন্যূনতম কতগুলো পূর্ণ বর্গ পদ প্রয়োজন।
ধরি মান ৯৪, তাহলে 95 = 9² + 3² + 2² + 1²। তাই উত্তর ৪।
ধারণা হল ১ থেকে শুরু করে পূর্ণ বর্গ সংখ্যা পাওয়ার জন্য এগিয়ে যাওয়া। যখন মান ১ থেকে ৩ হয়, সেগুলো শুধু ১ দিে গঠন করতে হয়।
ইনপুট এবং আউটপুট
ইনপুট: একটি পূর্ণসংখ্যা। ধরা যাক ৬৩। আউটপুট: বর্গ পদের সংখ্যা। এখানে উত্তর ৪। 63 = 7² + 3² + 2² + 1
অ্যালগরিদম
minSquareTerms(value)
ইনপুট: প্রদত্ত মান।
আউটপুট: প্রদত্ত মানের সমান হওয়ার জন্য ন্যূনতম বর্গ পদের সংখ্যা।
শুরু
value+1 আকারের sqList অ্যারে সংজ্ঞায়িত করুন
sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3
i := 4 থেকে n পর্যন্ত রেঞ্জে, করুন
sqList[i] := i
x := 1 থেকে i পর্যন্ত, করুন
temp := x²
যদি temp > i হয়, তবে
লুপ ব্রেক করুন
অন্যথায় sqList[i] := sqList[i] এবং (1 + sqList[i-temp]) এর মধ্যে ন্যূনতম
끝난
끝난
sqList[n] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
int min(int x, int y) { return (x < y) ? x : y; }
int minSquareTerms(int n) {
int *squareList = new int[n+1];
squareList[0] = 0;
squareList[1] = 1;
squareList[2] = 2;
squareList[3] = 3;
for (int i = 4; i <= n; i++) {
squareList[i] = i;
for (int x = 1; x <= i; x++) {
int temp = x*x;
if (temp > i) break;
else squareList[i] = min(squareList[i], 1 + squareList[i-temp]);
}
}
return squareList[n];
}
int main() {
int n;
cout << "Enter a number: "; cin >> n;
cout << "Minimum Squared Term needed: " << minSquareTerms(n);
return 0;
}
আউটপুট
Enter a number: 63 Minimum Squared Term needed: 4
