- PR -

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

投稿者投稿内容
jk
ベテラン
会議室デビュー日: 2005/08/19
投稿数: 94
投稿日時: 2005-11-16 15:02
あぁ寝ぼけてました。
循環してたらnはもとまりませんねぇ
引用:

1度目でnを求める。



cats様、zar様
すばらしい。
最悪は逃げるほうのポインタが1周余計にループ部を多く回ることになりそうですが
ばっちり判定できてますね。

感動しました。
一郎
ぬし
会議室デビュー日: 2002/10/11
投稿数: 1081
投稿日時: 2005-11-16 15:02
なるほどねぇ。
2つのポインタで追いかけっこですか。

catsさんのソースを私なりに書いてみました。(C#)
nullか調べるのはlじゃなくてpですね。pの方が先に進んでますから。

コード:
bool IsDangling(List l)
{
	if(l == null)return false;

	List p = l.Next;

	while (true)
	{
		if(l == p)return true;
		if(p == null || p.Next == null)return false;

		l = l.Next;
		p = p.Next.Next; 
	} 
}

kanai
ベテラン
会議室デビュー日: 2004/09/13
投稿数: 98
投稿日時: 2005-11-16 15:06
kanaiです。

ごめんなさい。先ほどのコードはバグがありました。
もう一度出直してきます。
kanai
ベテラン
会議室デビュー日: 2004/09/13
投稿数: 98
投稿日時: 2005-11-16 15:32
kanaiです。

再びチャレンジしてみました。

先に投稿したコードと同様、リンクリストはInteger配列で表現し、
添字0の要素がリストの先頭、要素-1はリストの末尾を表すものとします。

list(i)とlist(list(i))の要素を交換してもリンクリストとしては等価で
あることに着目し、要素を順次交換していき、末尾にたどり着くか、
それとも同じポインタを指し続けるのかを判定しています。

こんな感じでいかがでしょう?

コード:

Module Module1

Sub Main()
'ループありのリスト
Dim loopedlist() As Integer = {1, 2, 3, 4, 2}
Console.WriteLine("Result = " & IsLooped(loopedlist, 0))
Console.WriteLine()
'ループなしのリスト
Dim nolooplist() As Integer = {1, 2, 3, 4, -1}
Console.WriteLine("Result = " & IsLooped(nolooplist, 0))

Console.ReadLine()
End Sub

'リンクリスト中にループがあるかを判定(True:あり、False:なし)
Private Function IsLooped(ByVal list As Integer(), ByVal index As Integer) As Boolean
OutputList(list)
If list(index) = -1 Then
'index番目の要素が末尾ならばループなし
Return False
ElseIf list(index) = index Then
'index番目の要素が添字と同じならループあり
Return True
Else
'リストのindex番目の要素とlist(index)番目の要素を交換する
Dim newlist As Integer() = ExchangeMember(list, index, list(index))
'交換後のリストに対して再帰呼出
Return IsLooped(newlist, newlist(index))
End If
End Function

'リンクリストの指定した2つの要素を交換する
Private Function ExchangeMember(ByVal list As Integer(), ByVal index1 As Integer, ByVal index2 As Integer) As Integer()
Console.WriteLine("change " & index1 & " <-> " & index2)
Console.WriteLine()
'配列をコピー
Dim newlist(list.GetUpperBound(0)) As Integer
For i As Integer = 0 To list.GetUpperBound(0)
newlist(i) = list(i)
Next
'要素を交換
newlist(index1) = list(index2)
newlist(index2) = list(index1)
Return newlist
End Function

'リンクリストの内容を出力する
Private Sub OutputList(ByVal list As Integer())
Console.Write("index ")
For index As Integer = 0 To list.GetUpperBound(0)
Console.Write(index)
Console.Write(" ")
Next
Console.WriteLine()
Console.WriteLine("-----------------------")
Console.Write("value ")
For Each member As Integer In list
Console.Write(member)
Console.Write(" ")
Next
Console.WriteLine()
Console.WriteLine()
End Sub

End Module



編集
・ExchangeMemberに一箇所間違いがあるのを修正
・確認用に、リンクリストの内容を出力するように変更
・IsLoopedで引数listをコード中で再利用している箇所をリファクタリング
・コメントを追加

編集2
・ExchangeMemberで引数listが書き換えられてしまうのを修正
(配列をコピーするコードが美しくないのですが・・・)

[ メッセージ編集済み 編集者: kanai 編集日時 2005-11-16 16:07 ]

[ メッセージ編集済み 編集者: kanai 編集日時 2005-11-16 17:01 ]
ぼのぼの
ぬし
会議室デビュー日: 2004/09/16
投稿数: 544
投稿日時: 2005-11-16 15:55
一個思いつきました。
休憩中に考えて細かく検証してないので、自信ありませんが、とりあえず投下してみます。

まず、リストを順方向に辿っていくAがいます。
Aは自分が辿ってきた道筋を、逆向きの単方向リストとして作成していきます。
そして常にAの一個前にいるaと、逆方向のリストを辿っていくBがいます。
Bは、リストの先頭に達したら、Aと同じ位置に戻ります。
で、リストの先頭に達する前にBがAまたはaと出会ったら、
循環参照ハケーン!!(・∀・)
以下、コードだとわかりづらいので一例を図化します。

コード:
(  )→(AB)→(  )→(  )→(  )→(  )→(  )→(  )
                   ↑                      │
                   └────────────┘
( B)→(a )→(A )→(  )→(  )→(  )→(  )→(  )
                   ↑                      │
                   └────────────┘
(  )→(  )→(a )→(AB)→(  )→(  )→(  )→(  )
                   ↑                      │
                   └────────────┘
(  )→(  )→( B)→(a )→(A )→(  )→(  )→(  )
                   ↑                      │
                   └────────────┘
(  )→( B)→(  )→(  )→(a )→(A )→(  )→(  )
                   ↑                      │
                   └────────────┘
( B)→(  )→(  )→(  )→(  )→(a )→(A )→(  )
                   ↑                      │
                   └────────────┘
(  )→(  )→(  )→(  )→(  )→(  )→(a )→(AB)
                   ↑                      │
                   └────────────┘
(  )→(  )→(  )→(A )→(  )→(  )→( B)→(a )
                   ↑                      │
                   └────────────┘
(  )→(  )→(  )→(a )→(A )→( B)→(  )→(  )
                   ↑                      │
                   └────────────┘
(  )→(  )→(  )→(  )→(aB)→(A )→(  )→(  )
                   ↑                      │
                   └────────────┘

渋木宏明(ひどり)
ぬし
会議室デビュー日: 2004/01/14
投稿数: 1155
お住まい・勤務地: 東京
投稿日時: 2005-11-16 17:39
引用:

互いに素な、歩幅の忍者を放ち、後ろから追突したら ループ有。



なるほどー、確かに出来ますねw
らぶま
常連さん
会議室デビュー日: 2004/10/21
投稿数: 32
投稿日時: 2005-11-16 19:32
らぶまです。

もう答えは出ていますが、
私も思いついた案を出してみます。

問題文を「リストのノードの内容以外なら変更してよい」
と曲解すれば、

元のリストのノードとノードの間に新しいノードを追加しながら走査する。
nilに達するまでに、追加したノードに出会ったら循環リスト。

ノードにマーキングしているわけではないので、問題文の制約には抵触しないかなと・・
元のリストは破壊するので、問題の趣旨には反していますが・・・
(後で元に戻す処理を追加すればいいかな)。

ぼのぼのさんの書き方をお借りすると、と思ったらなぜか上手く表示されないので、
ちょっと変更。(8 )→(4 )で循環していると考えて、

丸が追加分,*がカレントのノード
コード:
--------------------------------------------------------------------------------

(*1)→(2 )→(3 )→(4 )→(5 )→(6 )→(7 )→(8 )→(4 )→...

(1 )→(○)→(*2)→(3 )→(4 )→(5 )→(6 )→(7 )→(8 )

(1 )→(○)→(2 )→(○)→(3 )→(○)→(4 )→(○)→(5 )→(○)→(6 )→(○)→(7 )→(○)→(8 )→(○)→(*4)→(○)→...






[ メッセージ編集済み 編集者: らぶま 編集日時 2005-11-16 19:35 ]

[ メッセージ編集済み 編集者: らぶま 編集日時 2005-11-16 19:35 ]
Jitta
ぬし
会議室デビュー日: 2002/07/05
投稿数: 6267
お住まい・勤務地: 兵庫県・海手
投稿日時: 2005-11-16 19:39
引用:

らぶまさんの書き込み (2005-11-16 19:32) より:

ぼのぼのさんの書き方をお借りすると、と思ったらなぜか上手く表示されないので、


[code]ですな

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