平々毎々 (Hey hey, My my) | アルゴリズムパズル（リンクリスト）に答える
「諸悪の根源は物理的」より： 単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。つまり、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは出来ない。 これは有名なアルゴリズムなので知っている人も多いと思う。 回答 ポインタaとbを用意して、aは1ずつ、bは2ずつインクリメントする(次の要素に進む)。 もしループしているなら、aがループによって以前の要素に戻ってくる前に必ずbと同じ位置を指すときが来る。 ループしてなければbが終端に到達して終わり。 なぜこうなるのかは、図で説明するとわかりやすい。 循環のある
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
BigBold - Informasi Tentang Bisnis dan Marketing
東京工業大学 情報理工学院 数理・計算科学系
