人気ブログランキング | 話題のタグを見る

とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
その他のジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
カメとウサギのアルゴリズム、もしくは・・・
Exercise 3.19について他の人の解答を見てみると、メモリ消費量を抑えつつ線形時間で完了するやり方があるということで、うならされました。

私の考えたdepthを使ったやり方は、リストをカントールの証明のように操作する方法ですが、それだとリスト長(もしくは無限ループの大きさ)に対して2乗オーダで計算時間が増えます。

Barry Allisonさんのコードでは「カメとウサギのアルゴリズム」として紹介されていた方法ですが、最初このコードを読んでも何をやっているのかわかりませんでした。

その方法は、リストの先頭から、1歩ずつ進むポインタ(カメ)と2歩ずつ進むポインタ(ウサギ)を同時に動かしてやるやり方なのですが、直感的にはカメとウサギがどんどん離れていくのでうまくいかないように思えます。

しかし、循環リストの構造としては、L = (a1 ... an b1 ... bm b1 ... bm b1 ...)というような構造をしていて、2つのポインタがanより後ろにあれば、ポインタの距離がmの整数倍の条件で一致するという特徴があります。

なので、カメポインタで必ず1歩は進むようにすればとっととanよりも先に進むことができ、カメポインタとウサギポインタの距離を常に離していくことで距離mを同時に探索することもできるということです。アタマいい〜

以下は私がアレンジした「カメとウサギのアルゴリズム」のコードです。
(optional lineの行はあってもなくてもいいです)

(define (cycle? lst)
  (define (go-downstairs walker runner)
    (cond ((null? runner) #f)
          ((null? (cdr runner)) #f)
          ((eq? runner walker) #t)
          ;((eq? (cdr runner) walker) #t) <- optional line ->
          (#t (go-downstairs (cdr walker) (cddr runner)))))
  (and (not (null? lst))
       (not (null? (cdr lst)))
       (go-downstairs lst (cddr lst))))


by tempurature | 2015-08-26 00:59 | scheme
<< chromeリモートデスクトッ... SICP Exercise 3... >>