読者です 読者をやめる 読者になる 読者になる

totofugaのブログ

PerlとかC++のプログラム系の話

gauss-jordan法

#!/usr/bin/perl use strict; use warnings; use Data::Dumper; my $a = [ [1, -1, 1], [2, 1, -3], [3, 2, -1], ]; my $b = [ [-5], [19], [16], ]; gauss_jordan($a, $b); print Dumper($a); print Dumper($b); sub gauss_jordan { my ($a, $b) = @_; my $…

内部探索(interpolation search)

データが均等なランダムの場合loglogNの速度になるため、 binary searchより効率がよくなるが、 一つの計算時間は増えるため、データがかなり大きい場合にのみ有効。 やってることは、binary searchのメディアンの選び方を現在のデータから 有効そうな位置を…

グラフ

グラフの内部表現で通常c言語だと エッジの数によって隣接行列か隣接リストのどっちかで表すが、 メモリと速度をあまり気にしない場合perlだと ハッシュを使った下記のような形で作るのが簡単。 my $adj; sub add_connect { my ($a, $b) = @_; $adj->{$a}->{…

ヒープ木

順位キューで挿入と探索をlogNで行いたいときに使う 二分ヒープ - Wikipedia 挿入のときは最下層の一番左に挿入して補正 取り出すときは一番上から取得 => 最下層の一番左にあったものを上に付けて補正 を行うので常に完全バランスが取れて、左からノードが…