给定一个整数，将其表示为 s 个平方和

Question

如果我有数字 75，我的输出应该如下所示： 64+9+1+1

我试过这个：

#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int number, sum = 0;
  cin >> number;

  for (int i = number; i > 0; i--) {
    if (sqrt(i) == round(sqrt(i))) {
      if (number-i > 1) {
        cout << i << "+";
        number -= i;
        sum += i;
      }
    }
  }

  for (int i = number; i > 0; i--) {
    if (i == 1) {
      cout << "+1";
    } else {
      cout << "1";
    }
  }
}

输入 75 代码工作正常，但如果我输入 24，那么我应该收到：

This: 16+4+4
However I get: 16+4+1+11+1

如果我输入 1245

我收到这个：1225+16+1+11+1

然而正确答案是：1225+16+4

感谢任何帮助。提前致谢:)

Answer 1

我觉得你应该先重写算法。

1) 从 sqrt(number) 开始迭代，而不是从数字开始，向下迭代到 1，将 i 视为根（即平方）。应该会快很多。

2) 要检查是否需要 + 字符，最好有一个 bool 标志，表示已将某些内容写入输出并写入 + 之前基于该标志的平方数。

我认为你算法的问题是每个方格最多检查一次，而它可能出现不止一次。

Answer 2

我的 5 美分在这里。这个想法是找到最接近的平方根，其 2 的幂小于或等于给定的数字。写下这个平方数，然后从数字中减去它。如果数字仍然大于 0（我假设 number 是一个正整数），请重复该过程：

void main() {
    uint32_t number;
    cin >> number;

    while (number > 0) {
        uint32_t floorRoot = floor(sqrt(number));
        uint32_t squareNumber = floorRoot * floorRoot;

        cout << squareNumber;
        number -= squareNumber;

        if (number > 0) {
            cout << "+";
        }
    }
}

用法示例

Input: 67

Output: 64+1+1+1

更新：

如果number是任意整数那么代码可以改进如下：

void main() {
    int number;
    cin >> number;

    // abs(INT_MIN) is still negative!!!
    if (number == INT_MIN) {
        printf("Please provide a number larger than %i", INT_MIN);
        return;
    }

    if (!number) {
        cout << "0";
        return;
    }

    while (number != 0) {
        int floorRoot = floor(sqrt(abs(number)));
        int squareNumber = floorRoot * floorRoot;

        if (number > 0) {
            cout << squareNumber;
            number -= squareNumber;
        } else {
            cout << -squareNumber;
            number += squareNumber;
        }

        if (number > 0) {
            cout << "+";
        }
    }
}

用法示例

Input: -67

Output: -64-1-1-1

Input: 67

Output: 64+1+1+1

Input: 0

Output: 0

给定一个整数，将其表示为 s 个平方和

Given an integer, represent it as s sum of squares

c++

algorithm

root

square