Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

平成29年度春季基本情報午後問12

情報処理技術者試験 CASL

平成29年度春季 基本情報技術者試験(FE)の午後問題12(アセンブラ,CASL)は、64ビット符号なし整数の加算(副プログラムADD64)と副プログラムADD64を使用して、32ビット符号なし整数の乗算を行う副プログラムMUL32に関する問題でした。

設問1

空欄a

桁上がりのための処理を選択することになります。

空欄b

最下位の16ビット同士、第3位16ビット同士、第2位16ビット同士、最上位16ビット同士と加算処理が進んでいきますが、17行目の実行結果、ゼロフラグが1になれば、18行目でEXITにジャンプすることを考えると、最上位16ビットまで処理が進んだかを判定する処理を選ぶことになります。

設問2

行番号7の命令が2回目に実行されるときは、行番号11で(GR1)+3番地と(GR2)+3番地の加算をした結果#A684+#B759=#15DDDとなり、14行目でGR5が1となり、16行目でGR0が1になった状態で、7行目の処理が実行されることになります。#1+#2E0Cの結果を選択することになります。

設問3

2進数の掛け算では、以下のようになり、(A)の左シフトと加算で計算することができます。プログラム2の中で出てくるTEMPは、(A)をシフトした数を格納する役割を持っています。

    1011 (A)
   x1010 (B)
  ------
   10110 TEMP
 1011000 TEMP
 -------
 1101110

MUL32の中心的な処理は以下の所だと思います。TESTBITでは、かける数(GR0)の一番右側のビットが0の場合は、EXITLOOPへ、1の場合は、TEMPとGR3(乗算結果)を加算します。EXITLOOPでは、32ビット分の処理が終わっていればEXITへ、そうでなければTEMPを左に1ビットシフトする処理(ここでは2倍する処理で実現)が行われることになります。

TESTBIT  AND  GR0,=#0001
         JZE  EXITLOOP
         LD   GR1,GR3
         LAD  GR2,TEMP
         CALL ADD64
EXITLOOP CPL  GR5,=31
         JZE  EXIT
         ADDL GR5,=1
         LAD  GR1,TEMP
         空欄f
         CALL ADD64 
         LD   GR2,GR4    ; GR4に退避した値をGR2に復帰
         JUMP LOOP
EXIT     RPOP
         RET

平成29年度春季基本情報午後問8

Ruby 情報処理技術者試験

平成29年度春季 基本情報技術者試験(FE)の午後問題8は学生時代から何度となく出会ってきたダイクストラ法の問題でした。

h29h_fe_pm8.rb

Rubyだともっと効率よく書けそうですが、できるだけ疑似言語に近づけて書いてみました。

実行結果

$ ruby h29h_fe_pm8.rb
[6, 5, 2, 4, 1, 0, -1]
13

優先度付きキュー仕様版

現役東大医学部生が教える「最強の勉強法」

Book

自分が今から受験勉強するわけではないのですが、

  • 書店で平積みされていて気になった
  • どうやって東大医学部に合格できたのか興味があった
  • 生徒にフィードバックできる部分があるかも

と思って読んでみました。以下、自分が復習するためのメモです。

p72

ほとんどの成功者が、ある環境下での小さな成功体験の積み重ねで、「できる」という確信と自信に繋がり、それらが大きな成功をもたらしているのです。

p88

「高校生の勉強を自給換算にするといくらだと思いますか？」

p99

「高い壁を乗り越えた時、その壁はあなたを守る砦となる」

p108

目標設定の重要性として、「サイバネティクス理論」というものがあります。

p139

知覚動考（ともかくうごこう） 「知る→覚える→考えて→動く」ではなく、「知る→覚える→動いて→考える」

p190

寝る前の1時間で記憶が焼きつけられる

p275

作業興奮

p287

A man is a creature of habit 「人間は習慣の奴隷である」

p289

「コンフォートゾーン(Comfort Zone)からの脱出」

p319

「ユースレス・タイム(Useless Time)」をいかになくすことができるか？

p320

「ポモドーロテクニック」

p340

「思考→行動→習慣→結果」

現役東大医学部生が教える「最強の勉強法」

現役東大医学部生が教える「最強の勉強法」

ナミヤ雑貨店の奇蹟

Book

本の帯に「東野作品史上もっとも泣ける感動作！」とあり、最近、東野作品を読んでなかったので読んでみようと手にとった本です。

点と点が繋がって線となる瞬間に、ゾクゾクっと感動が湧き上がってくる作品だったと思います。読み終えたあと、書名で検索してみたのですが、今年、映画化されていたんですね。つくづく情報に疎いなと思います。

ナミヤ雑貨店の奇蹟 (角川文庫)

ナミヤ雑貨店の奇蹟 (角川文庫)

平成29年度秋季基本情報午後問12

情報処理技術者試験 CASL

平成29年度秋期 基本情報技術者試験(FE)の午後問題12(アセンブラ, CASL)は、連続する2語から成るビット列αの中から、別のビット列βと一致する部分ビット列を検索し、βと同じ長さの別のビット列γで置き換えるプログラムに関する問題でした。

設問1

空欄a

12 LP      LD   GR7,GR4
13         AND  GR7,GR6
14         (空欄a)
15 JZE     FOUND        ; 一致あり

12行目で、検索対象の文字列をGR7に取り込み、13行目でビット列βの長さ分GR7に取り出します。 15行目で、ZF(ゼロフラグ)が1の場合、つまり14行目の演算結果が0の場合FOUND処理にジャンプするので、GR7とビット列β(GR2)が一致すれば0、一致しなければ非0になるような演算を選ぶことになります。

空欄b

18         SLL  GR4,1   ; αを1ビット左シフト
19         SLL  GR5,1
20         (空欄b)
21         JUMP LP
22 NEXT    OR   GR4,=#0001
23         JUMP LP

18行目から23行目は2語からなるビット列αを次の検索処理のためにお膳立てをする処理です。まず、18行目で1語目を左へ1ビット論理シフトし、同様に19行目で2語目も左へ1ビット論理シフトしています。このとき、オーバフローが発生すると、1語目の最後尾に1を追加する処理が必要になりますが、その処理がNEXT部ということになります。よって、OF（オーバーフローフラグ）が1のとき、NEXTへジャンプするという処理を選ぶことになります。

設問2

4         LD   GR6,=#FFFF ; マスク作成
5         SRL  GR6,0,GR3
6         XOR  GR6,=#FFFF

GR3には、検索対象ビット列βのビット長nが格納してあります。例えば、GR3が5のとき、5行目の処理でGR6は5ビット論理右シフトするので#07FFとなり、6行目で#F800となります。

LD       GR6,=#8000

のあとに、GR6を#F800とするには、GR6を4ビット算術右シフトすればよいことになります。

設問3

空欄c

29 ONL2    (空欄c)
30         SUBA GR2,GR3   ; GR2 <- p-16
31         LAD  GR1,1,GR1 ; 操作対象を2語目にして、
32         CALL S1        ; 2語目の処理

ONL2の処理にやってくるときは、置き換え対象ビット列γが2語目にあるときです。例えば、置き換えたいビット位置の先頭が24の場合、4行目の処理でGR2が24、10行目の処理でGR3が16ですから、

11         SUBA GR3,GR2

の処理を経てGR3には16-24=-8が格納された状態で、29行目の処理に移ることになります。30行目の処理でGR2には、2語目の左から何ビット目かという値を格納するには、空欄cでGR2に0を設定しておけばよいということになります。

空欄d

35 S1      SRL GR4,0,GR2  ; γの調整
36         SRL GR6,0,GR2  ; マスクの調整
37 S2      LD  GR2,0,GR1  ; 操作対象語の取出し
38         XOR GR6,=#FFFF
39         AND GR2,GR6
40         (空欄d)
41         ST  GR2,0,GR1

置き換え対象ビット列が8ビット目から始まるとき、GR2に8が設定されていることになります。 今、

  • GR4にはγとして#A000
  • GR6に、#0FFF

とすると、35行目でGR4が#00A0となり、36行目でGR6が#00F0になります。38行目でXOR演算を行うことにより、GR6が#FF0Fとなります。GR2には、37行目の処理により置き換え前のビット列が格納されていますので、GR2=#CCCCとすると、39行目のAND演算により、GR2は#CC0Cになります。これで置き換えたいビット部分列を0に置き換えることができましたので、40行目で、γを調整したもの(GR4)をセットすればよいことになります。

設問4

β:11011は、1語目の14,15ビット目から2語目の0〜2ビット目にマッチします。23行目は2語目用マスクの調整処理であり、2語目は0〜2ビット目にマッチすることから、#E000となります。

感想

10数年ぶりに基本情報技術者試験のCASLの問題を解いてみました。プログラムを読む前に自分だったらこうやって解くだろうから、こんな処理をやっている所があるはずだなどと考えてから解いてみると面白いですね。ビット遊びをしているような感覚で楽しく取り組めました。

高校生に基本情報技術者試験をクリアさせようと考えたとき、表計算, C, Javaなどの選択肢がありますが、CASLの命令語数の少なさを考えると、やはりメリットはあるのかなと思います。今年の授業でCASLを取り入れてみましたが、各命令の動作を覚えて終わりというのではなく、過去問演習ができるくらいまで取り組めるといいなと思います。

平成29年度秋季応用情報午後問3

Ruby 情報処理技術者試験

平成29年度秋期 応用情報技術者試験(AP)の午後問題3はナップザック問題でした。動的計画法を学習する際のテッパン問題ですね。

h29a_ap_pm3.rb

実行結果

$ ruby h29a_ap_pm3.rb
 C Bを選んだとき
価値合計 = 15

平成29年度秋季基本情報午後問9

C 情報処理技術者試験

平成29年度秋期 基本情報技術者試験(FE)の午後問題9は文字列の中から、回文(palindroe)を探して表示する問題でした。

設問1(h29h_fe_pm9_1.c)

実行結果

$ gcc h29h_fe_pm9_1.c && ./a.out
bc0cb
Bc0Cb
B!c0 Cb
bc0cb

設問2, 3(h29h_fe_pm9_2.c)

実行結果

$ gcc h29h_fe_pm9_2.c && ./a.out
Madam, I'm Adam

感想

例えば"abcdcba"は回文であるかを判定するプログラムは簡単に作れますが、文字列の中から、回文を探して表示するというケースは今まで体験したことがなく、どうやって作成するのか興味深かったので、張り切って取り組んでみました。きっとこんなことをやっているだろうという予測ができるので解くことはできますが、設問2は、find_last_charの第1引数がith+1であることに注意してdとeを解答しなければならなかったりと慎重に取り組まないといけないなと感じました。