平成31年春期午後問8 ハフマン符号化のトレース4 再帰処理


平成31年春期午後問8。ハフマン符号化を扱った疑似言語の「プログラム2」のトレースです。構築されたハフマン木を使って文字を「0と1に符号化」するプログラムで再帰処理を用いています。

【再帰処理は自分で自分を呼出す 引数や変数に注意してトレース】

再帰処理は「自分で自分を呼出す」という特殊なプログラムですが、基本は変わりません。「呼出す元のプログラム」と「呼び出し先」のプログラムがあり、それぞれ引数や、変数の状況は異なります。扱うプログラムは同じでも、その中で使っている引数、変数の内容は異なる‥ここさえしっかり留意すれば再帰処理は複雑ではありません。

ここでは、状況設定として、問題文中に記載されている「図2」を使い、文字「D」を符号化することとします。なので、問題文中表5の「説明」から判断してkの初期値は「K=3」とします。

以上をもってトレースに入ります。ここでは、便宜上、プログラム「Encode」のプログラム名に番号を付けます。なので、最初に実行されるプログラムを「Encode1」とします。

1行目「Encode1」の引数は下記のとおりです。

2行目。「K=3」なので条件判定式「Parent[k] ≧ 0」は真となり、3行目に移動。3行目で新たに自分自身「Encode」を呼出しています。3行目Encodeの第1引数は「Parent[k]」となっています。ここでは。「K=3」なので「Parent[3]=4」、 3行目Encodeの第1引数は 「4」となります。

よって、「Encode1」から呼び出された「Encode2」の引数は下記のとおりです。

2行目。「k=4」なので「Parent[k] ≧ 0」は真となり、3行目に移動。3行目で新たに自分自身「Encode」を呼出しています。 そして、「Encode2」の時と同様に、「Encode3」が呼び出され、引数、変数の状況は下記の通りとなります。

プログラム「Encode3」の2行目。「k=5」なので「Parent ≧ 0」は真となり、3行目に移動。「Encode4」を呼出します。引数、変数の状況は下記のとおりです。

【再帰処理 自分自身の呼出しの後は自分自身に戻る】

プログラム「Encode4」の2行目。「k=6」なので、ここで初めて「Parent ≧ 0」が偽となり、処理は条件判断ブロックの外(8行目の次)に移動します。しかし、プログラム「Encode」に「8行目の次」がありませんので、ここで「Encode4」は終了となり、処理が「Encode3」の4行目に戻ります。

なお、処理が 「Encode3」の4行目に戻れば、引数、変数の状況も「Encode3」実行時の状態になりますので、下記の通りとなります。

ここから「Encode3」のトレースとなりますが、4行目も条件判定式となります。ここでは「K=5」となりますので真となり、処理は5行目に移ります。

なお、4行目の「Left[parent[k]] ≧ 0」は二重変数となっており、少々ややこしいので、「k=3」の場合の状況を下記に示します。

5行目で「0」が表示。ここでは出力先がディスプレイなのか、プリンタなのか‥等の記載がありませんので、「何らかの形で出力される」という程度の理解で構いません。実際、問題文中にも「出力先」に関する具体的な記載はありません。

5行目を終了すると、処理は7、8行目に移りますが、7、8行目は特に処理がないため、ここで「Encode3」が終了となります。

「Encode3」が終了 すると処理は「Encode2」に戻ります。引数、変数の状態は次の通りです。

「Encode2」の処理は4行目から再開され、4行目の条件判定式は下記の通り解析され、偽となります。

処理は6行目に移り「1」が表示されます。処理は7、8行目に移りますが、特に処理がありませんので、これで「Encode2」が終了。処理は「Encode1」に戻ります。

「Encode1」も「Encode2」同様に4行目から再開されます。引数、変数の状況、4行目条件判定文の解析は下記のとおりです。

4行目の条件判定式は偽となり、処理は6行目に移って「1」が表示されます。処理は7、8行目に移りますが、特に処理がありませんので「Encode1」の処理が終了。これで「プログラム2」のすべての処理が終了します。

ここまでで表示された符号は「0」「1」「1」。問題文中の図2のハフマン木(”D”の符号は”011″ちなる)と一致することがわかります。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です