ন্যূনতম সংখ্যক বর্গক্ষেত্র যার যোগফল প্রদত্ত সংখ্যা n এর সমান

যেকোন সংখ্যাকে কিছু নিখুঁত বর্গ সংখ্যার যোগফল দ্বারা উপস্থাপন করা যেতে পারে। এই সমস্যায়, আমাদের খুঁজে বের করতে হবে যে প্রদত্ত মানকে উপস্থাপন করার জন্য নিখুঁত বর্গ পদের সর্বনিম্ন কত সংখ্যা প্রয়োজন।

মানটি হল 94, তাই 95 =9 ² + 3 ² + 2 ² + 1 ² . তাই উত্তর হবে 4

ধারণাটি হল 1 থেকে শুরু করা, আমরা নিখুঁত বর্গ সংখ্যা পেতে আরও এগিয়ে যাই। যখন মান 1 থেকে 3 হয়, তখন তাদের অবশ্যই 1s দিয়ে গঠিত হতে হবে।

ইনপুট এবং আউটপুট

Input:
An integer number. Say 63.
Output:
Number of squared terms. Here the answer is 4.
63 =72 + 32 + 22 + 1

অ্যালগরিদম

minSquareTerms(value)

ইনপুট: প্রদত্ত মান।

আউটপুট: প্রদত্ত মান পৌঁছানোর জন্য বর্গ পদের ন্যূনতম সংখ্যা৷

Begin
   define array sqList of size value + 1
   sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3

   for i in range 4 to n, do
      sqList[i] := i
      for x := 1 to i, do
         temp := x^2
         if temp > i, then
            break the loop
         else sqList[i] := minimum of sqList[i] and (1+sqList[i-temp])
      done
   done
   return sqList[n]
End

উদাহরণ

#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];

   //for 0 to 3, there are all 1^2 needed to represent

   squareList[0] = 0;
   squareList[1] = 1;
   squareList[2] = 2;
   squareList[3] = 3;

   for (int i = 4; i <= n; i++) {
      squareList[i] = i; //initially store the maximum value as i

      for (int x = 1; x <= i; x++) {
         int temp = x*x;      //find a square term, lower than the number i
         if (temp > i)
            break;
         else squareList[i] = min(squareList[i], 1+squareList[itemp]);
      }
   }
   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