Số ô vuông tối thiểu có tổng bằng số n đã cho

Mọi số đều có thể được biểu diễn bằng tổng của một số bình phương hoàn hảo. Trong bài toán này, chúng ta cần thấy rằng cần có bao nhiêu số hạng tối thiểu của các số hạng bình phương hoàn hảo để biểu thị giá trị đã cho.

để giá trị là 94, vì vậy 95 =9 ² + 3 ² + 2 ² + 1 ² . vì vậy câu trả lời sẽ là 4

Ý tưởng là bắt đầu từ số 1, chúng tôi tiến xa hơn để có được các số bình phương hoàn hảo. Khi giá trị từ 1 đến 3, chúng phải được tạo chỉ với 1s.

Đầu vào và Đầu ra

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

Thuật toán

minSquareTerms(value)

Đầu vào: Giá trị đã cho.

Đầu ra: Số thuật ngữ bình phương tối thiểu để đạt được giá trị nhất định.

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

Ví dụ

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

Đầu ra

Enter a number: 63
Minimum Squared Term needed: 4