No Such Blog or Diary

«Prev || 1 | 2 | 3 |...| 857 | 858 | 859 |...| 884 | 885 | 886 || Next»

Pickの定理

格子点上に頂点を持つ多角形の面積と内部の格子点数と辺の上に載っている格子点数の間には関係式がある.

「Pickの定理」 平面上の格子多角形 P に対して,辺上にある格子点の個数を b, P の内部格子点数を c とすると, その面積 S(P) は次式となる: S(M) = (c-1) + b/2 .

基本的なアイデアは多角形を面積が 1/2 の三角形に分解していくイメージのはず.とりあえず,この定理を知っていると格子点上の図形問題が格段に簡単に解けるに違いない.

自転車で180度回転

今朝の道路は雨に濡れて滑りやすかった.面白そうなので赤信号の手前で自転車の後輪にブレーキを掛けて後輪を滑らしてみた.そしたら見事に180度回転した.

いやぁ,急ブレーキは危ないねぇ.

ThunderBird のプロファイル設定

ThunderBird を使うのにプロファイルの設定をデフォルトのままにしてしまい,設定の保存先がCドライブになっていた.これではOSの再インストール時に消してしまう恐れがあるため,新しいプロファイルを作って設定ファイル群を別のドライブへ移動.プロファイルを設定するには thunderbird.exe -p するか,スタートメニューから Profile Manger を選択.あとはディレクトリを指定して新しいプロファイルを作成するだけ.古いのは危ないので消しておく.次回以降も新しいプロファイルで起動されるようにチェックを入れたら ThunderBird 起動.どうやらうまくいったようだ.

続・冪のソート

ということで,横でゲームをしつつ冪を下位桁からの辞書順にソートするプログラムを組んでみた.冪をソートするときにはその桁数が大きすぎてメモリに載らないことが問題になる.そこで,基本的にメモリの節約をメインに考えて作成した.節約のための重要点は,冪をソートするといってもその全ての桁が必要ではなく,基本的には下位の桁の一部しか必要でないこと.そして,冪の下位桁は上位桁を計算しなくても正確に求められ,再計算も簡単であること.これらに基づき,最初は下位の一部を計算しておき,ソートのときに区別が付かなければより上位の桁まで再計算するようにした.

実際に計算してみると,2の冪の場合には冪が20000000になっても下位16桁だけでソートが完了.思いのほか下位桁がバラバラのようである.このときのメモリ使用量は 1G強.時間は... 分単位.それなりに動くプログラムが出来上がって満足.単位は去年とってしまったけど課題を提出しても良いかなぁ?

冪のソート

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

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

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

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

HDDデータ消去

借りていたノートPCの返却のため HDD の中身を適当に消去することにした.OSが起動しなくなって良いのなら楽なのだが,動作確認とか言ってOSを起動させるので消すに消せない.しょうがなく,手動でほとんどのソフトをアンインストールしてレジストリも掃除して... さらに空いたディスク領域に dd コマンドでランダム書き込み2回+ゼロ書き込み1回でデータ消去.とりあえずこんなんでいいかと.時間ないし.

«Prev || 1 | 2 | 3 |...| 857 | 858 | 859 |...| 884 | 885 | 886 || Next»
Search
Feeds

Page Top