24.4.5. 反復処理

条件分岐と反復処理を行うと，さまざまな計算が実現できます． 1から10までの和を，反復で計算してみましょう．

枠組み #

指定された条件を満たすまで，反復する処理を次のように，実現します．

計算をする
条件を満たしているならば，プログラムを終了する
そうでなければ（条件を満たしていないならば）１の計算に戻る

反復処理の例 “1から10までの和” #

反復処理を使ったプログラムの例として， “1から10までの和” を計算するプログラムを考えてみます．教科書図8.2 （下の図の右側）のプログラムを， Littele Man Computer (LMC) 用に書き直したものが，下図の左側部分です．

各命令の対応関係は以下のようになっています．

LDA	ADD	STA	SUB	BRZ	BRA	OUT	HLT
load	add	store	subtract	jumpzero	jump	write	halt

LMCの命令セットの詳細は，別ページにまとめられています．
24.4.9. 参考: 命令セット

プログラムの入力 #

以下のプログラムをプログラム領域にコピー＆ペーストして，“Submit"ボタンを押して，メインメモリに読み込んでください．

LDA 11
ADD 12
STA 11
LDA 12
SUB 13
STA 12
BRZ 8
BRA 0
LDA 11
OUT
HLT
DAT 0
DAT 10
DAT 1

“STEP"によるプログラムの実行 #

ここでも"STEP"をクリックして1命令ずつ実行して行きます．最初の状態では"PROGRAM COUNTER"と"ACCUMURATOR"の値は，ともに「0」となっています．

LDA 11 #

0番地の命令は “511 (LDA 11)” です．メインメモリの11番地の値「0」を “ACCUMULATOR” に読み込みます．

ADD 12 #

1番地の命令は “112 (ADD 12)” です．“ACCUMULATOR” の値である「0」にメインメモリの12番地の値「10」を加えて，結果の値「10」を “ACCUMULATOR” に格納します．

STA 11 #

2番地の命令は “311 (STA 11)” です．“ACCUMULATOR” の値「10」をメインメモリの11番地に書き出します．

LDA 12 #

3番地の命令は “512 (LDA 12)” です．メインメモリの12番地の値「10」を “ACCUMULATOR” に読み込みます．

SUB 13 #

4番地の命令は “213 (SUB 13)” です．“ACCUMULATOR” の値「10」からメインメモリの13番地の値「１」を引き，結果の値「9」を “ACCUMULATOR” に格納します．

STA 12 #

5番地の命令は “312 (STA 12)” です．“ACCUMULATOR” の値「9」をメインメモリの12番地に書き出します．

BRZ 8 #

6番地の命令は “708 (BRZ 8)” です．“ACCUMULATOR” の値がゼロだった場合，“PROGRAM COUNTER” の値を「8」にして，プログラムの実行を8番地にジャンプします．この段階では “ACCUMULATOR” の値は「9」であり，ゼロではないので “PROGRAM COUNTER"の値は1増えて「7」になります．

BRA 0 #

7番地の命令は “600 (BRA 0)” です．無条件で “PROGRAM COUNTER” の値を「0」にして，プログラムの実行を0番地にジャンプします．

(2回目) 0番地からのプログラム実行 #

ここでは"PROGRAM COUNTER"の値は「0」となっています．ただしメインメモリの11番地と12番地の値が，最初の状態とは異なっていることに注意する必要があります．

LDA 11 #

0番地の命令は “511 (LDA 11)” です．メインメモリの11番地の値「10」を “ACCUMULATOR” に読み込みます．

ADD 12 #

1番地の命令は “112 (ADD 12)” です．“ACCUMULATOR” の値である「10」にメインメモリの12番地の値「9」を加えて，結果の値「19」を “ACCUMULATOR” に格納します．

STA 11 #

2番地の命令は “311 (STA 11)” です．“ACCUMULATOR” の値「19」をメインメモリの11番地に書き出します．

LDA 12 #

3番地の命令は “512 (LDA 12)” です．メインメモリの12番地の値「9」を “ACCUMULATOR” に読み込みます．

SUB 13 #

4番地の命令は “213 (SUB 13)” です．“ACCUMULATOR” の値「9」からメインメモリの13番地の値「１」を引き，結果の値「8」を “ACCUMULATOR” に格納します．

STA 12 #

5番地の命令は “312 (STA 12)” です．“ACCUMULATOR” の値「8」をメインメモリの12番地に書き出します．

BRZ 8 #

6番地の命令は “708 (BRZ 8)” です．“ACCUMULATOR” の値がゼロだった場合，“PROGRAM COUNTER” の値を「8」にして，プログラムの実行を8番地にジャンプします．この段階では “ACCUMULATOR” の値は「8」であり，ゼロではないので “PROGRAM COUNTER"の値は1増えて「7」になります．

実行が進むにしたがって，5～7の操作によって12番地の値が1つずつ小さくなり，ゼロになるときが訪れます．

BRA 0 #

7番地の命令は “600 (BRA 0)” です．無条件で “PROGRAM COUNTER” の値を「0」にして，プログラムの実行を0番地にジャンプします．

反復のまとめ #

2回目の反復が終わった際には，以下のようになります．

反復の過程で，メインメモリ上の11～13番地の値は，以下のようになることがわかります．

13番地の値は，12番地の値を減らす数値で，常に「1」である
12番地の値は，11番地の値に加算される数値で，最初「10」であり，1回毎に「1」だけ減っていく
11番地の値は，12番地の値の加算を反復した数値で，最初は「0」であり，0 + 10 + 9 + 8 + … となる

この反復が終わるのは，「8. “BRZ 8"による条件分岐」で"ACCUMULATOR"の値が「0」(ゼロ)になる場合で，プログラムの実行は8番地にジャンプします．その直前で「7. “STA 12” の実行」を実行していることから，12番地の値が「0」となる状態であり，その際に11番地は「55」になっています．

反復終了後 #

8番地の命令は “511 (LDA 11)” です．メインメモリの11番地の値「55」を “ACCUMULATOR” に読み込みます．

“OUT” による出力 #

9番地の命令は “902 (OUT)” です．“ACCUMULATOR” の値「55」を出力します．

“HLT” によるプログラムの終了 #

10番地の命令は “000 (HLT)” です．HLT命令によって，プログラムが終了します．“OUTPUT"には1から10までの和である「55」が表示されています.

プログラムの終了時には，以下のようになります.