@IT会議室は、ITエンジニアに特化した質問・回答コミュニティ「QA@IT」に生まれ変わりました。ぜひご利用ください。
- PR -

アルゴリズムパズル(リンクリスト)

投稿者投稿内容
がらす
ベテラン
会議室デビュー日: 2005/07/14
投稿数: 99
投稿日時: 2005-11-16 06:44
すみません、.NETと直接は関係ないのですが、他に適当な会議室が見当たらなかったのでここに投稿させてください。

ウェブ上で見つけた問題ですが、いい答えが思いつかずに気になっています。元は以下のアドレスの11月13日の記事です。
http://www.cotton-tree.com/garyu/

引用:

単方向リンクリスト(連結リスト)がある。ノード数を n とするが、n の値は分からない。リスト中にループ(循環参照)が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。つまり、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは出来ない。



どなたかいいアイデアがあれば教えてください。
でっち6号
大ベテラン
会議室デビュー日: 2005/01/31
投稿数: 176
お住まい・勤務地: Kawasaki
投稿日時: 2005-11-16 12:17
こんにちは、でっちです。

単方向リストって座学で聞きかじった程度なので、恥ずかしい勘違いをしているかもしれませんが、
次のポインタに従い順次参照して、
x回リンクを辿った段階で、参照したポインタの最大値がx未満の場合循環参照してる
きちんと最後まで辿ることができればOK
って感じじゃないですかね?
jk
ベテラン
会議室デビュー日: 2005/08/19
投稿数: 94
投稿日時: 2005-11-16 12:33
こんにちは

引用:

x回リンクを辿った段階で、参照したポインタの最大値がx未満の場合循環参照してる


通常はそれでいいかもしれませんけど、問題は
引用:

ノード数を n とするが、n の値は分からない。



となっているので正解ではないんですかねぇ?
でも1パスでという条件がないから正解なんですかねぇ?


私も良くわかりませんが、O(n)っていうのはCPU時間がnに比例するってことですよね?
だとしたら、2度走査してもいいんですかねぇ?もしかして引っ掛け問題?

1度目でnを求める。
2度目ででっち6号様のとおり

がらす様、パズルですからご自分でも良く考えてみたほうがいいと思います。
ページの著者も要望があれば1週間後あたりに解答を出しますと書いてありますし..
iStation
大ベテラン
会議室デビュー日: 2003/12/08
投稿数: 158
投稿日時: 2005-11-16 12:52
ポインタを2つ用意して追いかけっこする。
_________________
IEEE-CSDP 2004-2007
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2005-11-16 13:01
こんにちは。
引用:

1度目でnを求める。
2度目ででっち6号様のとおり


だと、循環参照している場合、n の数が分からないかなぁ。計算量も O(2n) になるような・・・。(くわしくないのでどなたかつっこんで下さい)

リンクリストを辿る度に、そのアドレスを保持しておいて、重複してないか確認する、かな。(この時の計算量は O(n) なのか分からない・・・)
渋木宏明(ひどり)
ぬし
会議室デビュー日: 2004/01/14
投稿数: 1155
お住まい・勤務地: 東京
投稿日時: 2005-11-16 13:06
ネタなのかなぁ?

「n が不明」な時点で O(n) が算出不可能だと思うんだけど。。。

「初期条件として n が不明」なのであれば、やっぱり n の探索からはじめるのがスジかな?

_________________
// 渋木宏明 (Hiroaki SHIBUKI)
// http://hidori.jp/
// Microsoft MVP for Visual C#
//
// @IT会議室 RSS 配信中: http://hidori.jp/rss/atmarkIT/
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷        良回答(20pt)
投稿日時: 2005-11-16 13:17
思い付きだけど、ノード間で大小関係を考えて、ソートしようとしてみる。そのソートの途中で、ジャンケンのようになって矛盾が出てくるかどうかを調べる?O(n)でできるのかな?
囚人
ぬし
会議室デビュー日: 2005/08/13
投稿数: 1019
投稿日時: 2005-11-16 13:19
引用:

「n が不明」な時点で O(n) が算出不可能だと思うんだけど。。。


いや、いいんではないですかね?
アルゴリズムの計算量が、その n に比例するようなアルゴリズムであるならば、O(n) だ、というわけでなないのかな・・・?(多分)

_________________
囚人のジレンマな日々

アイティメディアの提供サービス

ホワイトペーパー(TechTargetジャパン/閲覧には会員登録が必要です)

スキルアップ/キャリアアップ(JOB@IT)