カテゴリ
全体プログラミング 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で競技プログラミングメモ帳
最新のトラックバック
ライフログ
検索
タグ
racket
その他のジャンル
ブログパーツ
最新の記事
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
|
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
| ||||||||||||||||||||||
ファン申請 |
||