9/1 日常生活忌憚
気が付けば今年も残り 1/3 です。
そうか。残り1/3で餅食って昼寝する生活…と、休みが明けたら明けたで休みの事ばっかり考えてる学生ってイヤですね(ぉ
やる事は山積みなんですが、最近はDiablo2ばっかりやってます。ん〜、このクエスト解いたら…おっ、次のクエストだ… x ∞ の地獄の永久ループ。マシンがフリーヅしてもやめないぞ。熱暴走の可能性は高いけどフリーヅ。やはりメルトダウンとか言った方がいいんだろうか。
昼に買物に出かけたのですが、不意にキューピーハーフは、マヨネーズではないというパツキンの姉さんがアメフトする宣伝を思い出したので、マヨネーズで無いとして、では一体なんなンだ！という想いから、食料品売り場にてキューピーハーフを手にとってみました。
品名 : 半固体ドレッシング
…なんか。
それにしても、食卓にて、ねぇ、そこの半固体ドレッシング取って…といわれたら、僕ぁどんな顔したらいいんですか、父さん！
不意に、思い出し話。
最初の最初にアルゴリズムと言う物を意識して、良く使われてるアルゴリズムを調べて使ってみたというのは、ユークリッドの互除法だったような。
分数電卓を作ろう！と思っていたのですが、なにぶんCPUは遅いしBASICだしで、分数計算には必須の最大公約数の決定のためのルーチンが遅い遅い。空のループを1000回回すだけで約一秒かかるという環境でしたし。
自然数AとBの最大公約数を求めるために、どうやってたかというと、
function GCM(A,B:Integer):Integer;
var
d:Integer; //除数
begin
//A > Bになるように入れ換え
if A <= B then
swap(A,B); //AとBをひっくり返す手続きが有るとして読んでくれい
// resultは関数の返り値、公約数が入る
result:=1;
//除数2からスタート
d:=2;
while d <= B then begin
if (A mod d = 0) And (B mod d) = 0 then begin
//dが公約数なら、両方を割る
A:=A div d;
B:=B div d;
//公約数に記録
result:=result * d;
//最初からやってみる
d:=2;
end else begin
//ダメなら除数を増やしてみる
Inc(d);
end;
end;
end;
なんだかセンター試験の問題文に出てくるようなプログラムです(^^;)
余談ですが、最初に変数の宣言を書く必要の無い言語は、初学者には全く向かないし、出現位置(if 文の中か否か)によって = 演算子の意味(比較演算子か代入演算子か)が異なるので、BASICって高校生に教えるべき言語としては不適切なのではないかと思うのは、僕だけでしょうか。そういえば、C / C++も出現位置によって * 記号の意味かが異なります。ポインタが難しいと感じる理由は、実はここにもあるんじゃないかと思うんですが…
さてさて、ソースを日本語にすると、
- A > B になるように、 必要ならAとBの値を入れ替え
- 2〜B の範囲で、AとBを両方割り切れる数dが出現するかテスト
- dが出たら、AとBをdで割る
- dが出なくなるまで 2. 3.を繰り返す
…非常に正直です(^^;) そして、遅いです。当時の環境では、３桁の数同士でも、それなりに待たされた記憶が(^^;)
ユークリッドの互除法を使うと、こう。
function GCM(A,B:Integer):Integer;
var
m:Integer; //余剰
begin
//A > Bになるように入れ換え
if A <= B then
swap(A,B); //AとBをひっくり返す手続きが有るとして読んでくれい
//答えが出るまで帰っちゃダメ
while True do begin
// A割るB の余りを出す
m := A mod B;
if m = 0 then begin
//割り切れてるなら、そこで終了
result:=B;
exit;
end else begin
//割り切れなかったら、AにBを、Bに余りを代入して、もう一回
A:=B;
B:=m;
end;
end;
end;
しらみつぶしに探すのではなく、割った余りを利用しているので、早い早い。当時の環境でも瞬きするかしないかの内に、計算結果が返ってくるじゃありませんか！
掛け算でも割り算でもなくて、余りに着目することで事で最大公約数が求まるというのは、パッと見では不思議なのですが、良く考えれば確かにそう。全く、古人の知恵というのは偉大です。
このようにして、アルゴリズムとやらに味をしめたのですが、
- 最近は、基本的なアルゴリズムに特許が取られる事態が…
- このようにして現在に至り、現在では…
- 例えばゲームを作るからと言って、ゲームを作るためのアルゴリズムなどというものは存在せず…
…どれに繋がると面白い話なんでしょうね(^^;)
正解は４番。尻切れトンボで終わってみたいと思います。
戻る