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

Question

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

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

我一直在寻找正确的算法。例如，我将得到数字 65。我有一个想法来编写帮助程序“squares”，它总是找到给定数字的 sqr（从 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）-> true

(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)))))

标签： algorithmsumschemeracket

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