Как реализовать рекурсивную функцию в Racket?

Я пытаюсь создать функцию под названием lcm-from-factors, которая вычисляет наименьшее общее кратное двух чисел (m и n). Входными данными для функции являются m-co-groups и n-co-groups, в которых перечислены все простые Факторы и их силы. Например, для m = 2970 и n = 163 800 мы будем иметь:

m-когрупп = '((2 1) (3 3) (5 1) (7 0) (11 1) (13 0)) n-когрупп = '((2 3) (3 2) ( 5 2) (7 1) (11 0) (13 1))

Они возвращаются функцией, называемой кофактором, которая была дана мне. Я написал код, но функция не компилируется, потому что я считаю, что неправильно реализовал рекурсию. Я был бы признателен за любую помощь в выяснении того, что я делаю неправильно. Мой код выглядит следующим образом.

    (define (lcm-from-factors m n)
        (let-values (((m-co-groups n-co-groups) (co-factor m n)))
            (define (recurse m-co-groups n-co-groups)
                (let* ((a (first(m-co-groups)))
                      (b (first(n-co-groups))))
                   (cond ((>= (rest(a)) (rest(b)))
                         (+ (expt (first(a)) (rest(a))) (recurse (rest(m-co-groups)) (rest(n-co-groups)))))
                         (else (+ (expt (first(b)) (rest(b))) (recurse (rest(m-co-groups)) (rest(n-co-groups))))))))))

tail-recursion racket
person user2904796    schedule 10.02.2015    source источник
comment
Из того, что я вижу, (co-factor m n) нужно оценивать два списка процедур, поскольку вы применяете элементы ((a) и (b)), и эти процедуры должны создавать пары, поскольку вы пытаетесь first получить результаты?   -  person Sylwester    schedule 10.02.2015
comment
Да, функция, которую мне дали, действительно возвращает два списка, как показано для m = 2970 и n = 163 800.   -  person user2904796    schedule 10.02.2015
comment
Однако я не могу завершить (сначала (m-co-groups)) по какой-то причине?   -  person user2904796    schedule 10.02.2015
comment
(m-co-groups) означает вызов m-co-groups как процедуры. Если это не процедура, вы получите сообщение об ошибке. Ни одна из переменных никогда не должна вызываться как процедура.   -  person Sylwester    schedule 10.02.2015
comment
No m-co-groups — это возвращаемый список. Кофактор - это процедура, которую я считаю.   -  person user2904796    schedule 10.02.2015
comment
m-когрупп = ’((2 1) (3 3) (5 1) (7 0) (11 1) (13 0)). Он возвращает список, где каждый элемент является парой.   -  person user2904796    schedule 10.02.2015
comment
Опять же.. Когда вы заключаете переменную в круглые скобки на схеме, вы рассматриваете ее как процедуру без аргументов.. Например. если a было (lambda () 10), то (a) становится 10. Если a равно (2 1), вы получаете сообщение об ошибке, говорящее, что (2 1) не является процедурой, так как вы фактически вызываете ('(2 1)) Я предполагаю, что вы теряете много ошибок, удаляя лишние скобки. например, (first m-co-groups) вместо (first (m-co-groups)), что может потребовать, чтобы m-co-groups была процедурой, подобной +.   -  person Sylwester    schedule 10.02.2015
comment
Спасибо, я удалил все лишние скобки. Хотя ошибка все равно есть. Сообщение об ошибке выглядит следующим образом:   -  person user2904796    schedule 10.02.2015
comment
начало (возможно, неявное): нет выражения после последовательности внутренних определений   -  person user2904796    schedule 10.02.2015
comment
Это потому, что вы определяете процедуру recurse, но не используете ее, вызывая (recurse m-co-groups n-co-groups) в качестве последнего выражения в let-values. Вы можете сделать и то, и другое в одной форме с именованным let (let recurse ((m-co-groups m-co-groups) (n-co-groups n-co-groups) ... )   -  person Sylwester    schedule 10.02.2015

Ответы (1)


arrow_upward
0
arrow_downward

Следующее является ступенькой, чтобы вы начали. Код обрабатывает конкретную ситуацию, когда m и n имеют одинаковые простые делители. Это ваша работа, чтобы выяснить, как обращаться с другими случаями.

#lang racket
(require math/number-theory)

(define (co-factor m n) (values (factorize m) (factorize n)))
(define (exponent power) (second power))
(define (base power)     (first power))

(define (lcm-from-factors m n)
  (let-values ([(m-co-groups n-co-groups) (co-factor m n)])
    (define (recurse m-co-groups n-co-groups)
      (cond
        [(and (empty? m-co-groups) (empty? n-co-groups))  1]
        [(empty? m-co-groups)                             'something-1]
        [(empty? n-co-groups)                             'something-2]
        [else
         (define a-power (first m-co-groups))
         (define b-power (first n-co-groups))
         (define a-base  (base a-power))
         (define b-base  (base b-power))
         (define a-exp   (exponent a-power))
         (define b-exp   (exponent b-power))
         (cond 
           [(= a-base b-base)   (* (expt a-base (max a-exp b-exp))
                                   (recurse (rest m-co-groups) (rest n-co-groups)))]
           [(< a-base b-base)   'something-3]
           [(> a-base b-base)   'something-4])]))
    (recurse m-co-groups n-co-groups)))

(define x (* (expt 2 3) (expt 3 4)))
(define y (* (expt 2 1) (expt 3 5)))

(lcm-from-factors x y) ; gives 1944
(lcm x y)              ; gives 1944
person soegaard    schedule 10.02.2015