2005年06月02日
冪のソート
- 2005-06-02 (Thu)
- プログラミング
講義（単位取得済み）の課題で適当な基数の冪を下の桁からの辞書順でソートするプログラムを作れというものが出た．ついでに，階乗も同様にソートせよとの指示も出ている．
とりあえず，階乗を下の桁からソートするのは単純なのでプログラムする気力なし．やり方は以下のとおり．階乗の場合は 5 の倍数が現れるごとに 0 が少なくとも一つ増えるので，再開桁から連続する 0 の数が等しい５個程度の組をソートしておけば，あとはその組を 0 の数の多い順に並べるだけである．よって，このソートは入力サイズを n とすると O(n) で終了する．ちなみに，５個程度の組をソートするのに必要な有効桁数は１０桁もあれば足りるはずなので，
階乗を順に生成するのも n に関係ないオーダでできる．
ということで，ターゲットは冪のソートで，基数最下位桁が 0 でないものに．とりあえず案はできているのでコードを書きますか．
- Comments: 0
- TrackBack (Close): -