いちばん長いしりとり
Posted feedbacks - Common Lisp
kozima
#9420()
[
Common Lisp
]
普通の深さ優先探索。全パターン生成してるだけなのですが、正確な計算量はどれくらいになるのでしょうね。
ノード数 n のグラフのパスの数は、完全グラフの場合で Σ_k P(n, k) = n! * Σ_k 1/k! < n! * e なので、O(N!) で上から評価できるのだとは思いますが。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | (defun first-char (s) (char s 0))
(defun last-char (s) (char s (1- (length s))))
(defun longer (list1 list2)
(loop for x = list1 then (cdr x) and y = list2 then (cdr y)
if (null x) return list2
if (null y) return list1))
(defparameter *word-table* nil)
(defun get-next-words (c) (gethash c *word-table*))
(defun make-table (word-list key)
(let ((h (make-hash-table)))
(loop for w in word-list do (push w (gethash (funcall key w) h)))
h))
(defun longest (word-list)
(let ((*word-table* (make-table word-list #'first-char)))
(reverse (reduce #'longer word-list :key #'longest-path-from))))
(defun longest-path-from (word)
(search-path (list word)))
(defun search-path (path)
(let* ((w (car path))
(c (last-char w))
(words (set-difference (get-next-words c) path)))
(if words
(reduce #'longer words
:key (lambda (next) (search-path (cons next path))))
path)))
|
greentea #9391() Rating5/7=0.71
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。
なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。
ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう
see: 難聴者のための単語了解度試験用単語リスト
[ reply ]