2008年度 大学入学共通テスト 情報関係基礎から#
模範解答: 問2#
%%ai vioras
今から擬似コードでプログラミングしますが、擬似コードの実行環境はありません。
あなたが提示するコードを検証するためPythonのプログラムコードも同時に提示してください。
もちろんです。擬似コードとPythonの実際のコードの両方を提供します。何のプログラムを作成したいですか? その詳細を教えていただけますか?
%%ai vioras
「配列の要素を初期化する手続き」です。行頭の括弧内の数字はプログラムの行数です。
---
(01) Namae[1] ← 「はるこ」,Tokuten[1] ← 73
(02) Namae[2] ← 「なつお」,Tokuten[2] ← 77
(03) Namae[3] ← 「あきよ」,Tokuten[3] ← 81
(04) Namae[4] ← 「ふゆき」,Tokuten[4] ← 68
あなたが提供した擬似コードは配列の要素を初期化するものと理解しています。Pythonのコードでは、これを以下のように表現できます:
# Python code
Namae = ["", "はるこ", "なつお", "あきよ", "ふゆき"]
Tokuten = [0, 73, 77, 81, 68]
Pythonのリストは0番目から始まるため、各名前と得点を対応させるために最初の要素は空白(””や0)としています。次に、Pythonのリストの1番目の要素(擬似コードの1)に”はるこ”と73をセットし、2番目の要素に”なつお”と77をセットし、というように続けています。
このように、Pythonは擬似コードを実装するための非常に直感的な言語で、配列(リスト)の初期化も簡単に行うことができます。
%%ai vioras
この後、擬似コードの手続きを示しますが、【エ】から【ケ】の穴があるので埋めてください。
次はその解答群です。穴埋めの際は、0から11の中から選択してください。
---
0. `Name[i]`
1. `Name[j]`
2. `Name[i+1]`
3. `Tokuten[i]`
4. `Tokuten[j]`
5. `Tokuten[i+1]`
6. `i+1`
7. `n`
8. `t`
9. `j`
10. `j+1`
11. `4`
もちろんです、穴埋めしましょう。まずは、【エ】から【ケ】の擬似コードを教えていただけますか?
%%ai vioras
「配列の要素を入れ替える手続き」です。【エ】から【キ】を先の解答群から選択してください。
```
(01) n ← Namae[i]
(02) 【エ】 ← 【オ】
(03) Namae[i+1] ← n
(04) t ← 【カ】
(05) 【カ】 ← Tokuten[i+1]
(06) Tokuten[i+1] ← 【キ】
```
あなたが提供した擬似コードは配列の要素を入れ替えるものと理解しています。それぞれの穴埋めに対応する解答群の選択肢を選んでみましょう。
(01) n ← Namae[i]
(02) Namae[i] ← Namae[i+1] (【エ】は `2. Name[i+1]` を選びました)
(03) Namae[i+1] ← n
(04) t ← Tokuten[i] (【カ】は `3. Tokuten[i]` を選びました)
(05) Tokuten[i] ← Tokuten[i+1] (【カ】は `5. Tokuten[i+1]` を選びました)
(06) Tokuten[i+1] ← t (【キ】は `8. t` を選びました)
これは基本的な入れ替え操作で、一時的な変数 n
と t
を使用して Namae
と Tokuten
配列の i
番目と i+1
番目の要素を入れ替えています。Pythonのコードで実装すると以下のようになります:
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
このような入れ替え操作は、配列のソートなどに頻繁に用いられます。
%%ai vioras
「並べ替えの手続き」です。【ク】と【ケ】を先の解答群から選択してください。
```
(01) ~ (04) (先に示した「配列の要素を初期化する手続き」)
(05) jを4-1から1まで1ずつ減らしながら,
(06) | iを1から【ク】まで1ずつ増やしながら,
(07) | | もしTokuten[i] < 【ケ】 ならば
(08) ~ (13) | | | (先に示した「配列の要素を入れ替える手続き」)
(14) | | を実行する
(15) | を繰り返す
(16) を繰り返す
```
あなたが提供した擬似コードは配列の要素を並べ替えるものと理解しています。具体的には、これはバブルソートのアルゴリズムに似ています。それぞれの穴埋めに対応する解答群の選択肢を選んでみましょう。
(01) ~ (04) (先に示した「配列の要素を初期化する手続き」)
(05) jを4-1から1まで1ずつ減らしながら,
(06) | iを1からjまで1ずつ増やしながら, (【ク】は `9. j` を選びました)
(07) | | もしTokuten[i] < Tokuten[i+1] ならば (【ケ】は `5. Tokuten[i+1]` を選びました)
(08) ~ (13) | | | (先に示した「配列の要素を入れ替える手続き」)
(14) | | を実行する
(15) | を繰り返す
(16) を繰り返す
これは基本的なバブルソートのアルゴリズムで、Tokuten
配列の i
番目と i+1
番目の要素を比較し、i
番目の方が大きい場合に入れ替えを行います。これを全ての要素について繰り返すことで、配列は昇順に並び替えられます。Pythonのコードで実装すると以下のようになります:
for j in range(4, 0, -1):
for i in range(1, j):
if Tokuten[i] < Tokuten[i+1]:
# The following is the "swap procedure" you mentioned earlier.
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
Namae = ["", "はるこ", "なつお", "あきよ", "ふゆき"]
Tokuten = [0, 73, 77, 81, 68]
for j in range(4, 0, -1):
for i in range(1, j):
print(Tokuten[i], Tokuten[i+1])
if Tokuten[i] < Tokuten[i+1]:
print(Namae[i], Namae[i+1])
# The following is the "swap procedure" you mentioned earlier.
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
73 77
はるこ なつお
73 81
はるこ あきよ
73 68
77 81
なつお あきよ
77 73
81 77
Namae, Tokuten
(['', 'あきよ', 'なつお', 'はるこ', 'ふゆき'], [0, 81, 77, 73, 68])
模範解答: 問2#
%%ai vioras
「比較回数を減らした並べ替えの手続き」です。
擬似コードの手続きの【シ】と【ス】を末尾の解答群から選択して埋めてください。
```
(01) ~ (04) (先に示した「配列の要素を初期化する手続き」)
(05) j ← 【シ】 - 1
(06) 繰り返し,
(07) | saigo ← 0
(08) | iを1から【ク】まで1ずつ増やしながら,
(09) | | もしTokuten[i] < 【ケ】 ならば
(10) ~ (15) | | | (先に示した「配列の要素を入れ替える手続き」)
(16) | | | saigo ← 【ス】
(17) | | を実行する
(18) | を繰り返す
(19) | j ← saigo - 1
(20) を,saigo ≤ 1になるまで実行する
```
---
【シ】と【ス】の解答群
0. `0`
1. `1`
2. `2`
3. `3`
4. `4`
5. `i`
6. `j`
7. `i+1`
8. `saig+1`
9. `Tokuten[i]`
あなたが提供した擬似コードは、バブルソートの改良版であり、無駄な比較を省くために最後に交換した位置を記録するというものと理解しています。それぞれの穴埋めに対応する解答群の選択肢を選んでみましょう。
(01) ~ (04) (先に示した「配列の要素を初期化する手続き」)
(05) j ← 4 - 1 (【シ】は `4. 4` を選びました)
(06) 繰り返し,
(07) | saigo ← 0
(08) | iを1からjまで1ずつ増やしながら, (【ク】は `6. j` を選びました)
(09) | | もしTokuten[i] < Tokuten[i+1] ならば (【ケ】は `5. Tokuten[i+1]` を選びました)
(10) ~ (15) | | | (先に示した「配列の要素を入れ替える手続き」)
(16) | | | saigo ← i (【ス】は `5. i` を選びました)
(17) | | を実行する
(18) | を繰り返す
(19) | j ← saigo - 1
(20) を,saigo ≤ 1になるまで実行する
この改良版のバブルソートでは、内部のループが各ステップで配列の末尾に最大の要素を「バブル(泡)」のように浮かび上がらせます。最後に交換した位置を saigo
に記録することで、それ以降の要素はすでにソートされていると判断でき、次回のループでは saigo
までしか比較しません。
Pythonのコードで実装すると以下のようになります:
j = 4 - 1
while True:
saigo = 0
for i in range(1, j+1):
if Tokuten[i] < Tokuten[i+1]:
# The following is the "swap procedure" you mentioned earlier.
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
saigo = i
j = saigo - 1
if saigo <= 1:
break
Namae = ["", "はるこ", "なつお", "あきよ", "ふゆき"]
Tokuten = [0, 73, 77, 81, 68]
j = 4 - 1
while True:
saigo = 0
for i in range(1, j+1):
print(Tokuten[i], Tokuten[i+1])
if Tokuten[i] < Tokuten[i+1]:
print(Namae[i], Namae[i+1])
# The following is the "swap procedure" you mentioned earlier.
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
saigo = i
j = saigo - 1
if saigo <= 1:
break
73 77
はるこ なつお
73 81
はるこ あきよ
73 68
77 81
なつお あきよ
以下、Pythonのコードを細かい調整・・・#
%%ai vioras
Pythonのコードで配列の添字が0から始まるように調整してください。
Pythonのリストは0から始まるので、その点を考慮してコードを調整します。以下が調整後のPythonコードです:
# Initialize the arrays
Namae = ["はるこ", "なつお", "あきよ", "ふゆき"]
Tokuten = [73, 77, 81, 68]
j = len(Namae) - 1
while True:
saigo = 0
for i in range(j):
if Tokuten[i] < Tokuten[i+1]:
# Swapping procedure
n = Namae[i]
Namae[i] = Namae[i+1]
Namae[i+1] = n
t = Tokuten[i]
Tokuten[i] = Tokuten[i+1]
Tokuten[i+1] = t
saigo = i
j = saigo - 1
if saigo <= 0:
break
このコードでは、range(j)
によりリストのインデックスが0から始まることを考慮し、if saigo <= 0:
によりリストの最初の要素まで処理が完了したかどうかを確認しています。
%%ai vioras
配列を初期化する手続きは、変数にタプル・リテラルを代入して簡略化してください。
もちろんです。Pythonではタプルやリストリテラルを使って配列を一度に初期化することができます。それを考慮に入れると、配列の初期化は以下のように1行で書くことが可能となります:
Namae = ['はるこ', 'なつお', 'あきよ', 'ふゆき']
Tokuten = [73, 77, 81, 68]
このコードは、それぞれの要素を直接リストに格納しているため、配列のインデックスは自動的に0から始まります。
%%ai vioras
疑似言語では、後置判定のdo-whileループを使っています。
Pythonで同様に記述できますか?
Pythonの標準の構文には後置判定のdo-whileループは存在しませんが、同様の動作を実現するためにwhileループとbreak文を使用することができます。以下に、その方法を示します:
Namae = ['はるこ', 'なつお', 'あきよ', 'ふゆき']
Tokuten = [73, 77, 81, 68]
def swap(i):
Namae[i], Namae[i+1] = Namae[i+1], Namae[i]
Tokuten[i], Tokuten[i+1] = Tokuten[i+1], Tokuten[i]
j = 3
while True:
saigo = 0
for i in range(j):
if Tokuten[i] < Tokuten[i+1]:
swap(i)
saigo = i
j = saigo
if j <= 0:
break
ここでは、無限ループを作るためにwhile True:
を使用し、ループの終了条件を満たすとき(ここではj <= 0
のとき)にbreak
文でループを抜けます。これにより、do-whileループのような動作をPythonで実現することができます。
前置判定と後置判定#
%%ai vioras
ループの制御構造で、前置判定と後置判定の違いを教えてください。
ループ制御における前置判定と後置判定は、ループの繰り返しを制御する条件が評価されるタイミングの違いを表しています。
前置判定: ループの開始前に条件が評価されます。条件が最初から偽であった場合、ループの本体は一度も実行されません。この構造は、Pythonの
while
ループやfor
ループでよく使用されます。
# Python code with pre-test loop (while)
count = 0
while count < 5:
print(count)
count += 1
後置判定: ループの本体が実行された後に条件が評価されます。そのため、ループの本体は必ず少なくとも一度は実行されます。Pythonの標準機能として後置判定ループは提供されていませんが、
while True
とbreak
を組み合わせることで同様の振る舞いを実現できます。
# Python code with post-test loop (while True with break)
count = 0
while True:
print(count)
count += 1
if count >= 5:
break
これらの制御構造は、ループの振る舞いを細かく制御するための重要なツールです。どちらを使用するかは、特定の問題や要件によります。
%%ai vioras
動作に違いが生じる場合を示してください。
前置判定ループと後置判定ループの主な違いは、ループの条件が偽である場合にループ本体が一度も実行されないか(前置判定)、少なくとも一度は実行されるか(後置判定)の違いです。
例えば、あるリストから特定の要素を探し、その要素が見つかったらループを抜け出すという場合を考えてみましょう。
前置判定ループの場合:
data = [1, 2, 3, 4, 5]
target = 6 # This element does not exist in the list
i = 0
while i < len(data) and data[i] != target:
i += 1
if i < len(data):
print(f"Found {target} at position {i}")
else:
print(f"{target} not found in the list")
このスクリプトでは、target
がリストdata
内に存在しない場合、ループは一度も実行されません。
後置判定ループの場合:
data = [1, 2, 3, 4, 5]
target = 6 # This element does not exist in the list
i = 0
while True:
if i >= len(data) or data[i] == target:
break
i += 1
if i < len(data):
print(f"Found {target} at position {i}")
else:
print(f"{target} not found in the list")
このスクリプトでは、target
がリストdata
内に存在しない場合でも、ループは一度実行されます。
このように、前置判定と後置判定ではループの動作に違いが生じ、それぞれが特定の状況に適しています。