担当授業のこととか,なんかそういった話題。

主に自分の身の回りのことと担当講義に関する話題。時々,寒いギャグ。

<読書感想文1701>夏海公司,なれる!SE,2週間でわかる?SE入門

2017-11-20 21:13:07 | 
夏海公司,なれる!SE,2週間でわかる?SE入門,電撃文庫 (2010).


世の中に,この手のジャンルがあるということは十年ほど前から気づいてはいた。

しかし,腰を据えてちゃんと一冊通してラノベを読み通したのは,これが初めてである。

この歳で,いまさら学園ものだの,厨二病全開の世界系ファンタジーだのを読む気にはあまりなれないが,この作品の主人公は大卒でスルガシステム(株)というマイナーな中小企業で先輩にしごかれながらどうにかこうにか業務をこなしていく,といった,オトナ向けの物語のようなので,近所の図書館に置かれていたこともあり,試しに読んでみた。

主人公の桜坂工兵のOJT(オン・ザ・ジョブ・トレーニング)を担当する,いわば直属の上司は,どう見ても少女にしか見えない年齢不詳の女性,室見立華(りつか)である。Ixy 氏のイラストが表紙やカラーイラストに載っているのだが,うん,中高生の女の子にしか見えない。そしてどうしても『とらドラ!』の手乗りタイガーとダブってしまい,作中での立華のセリフも,私の脳内では釘宮理恵さんの声で再生されてしまう。

文章も,これがラノベか!という感じで,過去に目にした漫画やアニメの一シーンをもじったような光景を目に浮かべさせるような表現ばかりであり,もう,漫画化か,いっそアニメ化してくれたらと思うほどである。もし自分がアニメ業界の関係者で,資金も潤沢に持っていたとしたら,1クールだけでもいいから,この作品のアニメの制作指揮を執りたいものである。

内容については,ストーリーものである手前,ネタバレは最小限に抑えたいのでほとんど触れるつもりはないが,二つ感想を述べておく。

まず一つ目は,「働くって,大変だね」という,まあ,当たり障りのない感想である。現場で次々と発生する想定外のトラブルを,己のスキルや機転で辛くも乗り越えていく。その様は,緊急医療現場の医療スタッフや,窮地に陥った戦線の兵士さながらである。目まぐるしく変化する状況の中で,集中し,全身全霊をもって適応し,問題を解決していく。そんな暴れ馬みたいな現実に日々もまれ続けていたら,若くともすぐに消耗してしまうだろうが,戦いの場でこそ自分が生きていることを心の底から実感できる,という境地は,特に少年マンガではよく取り上げられる話ではある。このように,そうした境地に共感する癖がついているため,この作品をも好意的に受け入れることができるのだろう。

二つ目は,この作品に手を出した直接の動機ではあるが,SE,特にネットワークエンジニアの業務についてちょっぴり理解が進んだかな,ということである。といっても,自分がいま自宅で使用している屋内 WiFi でさえ,ルータのコンフィグ(設定)を自分で作ったわけでもなんでもなく,ただ単に電源を入れてケーブルをつないだらいつの間にか普通に使えていた,というド素人丸出しの体たらくなので,「SEの仕事,俺,わかっちゃったかも!」なんていうのはおこがましさを通り越して,犯罪の域に達しようとしているともいえるのであるが。

私はこの歳になるまで(この歳になっても)一般企業に勤めた経験がないため,疑似職業体験をさせてくれる,本作のような読み物は非常に貴重である。2010年にこの第一巻が刊行されてから,現在では第十二巻まで出ているようなので,ぼちぼち続きを楽しんでいこうと思っている。

ていうか,知り合いに SE を志望している就活生がいたらまっさきに薦めたいね,この本。
コメント
この記事をはてなブックマークに追加

【高校数学のツボ】Euclid の互除法には敵わないが。

2017-11-20 18:27:53 | mathematics
互いに素な2つの整数 13 と 21 に対して,不定方程式

13x+21y=1

の整数解 (x,y) を一組でいいから求めたい。

Euclid の互除法を利用すれば効率的かつ組織的に解が求められるが,ここではもう少し原始的なやり方を採用してみる。

大きい方の 21 を 13 で割ると余りは 8 である。すなわち,

21=13+8

である。この余り 8 の倍数のうち,13 で割った余りが 1 になるものを探す。

8×1=8 なので余り 8,
8×2=8+8=16=13+3 なので余り 3,
8×3=16+8=(13+3)+8=13+11 なので余り 11,
8×4=(13+11)+8=13+(11+8)=13+19=13+(13+6)=13×2+6 なので余り 6,
8×5=(13×2+6)+8=13×2+14=13×3+1 なので余り 1.

以上により,

21×5=(13+8)×5=13×5+8×5=13×5+(13×3+1)=13×8+1

となり,

-13×8+21×5=1,

すなわち,お題の方程式の解として (x,y)=(-8,5) があることが判明した。

与えられた2つの整数がたかだか2桁程度なら,このようにちょっとした手計算で不定方程式の解が一組求まる。順に倍数を求め,余りを求めるので,一回の計算ごとに足し算と引き算しか行わずに済む。そのため,計算しやすく感じられるのではないだろうか。

Euclid の互除法を利用する方法を理解し,身に着ける方が今後のためになるとは思うが,手っ取り早く解を求めたい場合にはこんな方法もあるのだと知っておいてもよいだろう。

といいつつ,数日前に同じ計算をしたはずの自分の計算メモを見てみると,なぜか x の値を -7 と間違えている・・・。

アハハハハハー。
コメント
この記事をはてなブックマークに追加

Prolog で3桁の2進数同士の加法と減法を行う。

2017-11-13 20:53:42 | 情報系
確か大学3年生の時だったか。授業で Prolog なるものを教わり,DEC-10 Prolog というのを大学の端末室でちょっとだけ触って遊んだ日々が懐かしく思い出される。

自分でも数行のプログラムを書いていろいろと試してみたが,肝心の Prolog 処理系の動作の仕組みが理解できておらず,プログラムが思い通りに動かないときに原因を突き止め,修正することができず,「デバッグの壁」の前で立ち往生するほかなかった。

それから今まで,ずっと Prolog に対する熱い想いは胸の奥底でくすぶり続けていたのだが,順列を生成するプログラムをコンパクトに記述できそうだと思い至り,また,和田秀男氏の単純計算機のシミュレータを Prolog で実装できないかという妄想も抱きつつ,今度こそある程度夢を形にしようと試行錯誤を始めている。

これは第5次くらいの Prolog マイブーム到来であるが,第3次ブームあたりで,Windows 上で動く無償の(!) Prolog 処理系 SWI-Prolog なるものがあることはすでに知っていた。

ネットで検索するとすぐにホームページが見つかり,無事 SWI-Prolog を自前の PC にインストールできたが,ブラウザ上で動くサービスがあることを知って驚いた。否,今はすでにそういう時代だということは,最近いろいろと同じような体験を繰り返して思い知っているはずであった。

それで,学部生当時も(ちょびっとだけ)お世話になった,

中島秀之,上田和紀共著,コンピュータ入門5 楽しいプログラミングII 記号の世界,岩波書店,1992年

という,コンピュータ初心者向けに丁寧に書かれたテキストの「4 足し算をプログラムしてみよう」をかじり読みして,どうにか 3 桁の2進数の加法と,2の補数を利用した減法のプログラムを作ることに成功した。

その本のさらに先をじっくり読めば,いろいろと融通の利くデータ構造としてのリストを使いこなせるようになりそうだが,かつてつまずいたのもその辺からだったこともあり,まだまだ勉強は進んでいない。

とりあえず,小文字 o を数字の 0,i を数字の 1 に見立てて,

add(bits(o,i,0),bits(o,i,i),X). (←最後のピリオドは必ずつける!)

とプロンプトに入力すると,

X=bits(i,o,i);
false

のように表示される「足し算」のプログラムを作った。ここで,X は bits(o,i,o)と bits(o,i,i) を足した結果である。
false というのは,これ以外に解 X がないというくらいの意味なので,気にしなくてよい。

なお,

add(X,bits(o,i,i),bits(i,o,i)).

と質問すると,

X=bits(o,i,o)

という答えが返ってくる。つまり,足し算の逆の引き算もある意味やってくれてしまうわけである。

そう考えると,add という術語だけで十分で,わざわざ引き算の術語を定義する必要はないかもしれないが,2の補数を作ってそれを加えるという伝統的なやり方で減法もできるようにした。それは add と同じように

subtract(bits(i,o,i),bits(o,i,i),X).

と質問すれば,101-011 の結果 010 に相当する

X=bits(o,i,o)

が返ってくるプログラムになっている。

下にそのプログラムを載せておく。これを例えば SWISH の画面の左のフレームにある Creat a Program というところの Program ボタンを押すと開くプログラム編集画面にコピペし,右下のフレームの右下隅の RUN ボタンを押してそのプログラムを読み込ませ,右下のテキスト入力欄に,上記のような質問文(くどいようだが,文末のピリオドを忘れずに。あと,小文字と大文字は区別して正しく記入のこと)を入力すれば,期待通りの結果が返ってくる。

ちなみに,このプログラムに至る前は,AND 演算を定義し,NOT 演算と合わせて OR 演算と XOR 演算を定義し,それらを組み合わせて全加算器を構成し,さらには全加算器を組み合わせて add を構成し・・・と,コンピュータの実際の構成と同じように組み立ててみたのだが,入力ミスをしたのだかなんだかわからないが,とにかくこちらの想定外の挙動が生じたので,現状のものへと変更した。おそらく繰り上がりの処理がまずかったのではないかと思い,初めから 3 つの 1 桁の2進数の和を,ベタな表として自前で書き込むという強硬手段に出たが,下手に小技を繰り出すよりもすっきりしていてよいのかもしれない。

さて,冒頭でも少し触れた「(超)単純計算機」に備える予定の 5 つの命令のうち,add と subtract のめどはついた。残りの load と store,jump minus もなんとかなると思うが,自己書き換えを許すプログラム内蔵方式を忠実に実現するにはどんなデータ構造がよいのか,まだ全く方針がつかめないままでいる。

--- プログラムの始まり ---
/* o は 0, i は 1 を表す。*/

/* ビット・ノットの定義 */
/* not(input,output). */
not(i,o).
not(o,i).

/* 1桁の数と一つ下の桁からの繰り上がりの和 */
/* add_3bits(input1,input2,carry,output). */
add_3bits(o,o,o,o,o).
add_3bits(o,i,o,o,i).
add_3bits(i,o,o,o,i).
add_3bits(i,i,o,i,o).
add_3bits(o,o,i,o,i).
add_3bits(o,i,i,i,o).
add_3bits(i,o,i,i,o).
add_3bits(i,i,i,i,i).

/* 3つの1桁の数の和を利用した,2つの1桁の数の和 */
add_2bits(X,Y,Z,W):-add_3bits(X,Y,o,Z,W).

/* 2組の3桁の2進数の和を求める */
/* add(input1,input2,input1+input2). */
add(bits(X_2,X_1,X_0),bits(Y_2,Y_1,Y_0),bits(Z_2,Z_1,Z_0)):-
add_2bits(X_0,Y_0,C_1,Z_0),
add_3bits(X_1,Y_1,C_1,C_2,Z_1),
add_3bits(X_2,Y_2,C_2,W,Z_2).

/* 2の補数 two's complement を求める。*/
/* not で各桁の o と i を反転し,その結果に i を加える。*/
/* complement_on_two(input,output). */
complement_on_two(bits(X_2,X_1,X_0),bits(Y_2,Y_1,Y_0)):-
not(X_2,Z_2),
not(X_1,Z_1),
not(X_0,Z_0),
add(bits(Z_2,Z_1,Z_0),bits(o,o,i),bits(Y_2,Y_1,Y_0)).

/* 2の補数を用いた減法 */
/* subtract(input1,input2,input1-input2). */
subtract(bits(X_2,X_1,X_0),bits(Y_2,Y_1,Y_0),bits(Z_2,Z_1,Z_0)):-
complement_on_two(bits(Y_2,Y_1,Y_0),bits(W_2,W_1,W_0)),
add(bits(X_2,X_1,X_0),bits(W_2,W_1,W_0),bits(Z_2,Z_1,Z_0)).

--- プログラムの終わり ---
コメント
この記事をはてなブックマークに追加

不規則動詞だったのか・・・。

2017-11-13 20:37:20 | 情報系
「2の補数」を英語でどう表現するのか知りたくてググってみた。

Wikipedia 英語版の解説を見たところ,two's complement というのが普通らしい。

2の補数を求める手続きとしては,桁ごとに 0 と 1 を反転させたものをまず求め,最後にそれに 1 を加えて完了というものしか知らなかったが,計算をしないで済ませる機械的な手続きもあることを学んだ。

2の補数を求めたいビット列の最下位 (Least Significant Bit, LSB) から調べ,初めて 1 が出てきたところまではそのままコピーし,それよりも上位の桁のビットは 0 と 1 を反転させればよい,というものである。

例えば 0000 には 1 が一つも出てこないので,まるまるコピーした 0000 が2の補数である。

0001 は最下位ビットがいきなり 1 だが,それはそのままコピーし,上位 3 桁は 0 を 1 に反転して 1111 とする。

1010 は,まず **10 とコピーしておいて,上位 2 桁を反転し 0110 とする。

おお,なぜかはわからないが確かにうまく行く!

このように 2 の補数の求め方に 2 つの流儀があることがわかったが,基本的にどちらが処理が速いわけでもないらしい。
そんな感じの記述に差し掛かった時,

can be sped up

という語句を目にした。

この sped とは,もしや・・・?!

これもさっそくググってみると,我々が日本語としてもよく使う「スピード」は名詞としての用法が主であるが,動詞としての意味もあり,その過去形および過去分詞形が sped だそうである。こんな馴染み深い英単語がまさかの不規則動詞だったとは・・・。今の今まで知らんかったわ~。
コメント (2)
この記事をはてなブックマークに追加

最近の世相。

2017-11-13 15:49:01 | 爺ネタ
11月に入り,世間はハロウィンムードから一気にクリスマスムードへとシフトした。

そんな中,11月11日は「ポッキーの日」だとばかり思いこんでいたのが,実は誤りで,正しくは「ポッキー&プリッツの日」だと知った。私のように勘違いしている人が多いため,この日プリッツは己を「ポッキーじゃないほう」と自虐的に表現したとのことである。

世の中のニュースはネットで見かけたものしか知らないのだが,兵庫県朝来市にある日本遺産「生野銀山」で,アツい超スーパー地下アイドル GINZAN BOYZ が活動していることを知った。GGGZPDS という彼らのデビューシングルの PV も観てみたが,妙にリアルな人物が混じっていると思ったら,SHICHO(市長)だそうだ。彼もアイドルの一員なのだろうか。

そして千葉は世界的に知られる存在となった。地球のある地質年代を「チバニアン」と呼ぶことが国際学会で認められる見通しだという。千葉の時代が来てしまったようである。

コメント
この記事をはてなブックマークに追加

順列の生成。(改改)

2017-11-06 22:38:32 | 情報系
これまでに到達したアイデアを元に,十進BASICで再帰的なプログラミングによる順列の生成にチャレンジしたものの,期待通りの結果が得られないままでいる。

そこで,少し気分を変えて,1 から 4 までの数字を重複を許して 4 つ並べた重複順列を生成するプログラムを作ってみた。

まずは FOR 文を入れ子にした,誰でもすぐ思いつく基本的なプログラムでうまくいくことを確かめた。

次に,順列の生成の手続きのアイデアと同様な方法で重複順列を生成しようとしたが,やはり失敗した。

しかし,この体験は無駄にならずに済みそうである。おかげでようやく考察が一歩前進しそうだからである。

私が考えた順列の生成手続きには,できた順列を出力した後,どの階層の手続きに戻るべきかの指示が欠けている。それが失敗の元凶のようだとようやく気付いた。

なお,二つの数字の入れ替えを軸とした順列の生成の基本姿勢は踏襲することにする。実際に我々が紙に順列を生成する樹形図などを描く際には,数字の入れ替えを行っているわけではなく,「ここまでに 3, 2, 4 は使ったから,ええと,あと 1 と 5 が残っているな」というように,既に使ってしまい,その後使えない数字とまだ使える数字を思い出して区別しながら作業するのが普通であろう。ただし,最後の2つの数字を並べる時だけは前後の数字の入れ替えを使っているはずである。リストの中の二つの文字の位置を入れ替える操作の方が,使える文字と使えない文字を区別するという,操作の許可・禁止の管理を行うより,実際には頭を悩ませずに済むので中高生にもおすすめの方法である。

解決までの見通しはそう悪くはないが,この文章を書きながらまとめようとしたら,ごちゃごちゃしてしまったので,もっと煮詰まってから改めて記事にしようと思う。

おそらく Prolog, Lisp, Haskell などのリスト処理に強い言語なら,簡単な練習問題程度なのだろうが・・・,うーん,難しい・・・。

あと,重複順列を生成しておいて,そのうち,数字や文字が重複していないものだけをふるい分ける方法もすぐ思いつく。効率の悪いやり方ではあるが,「文字が重複して使われているかどうかを判定する」手続きをきちんと書き出すのはとてもよい練習になるだろう。
コメント
この記事をはてなブックマークに追加

順列の生成。(改続)

2017-11-05 21:08:10 | 情報系
1 から 4 までの数字を並べたリスト [1,2,3,4] を並べ替え,24通りあるすべての順列を辞書式に(4桁の数値と見たときに小さい順に)生み出す手続きを考えよう。リストの左から i 番目の要素と j 番目の要素を入れ替える手続きを xch(i,j) と書く。これは

xch(2,4) [1,2,3,4] = [1,4,3,2]
xch(1,2) xch(2,4) [1,2,3,4] = xch(1,2) [1,4,3,2] = [4,1,3,2]

のように使う。xch(i,j) はリストの中の数字 i と j とを入れ替えるという意味ではないことを念のため注意しておく。

さて,並べ替えの際の一番上の階層の最初のリストは

[1,2,3,4]

[2,1,3,4]

[3,1,2,4]

[4,1,2,3]

である。うまい具合に

xch(1,2) [1,2,3,4] = [2,1,3,4]

xch(1,3) [2,1,3,4] = [3,1,2,4]

xch(1,4) [3,1,2,4] = [4,1,2,3]

となっているので,ぜひこの法則性を活かした手続きをしっかりと定式化したい,というのが本稿を含めた一連の記事の動機である。

始めに掲げた4つの見出しは,上から順に

xch(1,1) [1,2,3,4]

xch(1,2) xch(1,1) [1,2,3,4]

xch(1,3) xch(1,2) xch(1,1) [1,2,3,4]

xch(1,4) xch(1,3) xch(1,2) xch(1,1) [1,2,3,4]

と表すことができる。そこで,2つのリスト list と copy を用意して,まずは初期化

list ← [1,2,3,4]
copy ← []

を行う。これは,左のリストの内容を右のリストの内容で置き換えるという代入もしくはデータの更新の操作を意味している。

こうすると,

▼まず初期化

▽ i=1 から 4 まで
list ← xch(1,i) list
copy ← list
▽▽list の 2 番目から 4 番目までを並び替え,
list copy
を繰り返す

というように作業の流れを表現できる。

では,2 番目から 4 番目までを並び替える,一つ下の階層の下請け作業▽▽はどうなるだろうか。

いや,その前に,list や copy の役割をよく反省し,作業の順番も見直したくなってきた。

初期化は,むしろ

copy ← [1,2,3,4]
list ← []

としておいて,最後に処理していた copy ← list を最初におくことにする。

▽ i=1 から 4 まで
list ← copy
list ← xch(1,i) list
copy ← list
▽▽ list の 2 番目から 4 番目までを並び替え
を繰り返す

この方が流れがすっきりする。

ところが次の階層の▽▽の冒頭で
list ← copy
を行っても,list = copy のまま特に問題はないが,例えば次に
list ← xch(2,3) list
を行ってから
copy ← list
とされてしまっては,この階層で copy の内容が変更されてしまう。これでは困るので,copy に copy_1, copy_2, ... のように番号を振って,どの階層の見出しのリストなのか,区別できるようにしよう。

初期化は,list ← [1,2,3,4] とし,他のリストはすべて空リスト [] にする,という処理としておく。
copy ← list は,後ろの並び替えが終わった後にする方がよい気がしてきたので,そのバージョンに戻す。

▼初期化

▽ i=1 から 4 まで次を繰り返す。
list ← xch(1,i) list
copy_1 ← list
▽▽ list の 2 番目から 4 番目までを並び替え。
list ← copy_1

では,▽▽の中身を見ていこう。これは

▽▽ j=2 から 4 まで次を繰り返す。
list ← xch(2,j) list
copy_2 ← list
▽▽▽ list の 3 番目から 4 番目までを並び替え。
list ← copy_2

となる。

では,▽▽▽ の中身はというと,

▽▽▽ k=3 から 4 まで次を繰り返す。
list ← xch(3,k) list
copy_3 ← list
▽▽▽▽ list の 4 番目から 4 番目までを並び替え。
list ← copy_3

となる。▽▽▽▽ の作業は実質的に何も行わないため,copy_3 に list の内容を退避する必要はない。

階層 p の並べ替えの操作を perm(p) と書くことにすると,n 文字のリストについて,

p=n のとき,
perm(p) は list の出力(書き出し),

n-1>0 かつ p=n-1 のとき,
perm(p) は,
a(p)=p から a(p)=n まで
list ← xch(p,a(p)) list
perm(p+1)
を繰り返す,

それ以外のとき,
perm(p) は,
a(p)=p から a(p)=n まで
list ← xch(p,a(p)) list
copy_p ← list
 perm(p+1)
list ← copy_p
を繰り返す

となりそうである。

(仮称)十進 BASIC でこれを実現する際は,perm(p) を内部手続きとして定義することで,配列 list の受け渡しについて悩まなくて済むように思う。ただしその際は xch を行う繰り返しの添え字を変える必要があるかもしれないので,そのようなら FOR 文の代わりに IF 文を使おうと思う。
コメント
この記事をはてなブックマークに追加

順列の生成。(改)

2017-11-05 18:38:15 | 情報系
数字が 1 から 3 まで順に並んだリストを [1,2,3] とおく。

こうしたリストの先頭から数えて i 番目の数字を j 番目の数字と置き換える操作を xch(i,j) と記す。

あるリスト list の内容を書き出す操作を print list と記す。

では,リスト [1,2,3] の全順列を書き出す操作を考えよう。

xch(1,1) [1,2,3]
 xch(2,2) xch(1,1) [1,2,3]
  xch(3,3) xch(2,2) xch(1,1) [1,2,3]
   print xch(3,3) xch(2,2) xch(1,1) [1,2,3]

これで,まず [1,2,3] という元のリストがそのまま書き出される。

なお,xch(3,3) というのは無駄な気がするが,もとのリストが 1 文字だけの [1] であったとしても手続きの体裁をあまり変えずに済むよう,あえて入れてある。

次に出力されるべき [1,3,2] を生み出すには,
xch(1,1) [1,2,3]

の次に
 xch(2,3) xch(1,1) [1,2,3]

を実行しなければならない。つまり,続けて書くと
xch(1,1) [1,2,3]
 xch(2,2) xch(1,1) [1,2,3]
  xch(3,3) xch(2,2) xch(1,1) [1,2,3]
   print xch(3,3) xch(2,2) xch(1,1) [1,2,3]
 xch(2,3) xch(1,1) [1,2,3]
xch(3,3) xch(2,3) xch(1,1) [1,2,3]
print xch(3,3) xch(2,3) xch(1,1) [1,2,3]

となる。こう見てみると,次の階層の処理に入る前に list の内容をどこかに記録し,一連の作業を終えて元の階層に戻ったときに,記録した list の内容に戻してから次の処理に入るべきであることがわかる。

そこで,list1 の内容を list2 にコピーすることを list2 ← list1 と記すことにし,この記法を導入したうえで上の手続きを書き直してみよう。
なお,xch(3,3) xch(2,2) xch(1,1) [1,2,3] というのは見た目は長いが,どんなリストを扱っているかが一目瞭然であり,それは利点である。これは今導入したコピーの記法を使うと
list ← xch(1,1) [1,2,3]
list ← xch(2,2) list
list ← xch(3,3) list

のように記述できるが,簡潔ではあるものの,最後に得られた list の中身が xch(3,3) xch(2,2) xch(1,1) [1,2,3] であることを読み取るのはかえって難しくなる。

以上のことを念頭に置いて,上に記した手続きを書き直すと次のようになる。なお,セミコロン ; の後に,list や copy の更新結果も付してある。
list ← [1,2,3] ; list=[1,2,3]
copy ← [] ; list=[1,2,3], copy=[] (カラのリストを入れて初期化した。)

list ← xch(1,1) list ; list=[1,2,3], copy=[]
copy ← list ; list=[1,2,3], copy=[1,2,3]
 list ← xch(2,2) list ; list=[1,2,3], copy=[1,2,3]
  list ← xch(3,3) list ; list=[1,2,3], copy=[1,2,3]
   print list ; list=[1,2,3], copy=[1,2,3]
  list ← copy ; list=[1,2,3], copy=[1,2,3]
 list ← xch(2,3) list ; list=[1,3,2], copy=[1,2,3]
  list ← xch(3,3) llist ;  list=[1,3,2], copy=[1,2,3]
   print list ; list=[1,3,2], copy=[1,2,3]
  list ← copy ; list=[1,2,3], copy=[1,2,3]

これで list が初期の状態 [1,2,3] に戻ったので,処理を一番上の階層に戻し,xch(1,2) [1,2,3]=[2,1,3] の後ろの2つの数字を並び替えていく。
list ← xch(1,2) list ; list=[2,1,3], copy=[1,2,3]
copy ← list ; list=[2,1,3], copy=[2,1,3]
 list ← xch(2,2) list ; list=[2,1,3], copy=[2,1,3]
  list ← xch(3,3) list ; list=[2,1,3], copy=[2,1,3]
   print list ; list=[2,1,3], copy=[2,1,3]
  list ← copy ; list=[2,1,3], copy=[2,1,3]
 list ← xch(2,3) list ; list=[2,3,1], copy=[2,1,3]
  list ← xch(3,3) llist ;  list=[2,3,1], copy=[2,1,3]
   print list ; list=[2,3,1], copy=[2,1,3]
  list ← copy ; list=[2,1,3], copy=[2,1,3]

最後の1グループの手続きも記しておこう。
list ← xch(1,3) list ; list=[3,1,2], copy=[2,1,3]
copy ← list ; list=[3,1,2], copy=[3,1,2]
 list ← xch(2,2) list ; list=[3,1,2], copy=[3,1,2]
  list ← xch(3,3) list ; list=[3,1,2], copy=[3,1,2]
   print list ; list=[3,1,2], copy=[3,1,2]
  list ← copy ; list=[3,1,2], copy=[3,1,2]
 list ← xch(2,3) list ; list=[3,2,1], copy=[3,1,2]
  list ← xch(3,3) llist ;  list=[3,2,1], copy=[3,1,2]
   print list ; list=[3,2,1], copy=[3,1,2]
  list ← copy ; list=[3,1,2], copy=[3,1,2]

この最後の処理ではリスト copy は最初の下処理のみで必要で,その後に2回顔を出すが,それらは不要であるから,省いた方がすっきりする。とはいえ,同じ型の手続きをひとまとまりとして取り扱おうという下心があるので,xch(3,3) のように,あえてそのまま残してある。

さて,繰り返し出てくる全く同じ手続き
  list ← xch(3,3) llist ;  list=[3,2,1], copy=[3,1,2]
   print list ; list=[3,2,1], copy=[3,1,2]
  list ← copy ; list=[3,1,2], copy=[3,1,2]

を,perm(3) と名付けることにしよう。そうすると
list ← [1,2,3] ; list=[1,2,3]
copy ← [] ; list=[1,2,3], copy=[]

list ← xch(1,1) list ; list=[1,2,3], copy=[]
copy ← list ; list=[1,2,3], copy=[1,2,3]
 list ← xch(2,2) list ; list=[1,2,3], copy=[1,2,3]
  perm(3)
 list ← xch(2,3) list ; list=[1,3,2], copy=[1,2,3]
  perm(3)

list ← xch(1,2) list ; list=[2,1,3], copy=[1,2,3]
copy ← list ; list=[2,1,3], copy=[2,1,3]
 list ← xch(2,2) list ; list=[2,1,3], copy=[2,1,3]
  perm(3)
 list ← xch(2,3) list ; list=[2,3,1], copy=[2,1,3]
  perm(3)

list ← xch(1,3) list ; list=[3,1,2], copy=[2,1,3]
copy ← list ; list=[3,1,2], copy=[3,1,2]
 list ← xch(2,2) list ; list=[3,1,2], copy=[3,1,2]
  perm(3)
 list ← xch(2,3) list ; list=[3,2,1], copy=[3,1,2]
  perm(3)

となり,だいぶすっきりする。そして
 list ← xch(2,2) list
  perm(3)
 list ← xch(2,3) list
  perm(3)

の部分も perm(2) と書けば
list ← [1,2,3] ; list=[1,2,3]
copy ← [] ; list=[1,2,3], copy=[]

list ← xch(1,1) list ; list=[1,2,3], copy=[]
copy ← list ; list=[1,2,3], copy=[1,2,3]
 perm(2)

list ← xch(1,2) list ; list=[2,1,3], copy=[1,2,3]
copy ← list ; list=[2,1,3], copy=[2,1,3]
 perm(2)

list ← xch(1,3) list ; list=[3,1,2], copy=[2,1,3]
copy ← list ; list=[3,1,2], copy=[3,1,2]
 perm(2)

となる。最後に
list ← xch(1,1) list
copy ← list
 perm(2)

list ← xch(1,2) list
copy ← list
 perm(2)

list ← xch(1,3) list
copy ← list
 perm(2)

は,for 文を用いると
for i=1 to 3
 list ← xch(1,i) list
 copy ← list
 perm(2)
nedt i

と表せるが,これを perm(1) とまとめてしまえばよい。

こうして,perm(k) という手続きがはっきりしてきたわけである。

n 個の要素をもつリストのうち,k 番目から n 番目までの部分的なリストを並び替える手続きを perm(k) と書くことにすると,

k=n ならば perm(k) は,xch(n,n) を省いて,print list を実行したのち,list ← copy をする,

k<n ならば perm(k) は
<pre>
for i=k to n
list ← xch(k,i) list
copy ← list
perm(k+1)
nedt i

を実行する,ということにすればよさそうである。

ところが,copy ← list は perm(1) には入っているが,perm(2) には入っていなかった。
この操作をどう扱えばよいのかは,リストのサイズを一つ増やした [1,2,3,4] の順列を生成する手続きを考察することで手掛かりがつかめるかもしれない。

その考察については稿を改めることとしよう。
コメント
この記事をはてなブックマークに追加

単純計算機:プログラムの自己書き換えを利用して配列を扱う。

2017-11-04 23:13:14 | 情報系

A から E までの隣接する番地に格納された 5 つの数値の和を Sum として求めるプログラムは,和田秀男氏の単純計算機のアセンブリ言語では例えば次のようになる。


とりあえず,表を作るので力尽きたので,解説は・・・いつか・・・気が向いたときにでも・・・。


このブログで表 (table) を使うのはおそらくかなり久しぶりか,初めてかもしれない。ともかく,なんでか知らないけど無駄な空白がめっちゃ空くんだけど・・・。






























































































































番地ラベル命令参照値
00000: Start load A
00001:   add Sum
00010:   store Sum
00011:   load Count
00100:   subtract One
00101:   store Count
00110:   jump minus End
00111:   load Start
01000:   add One
01001:   store Start
01010:   jump Start
01011: End stop  
01100: One   1
01101: Count   4
01110: A   1
01111: B   2
10000: C   4
10001: D   8
10010: E   16
10011: Sum   0
コメント
この記事をはてなブックマークに追加

再帰的なプログラミングへの挑戦。

2017-11-03 19:42:50 | 情報系
二つの整数の最大公約数を求めるアルゴリズムとして古来有名な Euclid の互除法は同じ類の操作を繰り返す再帰的な手続きであることを何かで学んだ。

(仮称)十進BASICの作者である白石和夫氏の手になる入門テキスト「(仮称)十進 BASIC による JIS Full BASIC 入門」で,関数の再帰呼び出しの一例として取り上げられているが,まだその仕組みをよく理解していない。はやく再帰呼び出しを使いこなせるようになりたいものだ。

とりあえず自分なりに「内部手続き」という機能の使用例としてプログラムを作ってみた。
例として,45 と 108 の最大公約数 9 を求めさせている。

ともかく,こうした副プログラム(サブルーチン)を使えるようになると行える処理の幅がぐっと広がるし,再帰呼び出しや再帰手続きを使えるようになるとより洗練されたプログラムを書けるようになるので,そのような境地を目指したい。

100 LET a=45
110 LET b=108
120 CALL gcd(a,b)
130 PRINT b
140 SUB gcd(a,b)
150    LET r=MOD(a,b)
160    IF r>0 THEN
170       LET a=b
180       LET b=r
190       CALL gcd(a,b)
200    END IF
210 END SUB
220 END
コメント
この記事をはてなブックマークに追加