Функция Коллатца в схеме

Question

Так что я пытаюсь решить функцию Коллатца итеративно в схеме, но мои тесты продолжают отображаться как

(define (collatz n)   
    (define (collatz-iter n counter)
            (if (<=  n 1)
                1
            (if (even? n)  (collatz-iter (/ n 2) (+ counter 1))
                           (collatz-iter (+ (* n 3) 1) (+ counter 1)) 
            )
            )
    )
)

Тем не менее, мои тесты продолжают приводить к "#[constant 13 #x2]". Что я написал неправильно, если что?

Answer 1

Ты забыл позвонить collatz-iter, Кроме того, не ясно, что вы собираетесь делать с counter, вы просто увеличиваете его, но никогда не используете его значение - ваша процедура всегда вернет 1 (Предполагая, что гипотеза Коллатца верна, что кажется вполне возможным).

Я предполагаю, что вы намеревались вернуть счетчик, так что вот как исправить вашу процедуру:

(define (collatz n)
  (define (collatz-iter n counter)
    (if (<= n 1)
        counter ; return the counter
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1)))))
  (collatz-iter n 1)) ; call collatz-iter

И вот как это работает для примеров в Википедии:

(collatz 6)
=> 9

(collatz 11)
=> 15

(collatz 27)
=> 112

Таким образом, в основном мы рассчитываем длину последовательности Коллатца для данного числа.

Answer 2

Вы должны отступать свой код правильно. При правильном форматировании это

(define (collatz n)   
  (define (collatz-iter n counter)
    (if (<=  n 1)
        1
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1))))))

который явно не имеет форм тела для выполнения, только внутреннее определение. Вам нужно добавить звонок в collatz-iter, как это:

(define (collatz n)   
  (define (collatz-iter n counter)
    (if (<=  n 1)
        1
        (if (even? n)
            (collatz-iter (/ n 2) (+ counter 1))
            (collatz-iter (+ (* n 3) 1) (+ counter 1)))))
  (collatz-iter n 1))

(Я не уверен, что ваш начальный counter значение должно быть. Я предполагаю, что 1 разумно, но, возможно, оно должно быть нулевым?) А еще лучше, так как тело это просто призыв к collatz-iter, вы можете сделать это именованным let, что больше похоже на ваш оригинальный код:

(define (collatz n)
  (let iter ((n n) (counter 1))
    (if (<=  n 1)
        1
        (if (even? n)
            (iter (/ n 2) (+ counter 1))
            (iter (+ (* n 3) 1) (+ counter 1))))))

Это похоже на сочетание внутреннего определения с единственным вызовом локальной функции. Как только вы это сделаете, вы увидите, что он всегда возвращается 1, когда он в конечном итоге дойдет до базового случая (конечно, предполагая, что гипотеза Коллатца верна). Исправив это, вы получите:

(define (collatz n)
  (let iter ((n n) (counter 1))
    (if (<=  n 1)
        counter
        (if (even? n)
            (iter (/ n 2) (+ counter 1))
            (iter (+ (* n 3) 1) (+ counter 1))))))

Answer 3

Когда я пытаюсь запустить ваш код в Racket, я получаю сообщение об ошибке:

нет выражения после последовательности внутренних определений

Это говорит нам о том, что collatz функция содержит collatz-iter определение, но нет выражения для его вызова (кроме рекурсивных вызовов в collatz-iter). Это можно исправить, добавив вызов (collatz-iter n 0) как последняя строка в collatz,

Однако при запуске программы она всегда возвращает 1. Не очень интересно. Если вместо этого вы измените его, чтобы вернуть значение counter Вы можете увидеть, сколько шагов потребовалось, чтобы последовательность достигла 1.

(define (collatz n)   
    (define (collatz-iter n counter)
            (if (<=  n 1)
                counter
            (if (even? n)  (collatz-iter (/ n 2) (+ counter 1))
                           (collatz-iter (+ (* n 3) 1) (+ counter 1)) 
            )
            )
    )
  (collatz-iter n 0)
)

Мы можем сравнить это с несколькими примерами, приведенными в статье о гипотезе Википедии Коллатц.

> (collatz 6)
8
> (collatz 11)
14
> (collatz 27)
111
>