Схема: рекурсия и списки - PullRequest
Новая
       5

Схема: рекурсия и списки

1 голос
/ 09 июля 2010

Я пытался научиться программированию самостоятельно, работая над учебником Как разрабатывать программы для Scheme.Я прошел через все до сих пор.Вот проблема:

9.5.5 Разработка функции convert.Он потребляет список цифр и выдает соответствующий номер.Первая цифра является наименее значимой и т. Д.

Выполнив первые несколько шагов, от анализа данных до шаблона, я получаю вот это, голые кости программы: 

;; A list-of-numbers is either 1. an empty list, empty, or 2. (cons n 
lon) where n is a number and lon is a list of numbers 
;; convert : lon -> number 
;; to consume a lon and produce the corresponding number. The least 
significant digit corresponds to the first number in the list, and so 
on. 
;; (= (convert (cons 1 (cons 9 (cons 10 (cons 99 empty))))) 991091) 
(define (convert lon) 
  (cond 
    [(empty? lon)...] 
    [(cons? lon)...(first lon)...(convert (rest lon))...]))

Как мне пройти этот этап, чтобы, как говорится в книге, "объединить ценности"?Один способ, который я думаю, мог бы работать, если бы я умножил первое значение на 10 до степени значимости значения в общем числе, например,

(минусы 1 (минусы 9 пусто)) => 1 * 10^ (ЗНАЧЕНИЕ), где НАИМЕНОВАНИЕ ЗНАЧЕНИЯ будет равно 0. Используя мое ограниченное понимание программирования, я полагаю, что требуется некоторый счетчик, где n увеличивается на единицу каждый раз, когда функция, так или иначе, вызывается рекурсивно.Но это выглядит как попытка запустить две рекурсии одновременно.Поскольку выражения вычисляются последовательно (очевидно), вы не можете вызвать функцию счетчика, так как вызываете функцию преобразования.

Итак, кто-нибудь может помочь мне решить эту проблему?Я бы предпочел, чтобы вы решили это, используя естественную рекурсию и CONStructor для списков, а не лямбду или другие идеи, которые книга еще не рассмотрела.

Спасибо!

Ответы [ 2 ]

0 голосов
/ 09 июля 2010

Вот хвостовая рекурсивная версия: 

(define (convert lon)
  (let rec ((i 0)
            (n 0)
            (lon lon))
    (cond ((empty? lon) n)
          (else (rec (+ i 1)
                     (+ n (* (first lon) (expt 10 i)))
                     (rest lon))))))
0 голосов
/ 09 июля 2010

Вам не нужно делать возведение в степень - простое умножение будет хорошо. 

(define (convert digits) 
  (cond
    ((empty? digits) 0)
    (else (+ (* 10 (convert (rest digits))) (first digits)))
  )
)

(convert '(1 2 3 4 5 6))

Или другой способ думать об этом: 

(define (convert digits)
  (convert-helper digits 1 0)
)

(define (convert-helper digits multiplier sofar)
  (cond
    ((empty? digits) sofar)
    (else 
        (convert-helper 
            (rest digits) 
            (* 10 multiplier) 
            (+ (* multiplier (first digits)) sofar)
        )
    )
  )
)


(convert '(1 2 3 4 5 6))
...