Напишите процедуру, которая проверяет, является ли данное число суммой различных квадратов в схеме - PullRequest
Новая
       49

Напишите процедуру, которая проверяет, является ли данное число суммой различных квадратов в схеме

0 голосов
/ 06 февраля 2019

В нашем последнем экзамене мы должны были написать процедуру, которая выяснит, можно ли записать данное число в виде суммы квадратов не равных чисел.наименьший квадрат должен быть 2 ^ 2, а не 1 ^ 2

например - данное число равно 13 -> истина, потому что 13 следует переписать как 2 ^ 2 + 3 ^ 2, если заданное число равно 8 -> ложь, потому что 8равно 2 ^ 2 + 2 ^ 2, что является суммой равных квадратов.

Я застрял на поиске правильного алгоритма.Например, мне дадут номер 65. У меня есть идея написать вспомогательную процедуру «квадраты», которая всегда находит 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

edit 1:

Я написал этот код.Это не дает правильных результатов (сумма-кв 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)))))

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

1 Ответ

0 голосов
/ 06 февраля 2019 
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
...