基本情報技術者試験 - 平成30年秋期(科目B) - 問8

問題

 次のプログラムの説明及びプログラムを読んで,設問1~3に答えよ。

 整数式を受け取って,その値を返すプログラムである。例えば,例1に示す整数式を受け取ると,その値50を返す。
   例1: 2×(34-(5+67)÷8)

〔プログラムの説明〕
(1) 整数式は,文字の列で与えられる。整数式は,次のもので構成される。
・符号のない数字0~9の並び
・演算子: +,-,×,÷
・括弧: (,)
(2) 引数 Expression[] で整数式を,引数 ExpLen で整数式の文字数を,それぞれ受け取る。
(3) プログラム中の破線で囲んだ解析処理の部分では,受け取った整数式を解析し,計算に必要な情報を配列及び変数に設定する。
(4) プログラム中の破線で囲んだ計算処理の部分では,(3)で設定した情報を用いて,整数式の値を計算する。整数式の値は,Value[0] に得られる。
(5) 各配列の添字は,0から始まる。各配列の要素数は,十分に大きいものとする。
(6) 受け取った整数式に誤りはないものとする。また,計算の過程で,あふれやゼロ除算は発生しないものとする。

〔プログラム〕
○整数型関数: compute(文字型: Expression[], 整数型: ExpLen)
○文字型: Operator[100]
○整数型: OpCnt, Priority[100], Value[100]
○文字型: chr
○整数型: i, ip, nest
 解析処理(詳細は〔プログラム(解析処理の部分)〕に示す)
 計算処理(詳細は〔プログラム(計算処理の部分)〕に示す)
・return Value[0]

〔プログラム(解析処理の部分)の説明〕
(1) Expression[] で渡された整数式を解析し,計算に必要な情報を配列 Operator[],Priority[],Value[] 及び変数 OpCnt に設定する。関数 int() は,引数の数字が表す値を整数型で返す。
(2) 例1の整数式について,プログラム(解析処理の部分)を実行した直後の各配列及び変数の状態を,図1に示す。



〔プログラム(計算処理の部分)の説明〕
(1) 整数式の値を計算していく。図1に示す各配列及び変数の状態から,プログラム(計算処理の部分)の最外側の繰返しを1回実行した直後の各配列及び変数の状態を,図2に示す。


設問1  プログラム(解析処理の部分)に関する次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。

 プログラム(解析処理の部分)の行①~④で用いている定数について考察する。
 まず,行③及び④の処理では,定数として10を用いているが,この定数は10である必要はない。このプログラムにおいては,定数が [ a ] であれば常に正しい演算順序が保証される。
 また,行①及び②の処理では,定数として1及び2を用いているが,次に示すように書き換えることが可能である。ここで, priLow 及び priHigh は整数の定数を表し,その値は priLow<priHigh とする。
 ①→ ・Priority[OpCnt] ← nest + priLow
 ②→ ・Priority[OpCnt] ← nest + priHigh
 このように表現したとき,行③及び④の処理では,nest の値を増減する定数が [ b ] のときに限り正しい演算順序が保証されることになる。

aに関する解答群
ア1以上
イ2以上
ウ11以下
エ12以下

bに関する解答群
アpriHigh以上
イpriHigh+1以上
ウpriHigh-priLow以上
エpriHigh-priLow+1以上

設問2  優先順位の等しい演算子が複数個含まれている整数式の,演算の実行順序について考察する。プログラムに関する次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。ここで,c1~c3に入れる答えは,cに関する解答群の中から組合せとして正しいものを選ぶものとする。

 プログラム(計算処理の部分)では,優先順位の等しい演算子が複数個含まれている場合,演算を左から順に実行するようになっている。このプログラムでは,演算を左から順に実行するか右から順に実行するかは,行 [ c1 ] の内容が [ c2 ] か [ c3 ] かで決まる。
 演算の実行順序によって,計算結果が異なることがある。例えば,次の四つの整数式のケースを考える。

 ケース1:(12+3+1)×4×2
 ケース2:(12+3+1)÷4÷2
 ケース3:(12-3-1)×4×2
 ケース4:(12-3-1)÷4÷2

これらのケースのうち,演算を左から実行しても右から実行しても,プログラムによる計算結果が等しくなるのは,ケース [ d ] である。

cに関する解答群
c1c2c3
ア⑤・ip ← 0・ip ← OpCnt - 1
イ⑥i: 1, i<OpCnt, 1i: OpCnt, i>0, -1
ウ⑥i: 1, i<OpCnt, 1i: OpCnt-1, i>0, -1
エ⑦Priority[ip]<Priority[i]Priority[ip]≦Priority[i]

dに関する解答群
ア1
イ1及び2
ウ1及び3
エ1及び4

設問3  プログラムの動作に関する次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。

 符号付き整定数(数字の並びの先頭に符号+又は-を付けた定数)を含む整数式を考える。符号付き整定数は,例2のように括弧で囲んで記述する。ただし,符号付き整定数の直前の文字が演算子でない場合は,例3のように括弧で囲まなくてもよい。
  例2: (+2)×((-3)+(-4))
  例3: +2×(-3+(-4))
 符号付き整定数を含む整数式2×(-1)についてプログラム(解析処理の部分)を実行した結果を,図3に示す。
このように,符号付き整定数を含む整数式を受け取ったとき,プログラムは e 。



eに関する解答群
ア整数式が符号付き整定数で始まる場合に,正しい値を返さない
イ整数式中に符号-の付いた符号付き整定数がある場合に,正しい値を返さない
ウ整数式中に二つ以上の符号付き整定数が含まれる場合に,正しい値を返さない
エ正しい値を返す

f,gに関する解答群
ア-1
イ0
ウ1
エ2

正解と解説

正解設問1 (a)イ (b)エ 設問2 (c)エ (d)ア 設問3 (e)エ (f)イ (g)エ 
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム

解説

■ 問題の概要

 「2×(34−(5+67)÷8)」のような整数式を文字列として受け取り,その値を計算するプログラムです。処理は二つの部分に分かれています。
  • 解析処理:式を1文字ずつ読み,数値をValue[]に,演算子をOperator[]に,その演算子の優先順位をPriority[]に格納します。
  • 計算処理:Priority[]が最も大きい演算子を探してその計算を行い,配列を詰める,という作業を演算子がなくなるまで繰り返します。
 優先順位の付け方がこのプログラムの要点です。+と−には「nest+1」,×と÷には「nest+2」を与えます。nestは括弧の深さを表し,「(」で10増え,「)」で10減ります。例えば,括弧の外の×は2,1重の括弧の中の−は11,2重の括弧の中の+は21になります。数値が大きいほど先に計算されます。

■ 設問1 空欄a 正解:「イ」

 括弧の中の計算は,括弧の外のどの演算子よりも先に行う必要があります。最も不利なのは,括弧の中の+や−(nest+1)と,括弧の外の×や÷(nest+2)を比べる場合です。
 括弧で増える定数をkとすると,括弧の中の+の優先順位はk+1,括弧の外の×は2です。k+1>2,つまりk≧2であれば,括弧の中が必ず先に計算されます。
 よって,定数は「2以上」であればよく,「イ」が正解です。

■ 設問1 空欄b 正解:「エ」

 1と2をpriLowとpriHighに置き換えて,同じように考えます。括弧の中の最も低い優先順位はk+priLow,括弧の外の最も高い優先順位はpriHighです。
 k+priLow>priHigh,つまりk>priHigh−priLowとなればよいです。kは整数なので,「k≧priHigh−priLow+1」と表せます。よって「エ」が正解です。
 設問1の空欄aは,この式にpriLow=1,priHigh=2を入れた場合(k≧2)に当たります。

■ 設問2 空欄c 正解:「エ」

 計算処理では,行⑦の「Priority[ip] < Priority[i]」で,優先順位が最も大きい演算子の位置ipを探しています。演算子は左から順に調べられます。
 「<」の場合,優先順位が等しい演算子が後から出てきてもipは更新されないので,一番左のものが選ばれます。つまり,左から順に計算します。
 これを「≦」に変えると,等しい演算子が出てくるたびにipが更新されるので,一番右のものが選ばれ,右から順に計算することになります。
 よって,行⑦の内容が「<」か「≦」かで決まる,という「エ」が正解です。

■ 設問2 空欄d 正解:「ア」

 各ケースを,左から計算した場合と右から計算した場合で比べます。なお,÷は整数の商を求めます。
  • ケース1:括弧の中は16で,左からなら16×4×2=128,右からなら16×(4×2)=128です。足し算と掛け算は順番を変えても結果が同じなので,等しくなります。
  • ケース2:左からなら(16÷4)÷2=2,右からなら16÷(4÷2)=8で,異なります。
  • ケース3:括弧の中が,左からなら(12−3)−1=8,右からなら12−(3−1)=10で,異なります。
  • ケース4:ケース3と同様に括弧の中から結果が異なります。
 結果が等しくなるのはケース1だけなので,「ア」が正解です。

■ 設問3 空欄f,g 正解:f「イ」,g「エ」

 「2×(−1)」を解析処理で1文字ずつ処理します。
  • 「2」:Value[0]=2
  • 「×」:Operator[0]に×,Priority[0]=2,OpCntが1になり,Value[1]=0
  • 「(」:nestが10になります
  • 「−」:Operator[1]に−,Priority[1]=11,OpCntが2になり,Value[2]=0
  • 「1」:Value[2]=1
  • 「)」:nestが0に戻ります
 符号の−の前には数字がないので,Value[1]は0のままです。よって空欄fは「イ」(0),OpCntは2なので空欄gは「エ」(2)です。

■ 設問3 空欄e 正解:「エ」

 設問3の解析結果を見ると,「(−1)」は「0−1」として扱われています。符号の付いた数は,前に0が補われて「0+数」や「0−数」の形になります。
 計算すると,まず括弧の中の0−1=−1(優先順位11)が行われ,次に2×(−1)=−2(優先順位2)となり,正しい値が得られます。
 例3のように式の先頭が「+2×…」の場合も,「0+2×…」となって×が先に計算されるので,値は正しくなります。符号付き整定数が複数あっても同じです。
 したがって,プログラムは正しい値を返すので,「エ」が正解です。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる