Как написать программу Scheme (языки R5RS) для подсчета максимальной глубины (без использования функции max)?

Вот что у меня есть для программы глубины, но как это сделать без функции max (использовать только define, lambda, quote (‘), car, cdr, cons, cond, eq? И equal?)?

(define depth
     (lambda (expr)
        (cond ((null? expr) 0) 
              ((list? (car expr)) 
               (max (+ 1 (depth (car expr))) (depth (cdr expr)))) 
              ((null? (cdr expr))0) (max (depth (cdr expr))))))

ввод: ((id = id + id) (if bool then (if bool then (id = id + id)) (id = const / const) (id = id + id)) (while bool (id = id - const ) (id = id - id)))

Должен выводиться: максимальная глубина: 2


scheme racket r5rs
person Layla    schedule 03.12.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Что ж, вы всегда можете реализовать свой собственный my-max и использовать его вместо встроенной max процедуры:

(define (my-max a b)
  (if (> a b) a b))

Чтобы найти максимальную глубину, вам придется, так или иначе, провести в основном такое же сравнение, так что можно провести рефакторинг до вспомогательной процедуры. Обратите внимание, что было бы не лучшим решением встроить сравнение, потому что это повлечет за собой двойную оценку рекурсивных вызовов - лучше придерживаться вспомогательной процедуры, будь то max или my-max.

Кроме того, второй вызов max не нужен в вашем коде - если есть только одно значение, зачем вам искать максимум?

person Óscar López    schedule 03.12.2012
comment
Можно ли для этого использовать car и cdr? - person Layla; 03.12.2012
comment
@Layla, что ты имеешь в виду? для нахождения наибольшего между двумя числами требуется только сравнение и условное выражение, car и cdr используются для управления списками. Вы можете привести пример? - person Óscar López; 03.12.2012
comment
Не знаете, как проще всего посчитать глубину, вы можете привести мне пример? - person Layla; 03.12.2012
comment
поэтому для вашей функции my-max вы имеете в виду что-то вроде (define (my_max a b) (cond ((›a b) a) (b))) - person Layla; 03.12.2012
comment
@Layla на каждом шаге рекурсии добавьте 1 к максимальной глубине всех рекурсивных вызовов до этого момента, имея в виду, что список состоит из атомов и списков - person Óscar López; 03.12.2012
comment
Я не думаю, что «если» разрешено в R5RS. - person Layla; 04.12.2012
comment
@Layla конечно это так! (см. ссылку, раздел 4.1.5). На каком диалекте Лиспа нет if? - person Óscar López; 04.12.2012
comment
Ничего, с другими функциями напутал. (определить my-max (lambda (a b) (if (›a b) a b))) Это то же самое, не так ли? - person Layla; 04.12.2012
comment
THX, но у меня все еще проблема с кодом. Из примера, когда вводится как (depth '((id = id + id) (if bool then (if bool then (id = id + id)) (id = const / const) (id = id + id)) ( в то время как bool (id = id - const) (id = id - id)))), он должен получить 2 за ответ, но я всегда получаю еще один ... - person Layla; 04.12.2012
comment
@Layla, вы должны добавить 1 к результату максимума, в настоящее время вы находите максимум глубины + 1. Я надеюсь, что это сработает, и если этот ответ был для вас полезным, пожалуйста, не забудьте принять его, нажав на галочку слева ... это был очень долгий чат! - person Óscar López; 04.12.2012
comment
То есть вы имеете в виду, что когда я пишу выходной код, я должен делать там -1? - person Layla; 04.12.2012
comment
@Layla да, это правильный вариант - person Óscar López; 04.12.2012