Я искал в Интернете реализацию «Решета Эратосфена» в схеме, и хотя я нашел много контента, ни один из них, похоже, не сделал его так, как мне нужно.
Проблема в том, что большинство алгоритмов либо используют статический конец, либо используют итерацию. Это в сочетании с моим незнанием языка побудило меня попросить всех вас о помощи.
Мне нужна реализация Sieve, которая принимает один аргумент (число от Sieve до), использует только рекурсию и имеет список «минусов» числа с #t
(истина) или #f
(ложь).
По сути, алгоритм будет таким:
- Составьте список из 2-х введенных чисел, каждое из которых начинается с истины
- Рекурсивно пройдите и отметьте каждое число, которое делится на 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))
Если бы у вас также были комментарии, подробно объясняющие код, это было бы очень полезно.
Спасибо!
ПЕРЕСМОТРЕНО ::: Итак, я выучил небольшую схему, чтобы подробнее объяснить свой вопрос ...
Это входит в список.
(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))))))
Что я пытаюсь сделать, так это, как следует из названия функции, вызвать кратные уценки для каждого номера, который все еще помечен как истинный в списке. Таким образом, вы передаете ((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)
, и продолжает движение вниз по списку ...
На выходе я получаю список со всеми истинами.
Надеюсь, это поможет вам лучше понять мое затруднительное положение.