この年度は、 実習ではなく講義を行ないました。
1997 年 4 月 12 日（土）
「計算機基礎論３Ｂ」
（旧カリキュラム「電子計算機基礎論実習」の読みかえ）
上記の科目を本年度に履習しようと思う者で学籍番号の上二ケタが
93 以下である者は、4 月 18 日（金）または 25 日（金）の授業
終了直後に私に申し出て指示を受けること。これを怠った場合は
単位を認定しない。
岩瀬順一
1997-07-18 (金)
１９９７年度計算機基礎論３Ｂレポート問題
次の１〜５についてレポートしてください。また，私および来年度の授業担当者に聞い
てほしい感想・要望などのある方は書いてください。
１．適当な（十進表記の）自然数を選び，それを二進および十六進で表記せよ。あまり
自明でない数を選ぶことが望ましい。
２．適当な（十進表記の）有限小数を選び，それを二進で表記せよ。ただし，答えが有
限小数にならないものを選ぶこと。
３．適当な自然数を選び，Newton 法を使ってその平方根を有効数字８桁程度の精度で
求めよ。平方数でない数を選ぶこと。途中の加減乗除は電卓を使って計算して構わな
い。
４．トランプのカード一組から一つのスート（スペードとかハートとか）のカードのみ
を取り出し，よく切って並べることで，1 から 13 までの自然数が一回ずつ現われる数
列が得られる。（ここでは A, J, Q, K はそれぞれ 1, 11, 12, 13 とみなす。）デー
タを一つも持たない二分木にその順でデータを加えてゆく過程をレポートせよ。
※ 授業で言い忘れたかも知れないが，データを一つも持たない二分木に一つめのデ
ータを加えるときは，それが root になる。
５．トランプのカード一組に，適当な順序を定義する。例えば A < 2 < 3 < ... < 10
< J < Q < K とし，同じ数のカードの間では スペード < ハート < クラブ < ダイヤ
とする。ジョーカーは最大とみなす。（もちろん，これと違う順序でもよい。）
シェルソートは，1 < h < H なる自然数の組 h, H に対し，まず H おきに整列し，次に
h おきに整列すると，結果は H おきに整列されたままであるので最後に 1 おきに整列
する際の計算量が少なくて済む，という原理に基づいた整列アルゴリズムだった。
授業で説明したことも参考にして各自適当に h と H を選び，よく切ったカード一組に
対してシェルソートを実行し，その過程をレポートせよ。特に，h おきに整列した後も
H おきに整列されているかどうか，および 1 おきに整列する際の計算量に注目するこ
と。
※ 各ステップの整列は挿入法で行なうと授業では説明したが，H おきおよび h おき
に整列する段階では「めのこ」で整列しても構わない。ただし最後の 1 おきに整
列する段階では必ず挿入法を用いて，計算量を調べてみること。
※ 実際にやってみると，「こんな手間をかけるより普通に整列したほうが速いや」
と思うかも知れないが，それはトランプのカードの特殊性のためである。始めか
ら出てくるデータの種類が決まっていて，しかもそれらが一度ずつ出てくるとわ
かっている場合には，それに応じた方法を工夫したほうが速い。
提出は，今年度後期の「解析学Ａ１」または「解析学Ａ２」のうち，私が担当する第一
回目または第二回目の授業の終了直後とします。これらの科目を履習しない者に限り，
数学科事務室の私の書類受けに入れても構いません。その提出方法による提出は後期の
授業日の第６日目の１６時３０分までとします。
返却も「解析学Ａ１」または「解析学Ａ２」の授業終了直後に行なう予定です。追って
掲示します。これらの科目を履習しないなどの理由でその時間に出席できず，かつレポ
ートの返却を希望する者は，レポートと一緒に返却用の封筒（住所氏名を書き，必要な
額の切手を貼っておくこと）を提出してください。そうすればそれに入れて郵送しま
す。
岩瀬順一
問題５の二つ目の注の「始めから出てくるデータの種類が決まっていて」 は「初めから〜」の誤り。