Я пытаюсь отредактировать текущую программу, которая у меня есть
(define (sumofnumber n)
(if (= n 0)
1
(+ n (sumofnumber (modulo n 2 )))))
так что он возвращает сумму n числа положительных квадратов. Например, если вы введете 3, программа сделает 1+4+9, чтобы получить 14. Я пытался использовать модуль и другие методы, но это всегда входит в бесконечный цикл.
Базовый случай неверен (квадрат нуля равен нулю), как и рекурсивный шаг (почему вы берете модуль?) и фактическая операция (где вы возводите значение в квадрат?). Вот как должна выглядеть процедура:
(define (sum-of-squares n)
(if (= n 0)
0
(+ (* n n)
(sum-of-squares (- n 1)))))
Определение, использующее композицию, а не рекурсию. Прочитайте комментарии снизу вверх для процедурной логики:
(define (sum-of-squares n)
(foldl + ; sum the list
0
(map (lambda(x)(* x x)) ; square each number in list
(map (lambda(x)(+ x 1)) ; correct for range yielding 0...(n - 1)
(range n))))) ; get a list of numbers bounded by n
Я предоставляю это, потому что вы уже на пути к пониманию идиомы рекурсии. Композиция — это еще одна идиоматика Racket, которую стоит изучить и часто упоминается после рекурсии в образовательных контекстах.
Иногда я нахожу, что композицию легче применить к проблеме, чем рекурсию. В другой раз нет.
Вы ничего не возводите в квадрат, поэтому нет причин ожидать, что это будет сумма квадратов.
Запишите, как вы получили 1 + 4 + 9 с n = 3 (^ — это возведение в степень):
1^2 + 2^2 + 3^2
Это
(sum-of-squares 2) + 3^2
or
(sum-of-squares (- 3 1)) + 3^2
то есть,
(sum-of-squares (- n 1)) + n^2
Обратите внимание, что по модулю нигде не встречается, и вы не добавляете n ни к чему.
(И квадрат 0 равен 0 , а не 1.)
Вы можете разбить проблему на маленькие кусочки.
1. Создайте список чисел от 1 до n
2. Сопоставьте квадратную функцию со списком, чтобы возвести в квадрат каждое число
3. Примените +, чтобы добавить все числа в квадратный список
(define (sum-of-number n)
(apply + (map (lambda (x) (* x x)) (sequence->list (in-range 1 (+ n 1))))))
> (sum-of-number 3)
14
Это прекрасная возможность использовать технику преобразователей.
Вычисление суммы списка — это свертка. Карта и фильтр тоже складываются. Объединение нескольких сверток во вложенном виде, как в (sum...(filter...(map...sqr...))), приводит к многократному (здесь трем) обходам списка.
Но когда вложенные складки объединяются, их редуцирующие функции объединяются вложенным образом, что дает нам один обход fold вместо этого с помощью одной комбинированной функции редуктора:
(define (((mapping f) kons) x acc) (kons (f x) acc)) ; the "mapping" transducer
(define (((filtering p) kons) x acc) (if (p x) (kons x acc) acc)) ; the "filtering" one
(define (sum-of-positive-squares n)
(foldl ((compose (mapping sqr) ; ((mapping sqr)
(filtering (lambda (x) (> x 0)))) ; ((filtering {> _ 0})
+) 0 (range (+ 1 n)))) ; +))
; > (sum-of-positive-squares 3)
; 14
Конечно, ((compose f g) x) такое же, как (f (g x)). Комбинированная / «составная» (каламбур) функция редуктора создается просто заменой аргументов в определения, как
((mapping sqr) ((filtering {> _ 0}) +))
=
( (lambda (kons)
(lambda (x acc) (kons (sqr x) acc)))
((filtering {> _ 0}) +))
=
(lambda (x acc)
( ((filtering {> _ 0}) +)
(sqr x) acc))
=
(lambda (x acc)
( ( (lambda (kons)
(lambda (x acc) (if ({> _ 0} x) (kons x acc) acc)))
+)
(sqr x) acc))
=
(lambda (x acc)
( (lambda (x acc) (if (> x 0) (+ x acc) acc))
(sqr x) acc))
=
(lambda (x acc)
(let ([x (sqr x)] [acc acc])
(if (> x 0) (+ x acc) acc)))
который выглядит почти как что-то, что написал бы программист. В качестве упражнения,
((filtering {> _ 0}) ((mapping sqr) +))
=
( (lambda (kons)
(lambda (x acc) (if ({> _ 0} x) (kons x acc) acc)))
((mapping sqr) +))
=
(lambda (x acc)
(if (> x 0) (((mapping sqr) +) x acc) acc))
=
(lambda (x acc)
(if (> x 0) (+ (sqr x) acc) acc))
Таким образом, вместо того, чтобы самим писать определения объединенных функций редуктора, что, как и любая человеческая деятельность, подвержена ошибкам, мы можем составлять эти функции редуктора из более атомарных «преобразований», например, преобразователей.
Работает в DrRacket.
