2

私はスキームを学習しています。私がしなければならないことの1つは、リストが反映されているかどうかを調べるための再帰です。つまり、リストを逆にすると同じように見えます。リストに逆の方法を使用できないように、基本的に行う必要があります。明らかな再帰も使用する必要があります。問題は、スキームでは、リストにアクセスしたり、私たちが学んだ非常に基本的なものを使用してリストを短縮したりするのが非常に難しいことです。これらはリンクリストのようなものだからです。インデックスを使わずにやりたいです。そうは言っても、私にはいくつかのアイデアがあり、これらのいずれかが十分であるかどうか疑問に思っていました。スキームの基本を使用すると、実際にもっとうまくできると思いますか。

  1. 再帰（私の実装）を使用してリストを逆にし、元のリビジョンとこのリビジョンを比較します。リスト。
  2. リストの残りの部分を繰り返して最初と最後の要素を比較し、最後の要素を見つけて最初と比較します。繰り返した回数を追跡し、リストの最後から2番目の要素に対して1回少なくして、リストの2番目の要素と比較します。（これは私が試したので非常に複雑で失敗しましたが、皆さんも同じことをしたと思います）
  3. リストを短くして、毎回最初と最後の要素を削除して比較します。これがスキームの基本を使用して実行できるかどうかはわかりません。
  4. あなたの提案やヒントなど。私はスキームに非常に慣れていません。読んでくれてありがとう。私はそれが長いことを知っています。
4

3 に答える 3

3

リストを元に戻さずに回文であるかどうかを確認することは、DanvyとGoldbergによる「ThereandBackAgain」で説明されている手法の例の1つです。彼らは(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"))

したがって、あなたが取り組んでいる問題の1つのポイントは、選択したデータ構造（問題の表現）が問題の解決に強い影響を与える可能性があることを示すことだと思います。

（余談ですが、＃2は確かに実行可能ですが、単一リンクリストのデータ構造の粒度に反します。＃3へのアプローチでは、表現を根本的に変更する必要があります。一見したところ、変更可能である必要があると思います。後方に進むことができる必要があるため、あらゆる正義を解決するための二重リンクリスト。）

于 2012-09-30T00:43:00.743 に答える
0

dyooの質問に答えるために、あなたは自分が中間点にいることを知る必要はありません。あなたはただ特定の比較をする必要があります。その比較が機能する場合は、a）文字列が可逆的である必要があり、b）中間点にいる必要があります。

あなたがそれに手を伸ばすことができれば、より効率的な解決策がそこにあります...

于 2012-09-30T13:53:50.747 に答える