アルゴリズム (全80問中14問目)
No.14
三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数ƒ()を呼び出して終了した後のBの状態はどれか。ここで，スタックが，[a1 a2，…，an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2，…，an-1，an]で表す。
ƒ(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
ƒ()を呼び出す。
Cからpopした値をBにpushする。
}
}
ƒ(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
ƒ()を呼び出す。
Cからpopした値をBにpushする。
}
}
出典：平成31年春期 問6
- [1，2，3，1，2，3]
- [1，2，3，3，2，1]
- [3，2，1，1，2，3]
- [3，2，1，3，2，1]
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
スタックは後入れ先出しのデータ構造で、"pop"と"push"の2つの命令によってデータを操作します。
＜プログラム開始＞
A[1，2，3] B[1，2，3] C[1，2，3]
〔ƒ() 呼び出し1回目〕
Aからpopした値をCにpushする。Aから一番右の"3"が取り出され、Cの一番右に追加される(以下、取出位置と追加位置は同様)。
A[1，2] B[1，2，3] C[1，2，3，3]
〔ƒ() 呼び出し2回目〕
Aからpopした"2"をCにpushする。
A[1] B[1，2，3] C[1，2，3，3，2]
〔ƒ() 呼び出し3回目〕
Aからpopした"1"をCにpushする。
A[] B[1，2，3] C[1，2，3，3，2，1]
〔ƒ() 呼び出し4回目〕
Aが空なので何もしない
〔ƒ() 呼び出し3回目の続き〕
Cからpopした"1"をBにpushする。
A[] B[1，2，3，1] C[1，2，3，3，2]
//ƒ() 3回目終了
〔ƒ() 呼び出し2回目の続き〕
Cからpopした"2"をBにpushする。
A[] B[1，2，3，1，2] C[1，2，3，3]
//ƒ() 2回目終了
〔ƒ() 呼び出し1回目の続き〕
Cからpopした"3"をBにpushする。
A[] B[1，2，3，1，2，3] C[1，2，3]
//ƒ() 1回目終了
＜プログラム終了＞
関数ƒ()が終了した後のBの状態は[1，2，3，1，2，3]になっています。したがって「ア」が正解です。
- pop
- スタックからデータを取り出す
- push
- スタックにデータを追加する
＜プログラム開始＞
A[1，2，3] B[1，2，3] C[1，2，3]
〔ƒ() 呼び出し1回目〕
Aからpopした値をCにpushする。Aから一番右の"3"が取り出され、Cの一番右に追加される(以下、取出位置と追加位置は同様)。
A[1，2] B[1，2，3] C[1，2，3，3]
〔ƒ() 呼び出し2回目〕
Aからpopした"2"をCにpushする。
A[1] B[1，2，3] C[1，2，3，3，2]
〔ƒ() 呼び出し3回目〕
Aからpopした"1"をCにpushする。
A[] B[1，2，3] C[1，2，3，3，2，1]
〔ƒ() 呼び出し4回目〕
Aが空なので何もしない
〔ƒ() 呼び出し3回目の続き〕
Cからpopした"1"をBにpushする。
A[] B[1，2，3，1] C[1，2，3，3，2]
//ƒ() 3回目終了
〔ƒ() 呼び出し2回目の続き〕
Cからpopした"2"をBにpushする。
A[] B[1，2，3，1，2] C[1，2，3，3]
//ƒ() 2回目終了
〔ƒ() 呼び出し1回目の続き〕
Cからpopした"3"をBにpushする。
A[] B[1，2，3，1，2，3] C[1，2，3]
//ƒ() 1回目終了
＜プログラム終了＞
関数ƒ()が終了した後のBの状態は[1，2，3，1，2，3]になっています。したがって「ア」が正解です。