Я искал в сети реализацию «Решета Эратосфена» в схеме, и, хотя я придумал много контента, ни один из них, похоже, не сделал этого так, как мне нужно.
Проблема состоит в том, что большинство алгоритмов либо используют статический конец, либо используют итерацию. Это в сочетании с моим незнанием языка заставило меня попросить всех вас о помощи.
Мне нужна реализация Sieve, которая принимает один аргумент (число для Sieve до), использует только рекурсию и имеет список «минусов» числа с #t
(true) или #f
(false ).
Таким образом, по сути, алгоритм будет выглядеть так:
- Составить список из 2-х чисел, каждый из которых начинается с true
- Рекурсивно пройти и пометить каждое число, которое делится на 2 ложных
- Затем переходите к следующему «истинному» числу в списке, пока не останутся только простые числа, помеченные как истинные
- Вывести список
Пример вывода:
> (Эрат-сито 20)
((2. #T)
(3. #T)
(4. #F)
(5. #T)
(6. #F)
(7. #T)
(8. #F)
(9. #F)
(10. #F)
(11. #T)
(12. #F)
(13. #T)
(14. #F)
(15. #F)
(16. #F)
(17. #T)
(18. #F)
(19. #T)
(20. #F))
Если бы у вас также были комментарии, подробно объясняющие код, это было бы очень признательно.
Спасибо!
REVISED :::
Итак, я выучил немного схемы для дальнейшего объяснения моего вопроса ...
Это составляет список.
(define (makeList n)
(if (> n 2)
(append (makeList (- n 1)) (list (cons n (and))))
(list (cons 2 (and)))))
Возвращает список с каждым кратным делителя, помеченного как false.
(define (mark-off-multiples numbers divisor)
(if (null? numbers)
'()
(append
(list (cons (car (car numbers))
(not (zero? (modulo (car (car numbers)) divisor)))))
(mark-off-multiples (cdr numbers) divisor))))
Теперь с этой функцией у меня проблемы, похоже, она должна работать, я трижды проходил ее вручную, но не могу понять, почему она не возвращает то, что мне нужно.
(define (call-mark-off-multiples-for-each-true-number numbers)
(if (null? numbers)
'()
(if (cdr (car numbers))
(append (list (car numbers))
(call-mark-off-multiples-for-each-true-number
(mark-off-multiples (cdr numbers) (car (car numbers)))))
(append (list (car numbers))
(call-mark-off-multiples-for-each-true-number
(cdr numbers))))))
То, что я пытаюсь сделать, это, как следует из названия функции, вызывать кратные метки вызова для каждого номера, который все еще помечен как true в списке. Таким образом, вы передаете ((3.#t)(4.#t)(5.#t))
, а затем он вызывает mark-off-multiples
для 2 и возвращает (3.#t)(4.#f)(5.#t)
, и вы добавляете (2.#t)
к нему. Затем он снова вызывает себя, передавая (3.#t)(4.#f)(5.#t)
, и вызывает кратные разметки с cdr списка, возвращающего (4.#f)(5.#t)
, и продолжает идти по списку ...
Вывод, который я затем получаю, представляет собой список со всеми истинными значениями.
Это, надеюсь, поможет вам лучше понять мое затруднительное положение.