algorithm - 编写一个程序来测试给定数字是否是 Scheme 中不同平方的和

Question

在上次考试中，我们必须编写程序来确定给定数字是否可以写成不相等数字的平方数之和。 最小的正方形必须是 2^2，而不是 1^2

例如- 给定的数字是 13 -> true 因为 13 被重写为 2^2 + 3^2 如果给定数字是 8 -> false，因为 8 是 2^2 + 2^2，它是等平方和。

我一直在寻找正确的算法。例如，我将得到 65 号。我有一个想法来编写帮助程序“正方形”，它总是找到给定数字(从 2^2 开始)到给定数字或大于 65 的平方。因此，例如 65，它会找到2^2 3^2 4^2 5^2 6^2 7^2 8^2 现在我不知道如何测试所有正方形组合的总和是否会给出答案 65。答案应该是#true因为 4^2 和 7^2 的结果是 65

编辑 1:

这段代码是我写的。它没有给出正确的结果 (sum-sq 17) -> 真

(define (sum-sq n)
  (sum-sq-help n 2))

(define (sum-sq-help n i)
  (if (or (= (sqr i) (/ n 2)) (= n 0))          
      #f
      (if (integer? (sqrt (- n (sqr i)))) #t (sum-sq-help n (+ 1 i)))))

编辑 2:更新 - 这工作正常

(define (sum-sq n)
  (sum-sq-help-2 n 2))

(define (sum-sq-help-2 n i)
    (cond ((= (sqr i) (/ n 2)) #f)
          ((< n (sqr i)) #f)
          ((= 1 (- n (sqr i))) #f)
          ((integer? (sqrt (- n (sqr i)))) #t)
          (else (sum-sq-help-2 n (+ 1 i)))))

Answer 1

Input: n
Output: Is n a sum of squares?

Algorithm:
1.  xs := {i^2 | 1<i^2<n}
2.  x  := n
3.  loop
      if  x<=1     then return false as the final result
      if  x in xs  then return true  as the final result
      x := x - (largest number in xs smaller than x)
    endloop