トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

ダブリング

[アルゴリズム]

ダブリング

ダブリング(Doubling?)で検索しても、なかなか英語ではいい資料が出てこない。だったのですが、sataniC++様のブログ記事がかなり参考になりました。

    • 蟻本でダブリングの章を読んでみたのですが、なぜそうなっているかの説明が不足しておりいまいちでした

  アルゴリズム

 コードの説明
 上に示したコードは、次のような流れに沿って処理を行っています。
 
 各要素について、すぐ次の要素next[0]を調べる
 各要素について、next[0]を使ってnext[1]を求め、そのnext[1]を使ってnext[2]を求め、…としてnext全体を調べ上げる
 上で求めたnextを使って実際にp番目の要素のQ個次の要素を求める
  • 疑似コードをRuby化
    • ただしこれだとNが全体の要素より小さい場合にしか対応できない

+ 疑似コード1

  • 疑似コード(Nが全体の要素より大きい場合の対応)

+ 疑似コード2

お名前: コメント: