自然数の組成のO(1)時間生成について

書誌事項

タイトル別名
  • シゼンスウ ノ ソセイ ノ O 1 ジカン セイセイ ニ ツイテ
  • O(1) Time Algorithms for Generating Integer Compositions

この論文をさがす

抄録

順序を考慮して自然数nを適当な自然数の和に分解する問題は自然数の組成と呼ばれる.和を構成する数字を和因子と呼び,次式a_1+…+a_r=n, a_i≥1, を満たす文字列a_1a_2…a_rが自然数の組成である.GrimaldiとMeadowsは,最大の和因子がたかだかkであるような自然数の組成の個数はk段フィボナッチ数列に一致することを証明した.本論文では,ある自然数の組成から次の組成を生成する時間がO(1)時間であるような列挙アルゴリズムを二つ提案する.

収録刊行物

参考文献 (8)*注記

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ