- - PR -
アルゴリズムパズル（リンクリスト）
| 投稿者 | 投稿内容 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2005-11-16 06:44
すみません、.NETと直接は関係ないのですが、他に適当な会議室が見当たらなかったのでここに投稿させてください。
ウェブ上で見つけた問題ですが、いい答えが思いつかずに気になっています。元は以下のアドレスの11月13日の記事です。 http://www.cotton-tree.com/garyu/
どなたかいいアイデアがあれば教えてください。 | ||||||||
|
投稿日時: 2005-11-16 12:17
こんにちは、でっちです。
単方向リストって座学で聞きかじった程度なので、恥ずかしい勘違いをしているかもしれませんが、 次のポインタに従い順次参照して、 x回リンクを辿った段階で、参照したポインタの最大値がx未満の場合循環参照してる きちんと最後まで辿ることができればOK って感じじゃないですかね？ | ||||||||
|
投稿日時: 2005-11-16 12:33
こんにちは
通常はそれでいいかもしれませんけど、問題は
となっているので正解ではないんですかねぇ？ でも１パスでという条件がないから正解なんですかねぇ？ 私も良くわかりませんが、O(n)っていうのはCPU時間がnに比例するってことですよね？ だとしたら、2度走査してもいいんですかねぇ？もしかして引っ掛け問題？ 1度目でｎを求める。 2度目ででっち６号様のとおり がらす様、パズルですからご自分でも良く考えてみたほうがいいと思います。 ページの著者も要望があれば１週間後あたりに解答を出しますと書いてありますし.. | ||||||||
|
投稿日時: 2005-11-16 12:52
ポインタを２つ用意して追いかけっこする。
_________________ IEEE-CSDP 2004-2007 | ||||||||
|
投稿日時: 2005-11-16 13:01
こんにちは。
だと、循環参照している場合、n の数が分からないかなぁ。計算量も O(2n) になるような･･･。（くわしくないのでどなたかつっこんで下さい） リンクリストを辿る度に、そのアドレスを保持しておいて、重複してないか確認する、かな。（この時の計算量は O(n) なのか分からない･･･） | ||||||||
|
投稿日時: 2005-11-16 13:06
ネタなのかなぁ？
「n が不明」な時点で O(n) が算出不可能だと思うんだけど。。。 「初期条件として n が不明」なのであれば、やっぱり n の探索からはじめるのがスジかな？ _________________ // 渋木宏明 (Hiroaki SHIBUKI) // http://hidori.jp/ // Microsoft MVP for Visual C# // // ＠ＩＴ会議室 RSS 配信中: http://hidori.jp/rss/atmarkIT/ | ||||||||
|
投稿日時: 2005-11-16 13:17
思い付きだけど、ノード間で大小関係を考えて、ソートしようとしてみる。そのソートの途中で、ジャンケンのようになって矛盾が出てくるかどうかを調べる？O(n)でできるのかな？
| ||||||||
|
投稿日時: 2005-11-16 13:19
いや、いいんではないですかね？ アルゴリズムの計算量が、その n に比例するようなアルゴリズムであるならば、O(n) だ、というわけでなないのかな･･･？（多分） _________________ 囚人のジレンマな日々 | ||||||||
スキルアップ／キャリアアップ（JOB@IT）
Copyright © ITmedia, Inc. All Rights Reserved.
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。