2

我正在学习计划，我必须做的一件事是递归以确定列表是否具有反射性，即列表在反转时看起来相同。我必须原始地这样做，所以我不能对列表使用反向方法。我还必须使用显而易见的递归。问题在于，使用我们学到的非常基本的东西来访问列表或缩短列表非常困难，因为这些有点像链表。我也想不使用索引。话虽如此，我有一些想法，想知道这些是否足够，你认为我实际上可以用方案的基础做得更好。

  1. 使用递归（我的实现）反转列表并比较原始版本和此版本。列表。
  2. 通过递归列表的其余部分来比较第一个和最后一个元素以找到最后一个元素并与第一个元素进行比较。跟踪我递归了多少次，然后对列表的倒数第二个元素少做一次，以与列表的第二个元素进行比较。（这非常复杂，因为我已经尝试过了，但最终失败了，但我想看看你们也会这样做）
  3. 缩短列表以每次修剪第一个和最后一个元素并进行比较。我不确定这是否可以使用方案的基础知识来完成。
  4. 你的建议或提示或任何东西。我对计划很陌生。谢谢阅读。我知道它很长。
4

3 回答 3

3

检查列表是否是回文而不反转它是Danvy 和 Goldberg 在“There and Back Again”中解释的技术示例之一。他们在(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) ....)

这听起来像是家庭作业，所以我不想填写所有空白。

于 2012-09-30T16:40:46.240 回答
2

我同意＃1似乎是要走的路。这很简单，我无法想象它会失败。可能我的想象力不够强大。:)

您正在考虑的其他选项似乎很尴尬，因为我们正在讨论链表，它直接支持顺序访问但不支持随机访问。正如您所注意到的，“索引”到链接列表中是禁止的。它最终尽职尽责地沿着列表结构前进。正因为如此，其他选择当然是可行的，但它们很昂贵。

这笔费用不是因为我们在 Scheme：而是因为我们正在处理链表。只是为了确保清楚：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的方法需要对表示进行彻底改变：乍一看，我认为你需要可变的，双链表可以解决任何正义问题，因为您需要能够向后行进。）

于 2012-09-30T00:43:00.743 回答
0

要回答 dyoo 的问题，您不必知道自己处于中途；你只需要进行一定的比较。如果该比较有效，那么 a) 字符串必须是可逆的并且 b) 您必须处于中间点。

因此，如果您能达到它，那就有更有效的解决方案......

于 2012-09-30T13:53:50.747 回答