В Racket с использованием рекурсии как вернуть #true, если список "L" суммирует n, но никакие значения в L не дублируются - PullRequest
Новая
       15

В Racket с использованием рекурсии как вернуть #true, если список "L" суммирует n, но никакие значения в L не дублируются

0 голосов
/ 03 июля 2019

Этот вопрос может быть немного сложным, хотя я не уверен, что этот вопрос кажется мне по крайней мере довольно сложным. По сути, я пытаюсь написать кусок кода, который состоит из (список Num) и Num. Моя функция предназначена для вывода #true, если L является египетской дробью, которая представляет n. Египетская дробь - это сумма различных дробей, где числители равны 1 на тот случай, если некоторые не знают. В настоящее время у меня есть начало моего кода и у меня есть идея, чтобы решить вопрос, но я не знаю, куда идти дальше. Я бы предпочел, чтобы ответ сохранялся в том же формате, что и сейчас. Я практикую рекурсию и пытаюсь улучшить ее.

В моем коде у меня есть базовый случай, когда, если список пуст, он выдает # false.

Затем я написал случай, когда если какие-либо значения в L были повторены, то функция выдает # false

Затем я написал случай, когда, если сумма всех значений L равна значению n, функция вернет # true.

В моем последнем случае просто выводится #false, означающее, что сумма значений в L не равна n.

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

(define (egyptian? L n)
  (cond
    [(empty? L) #false]
    [(equal? (first L) (first (rest L)) (egyptian? (rest L))) #false]
    [( = n (+ (first L) (egyptian? (rest L))))#true]
    [else #false]))

Это то, что функция должна выводить 

(check-expect (egyptian? (list 1/2 1/3 1/6) 1) #true)
(check-expect (egyptian? (list 1/2 1/4 1/5 1/20) 1) #true)
(check-expect (egyptian? (list 1/2 1/3 1/4 1/5 1/6) 1.5) #false)
(check-expect (egyptian? (list 1/2 1/2 1/2 1/2) 1) #false)

Как видите, первые два случая являются #true, потому что сумма значений в списках равна "n". Третий случай неверен, потому что сумма значений в списке не равна "n". Четвертый случай неверен, поскольку значения в списке дублируются. Надеюсь, я предоставил достаточно информации по вопросу, с которым я борюсь.

1 Ответ

2 голосов
/ 03 июля 2019

Лучшая стратегия для этого (и многих других проблем) - разделить проблему на более мелкие части.Давайте начнем с простого нахождения суммы всех чисел в списке, это должно быть легко: 

(define (sum L)
  (if (empty? L)
      0
      (+ (first L)
         (sum (rest L)))))

Теперь давайте напишем процедуру, которая проверяет, являются ли элементы в списке уникальными.Это не так просто, как проверка одного элемента в списке следующим: повторяющийся элемент может быть в любом месте списка! 

(define (unique? L)
  (cond ((empty? L) #true)
        ((member (first L) (rest L)) #false)
        (else (unique? (rest L)))))

С этими процедурами наша основная проблема становится тривиальной:

(define (egyptian? L n)
  (and (unique? L)
       (= (sum L) n)))

Теперь вы видите, насколько мощна идея компоновки функций!В своей попытке решения вы смешивали код для трех разных задач в одной процедуре, и это усложняло понимание.

Еще один приятный эффект разделения проблемы на более мелкие части состоит в том, что вы можете переключать реализации позже., для более эффективных решений.Например, вот как мы написали бы процедуры sum и unique? в идиоматической ракетке: 

(define (sum L)
  (apply + L))

(define (unique? L)
  (= (length L) (set-count (list->set L))))
...