จำนวนช่องสี่เหลี่ยมขั้นต่ำที่มีผลรวมเท่ากับจำนวนที่กำหนด n

จำนวนใดๆ สามารถแทนด้วยผลรวมของจำนวนกำลังสองสมบูรณ์ ในปัญหานี้ เราต้องค้นหาว่าจำเป็นต้องมีจำนวนขั้นต่ำของพจน์กำลังสองสมบูรณ์จำนวนเท่าใดจึงจะแทนค่าที่กำหนดได้

ให้ค่าเป็น 94 ดังนั้น 95 =9 ² + 3 ² + 2 ² + 1 ² . ดังนั้นคำตอบจะเป็น 4

แนวคิดคือเริ่มจาก 1 เราก้าวต่อไปเพื่อให้ได้จำนวนเต็มกำลังสองสมบูรณ์ เมื่อค่าเป็น 1 ถึง 3 จะต้องสร้างด้วย 1 วินาทีเท่านั้น

อินพุตและเอาต์พุต

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