Home > Archives > 2005年06月02日

2005年06月02日

冪のソート

講義(単位取得済み)の課題で適当な基数の冪を下の桁からの辞書順でソートするプログラムを作れというものが出た.ついでに,階乗も同様にソートせよとの指示も出ている.

とりあえず,階乗を下の桁からソートするのは単純なのでプログラムする気力なし.やり方は以下のとおり.階乗の場合は 5 の倍数が現れるごとに 0 が少なくとも一つ増えるので,再開桁から連続する 0 の数が等しい5個程度の組をソートしておけば,あとはその組を 0 の数の多い順に並べるだけである.よって,このソートは入力サイズを n とすると O(n) で終了する.ちなみに,5個程度の組をソートするのに必要な有効桁数は10桁もあれば足りるはずなので,

階乗を順に生成するのも n に関係ないオーダでできる.

ということで,ターゲットは冪のソートで,基数最下位桁が 0 でないものに.とりあえず案はできているのでコードを書きますか.

Home > Archives > 2005年06月02日

Search
Feeds

Page Top