Проверка обратного списка такая же, как и список без изменений?

Я изучаю схему, и одна из вещей, которые мне нужно сделать, это рекурсия, чтобы выяснить, является ли список отражающим, то есть список выглядит так же, когда он перевернут. Я должен сделать это примитивно, поэтому я не могу использовать обратный метод для списков. Я также должен использовать рекурсию, что очевидно. Проблема в том, что на схеме очень сложно получить доступ к списку или сократить его, используя самые базовые вещи, которые мы изучили, поскольку они чем-то похожи на связанные списки. Я также хочу обойтись без использования индексации. С учетом сказанного у меня есть несколько идей, и мне было интересно, достаточно ли чего-то из них, и как вы думаете, я мог бы сделать это лучше с основами схемы.

  1. Переверните список, используя рекурсию (моя реализация), и сравните оригинал и эту версию. список.
  2. Сравните первый и последний элемент, рекурсивно просматривая остальную часть списка, чтобы найти последний элемент и сравнить его с первым. Отслеживая, сколько раз я рекурсировал, а затем делаю это на один меньше для второго последнего элемента списка, чтобы сравнить со вторым элементом списка. (Это очень сложно сделать, так как я пробовал и потерпел неудачу, но я хочу видеть, что вы, ребята, сделали бы то же самое)
  3. Сократите список, чтобы каждый раз обрезать первый и последний элемент, и сравните. Я не уверен, что это можно сделать, используя основы схемы.
  4. Ваши предложения или намеки или что-нибудь. Я очень новичок в схемах. Спасибо за чтение. Я знаю, что это долго.

recursion reverse scheme racket
person shn    schedule 30.09.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я согласен, что № 1 кажется здесь подходящим. Это просто, и я не могу представить, чтобы это потерпело неудачу. Возможно, у меня недостаточно сильное воображение. :)

Другие варианты, которые вы рассматриваете, кажутся неудобными, потому что мы говорим о связанных списках, которые напрямую поддерживают последовательный доступ, но не произвольный доступ. Как вы заметили, «индексирование» в связанный список запрещено. В конце концов он послушно продвигается вниз по структуре списка. Из-за этого другие варианты, безусловно, выполнимы, но они дороги.

Эти расходы связаны не с тем, что мы используем Scheme, а с тем, что мы имеем дело со связанными списками. Просто чтобы убедиться, что это ясно: в схеме есть векторы (массивы), которые поддерживают быстрый произвольный доступ. Проверить палиндромность вектора так же просто, как и следовало ожидать:

#lang racket
;; In Professional-level Racket

(define (palindrome? vec)
  (for/and ([i (in-range 0 (vector-length vec))]
            [j (in-range (sub1 (vector-length vec)) -1 -1)])
    (equal? (vector-ref vec i)
            (vector-ref vec j))))

;; Examples
(palindrome? (vector "b" "a" "n" "a" "n" "a"))
(palindrome? (vector "a" "b" "b" "a"))

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

(Кроме того: № 2, безусловно, выполним, хотя он противоречит сути структуры данных односвязного списка. Подход к № 3 требует радикального изменения представления: на первый взгляд, я думаю, вам понадобятся изменяемые, списки с двойной связью, чтобы отдать должное решению, поскольку вам нужно иметь возможность идти назад.)

person dyoo    schedule 30.09.2012
comment
Спасибо за ответ. Я думаю, что принял решение, и я выбираю номер 1. Это самый простой, хотя меня беспокоит его эффективность. Модификация будет заключаться в том, что я беру вторую половину списка, переворачиваю ее и сравниваю с первой половиной. Столько нудной работы, ура! - person shn; 30.09.2012
comment
Проблема с предложенной вами модификацией заключается в следующем: откуда вы знаете, что находитесь на полпути? :) - person dyoo; 30.09.2012
comment
:) Ага. Вот почему я сказал так много утомительной работы, потому что теперь мне нужно найти длину списка и разделить на 2, затем повторить список столько раз и получить вторую половину списка. Затем переверните этот список и сравните с первой половиной. О БОЖЕ, должен быть более простой способ. :( - person shn; 30.09.2012

arrow_upward
3
arrow_downward

Проверка того, является ли список палиндромом без обращения, является одним из примеров метода, описанного в "Туда и обратно" Дэнви и Голдберга. Они делают это в (ceil (/ (length lst) 2)) рекурсивных вызовах, но есть более простая версия, которая делает это в (length lst) вызовах.

Вот скелет решения:

(define (pal? orig-lst)
  ;; pal* : list -> list/#f
  ;; If lst contains the first N elements of orig-lst in reverse order,
  ;; where N = (length lst), returns the Nth tail of orig-lst.
  ;; Otherwise, returns #f to indicate orig-lst cannot be a palindrome.
  (define (pal* lst)
    ....)

  .... (pal* orig-lst) ....)

Похоже, это домашнее задание, поэтому я не хочу заполнять все пробелы.

person Ryan Culpepper    schedule 30.09.2012
comment
Я также новичок в схеме ... мне просто интересно, в чем разница между приятелем? и приятель - person neham; 14.04.2013

arrow_upward
0
arrow_downward

Чтобы ответить на вопрос dyoo, вам не нужно знать, что вы находитесь на полпути; вам просто нужно сделать определенное сравнение. Если это сравнение работает, то а) цепочка должна быть обратимой и б) вы должны быть на полпути.

Так что есть более эффективное решение, если вы можете просто дотянуться до него...

person itsbruce    schedule 30.09.2012