基本情報技術者試験〔科目B〕演習　2022年サンプル問題　問4（文法問題）

2025年1月7日 13:44

問4（文法問題）
　次のプログラム中のa ～ cに入れる正しい答えの組み合わせを、解答群の中から選べ。
　関数gcdは、引数で与えられた二つの正の整数num1とnum2の最大公約数を、次の(1) ～ (3) の性質を利用して求める。
(1) num1 と num2 が等しいとき、num1 と num2 の最大公約数num1 である。
(2) num1 がnum2　より大きいとき、num1 とnum2 の最大公約数は、（num1 – num2）とnum2の最大公約数と等しい。
(3) num2がnum1より大きいとき、num1とnum2の最大公約数は、（num2 – num1）とnum1の最大公約数と等しい。

〔プログラム〕
1: 〇整数型：gcd （整数型：num1, 整数型：num2）
2: 　整数型： x ← num1
3: 　整数型： y ← num2
4: 　a
5: 　if ( b )
6: 　x ← x - y
7: 　else
8: 　y ← y - x
9: 　endif
10: 　c
11: 　return x

解答：a: while (x ≠ y) , b: x ＞ y , c: endwhile

・本プログラムの構成

ループ (a)
- 最大公約数を求める処理は、x と y が等しくなるまで続ける必要がある。
  - 条件：(1) の性質より、x ≠ y の間は処理を繰り返す。
- よって、a の正しい答えは while (x ≠ y) である。
条件分岐 (b)
- x と y の大小関係に基づき、処理を分ける必要がある。
  - 条件：(2) の性質より、x > y の場合、x ← x - y を実行する。
  - 条件：(3) の性質より、それ以外（つまり y > x）の場合、y ← y - x を実行する。
- よって、b の正しい答えは x > y である。
ループの終了 (c)
- while 文が使用されているため、その終了を明示する必要がある。
- よって、c の正しい答えは endwhile である。

解答の根拠
最大公約数を求める際、ユークリッドの互除法の考え方を用いており、このアルゴリズムは正確にその性質を反映している。

・ユークリッドの互除法とは
ユークリッドの互除法（Euclidean Algorithm）は、2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率的に求めるアルゴリズムである。
アルゴリズムの基本概念
ユークリッドの互除法は次の性質を利用する：

性質 1
GCD(a,b)=GCD(b,amod b)

（ここで、a mod b はa を b で割った余り）

この性質により、2つの数 a と b の最大公約数は、b と a を b で割った余りの最大公約数と等しい。
性質 2
剰余が 0 になったとき、その時点での除数 b が最大公約数。
- このプロセスを繰り返すことで、剰余が 0 になるまで計算を進める。

アルゴリズムの手順
以下の手順を繰り返します：

a を b で割り、余り r を求める。
（例: a ÷ b = q（商）, 余り r = a – q × b）
aを b に、b を rに置き換える。
r=0になったとき、b が最大公約数。

・Javaで本問題をコーディング
public class GCDCalculator {
// ユークリッドの互除法を用いて最大公約数を計算
public static int gcd(int num1, int num2) {
while (num1 != num2) {
if (num1 > num2) {
num1 -= num2;
} else {
num2 -= num1;
}
}
return num1;
}

// テストコード
public static void main(String[] args) {
// テストケース
int[][] testCases = {
{252, 105}, // 結果: 21
{48, 18}, // 結果: 6
{101, 103}, // 結果: 1
{56, 98} // 結果: 14
};

// テスト実行
for (int[] testCase : testCases) {
int num1 = testCase[0];
int num2 = testCase[1];
int result = gcd(num1, num2);
System.out.println("GCD of " + num1 + " and " + num2 + " is: " + result);
}
}
}
・Pythonで本問題をコーディング
def gcd(num1, num2):
"""
ユークリッドの互除法を用いて最大公約数を計算
"""
while num1 != num2:
if num1 > num2:
num1 -= num2
else:
num2 -= num1
return num1

# テストコード
if __name__ == "__main__":
# テストケース
test_cases = [
(252, 105), # 結果: 21
(48, 18), # 結果: 6
(101, 103), # 結果: 1
(56, 98) # 結果: 14
]

# テスト実行
for num1, num2 in test_cases:
result = gcd(num1, num2)
print(f"GCD of {num1} and {num2} is: {result}")

補足
Chat-GPTによる解説
背景
ユークリッドの互除法は、紀元前から知られる効率的なアルゴリズムで、現代の計算機科学や数学においても基礎的かつ重要な役割を果たしています。特に、アルゴリズムの基礎学習や、効率的な計算の理解を深める際に取り上げられることが多いテーマです。
本問題では、擬似コードを完成させる形でアルゴリズムの理解を確認するとともに、最大公約数を求める問題を通じて、以下のポイントを学ぶ意図があります：

アルゴリズムの論理的構造。
条件分岐やループの使い方。
数学的性質のプログラムへの適用方法。

目的

アルゴリズムの学習
- 数学的な定義（最大公約数）を効率的に解くアルゴリズムの考え方を理解する。
- 条件分岐とループの活用法を習得する。
問題解決能力の向上
- 問題文で与えられた条件を適切に読み取り、それをコードで表現する力を養う。
擬似コードから実装への架け橋
- 擬似言語を基に、具体的なプログラムを作成する力を育成。
- 言語に依存しないアルゴリズムの汎用性を学ぶ。

結果
本問題を解くことで、以下の成果が得られます：

アルゴリズムの理解
- ユークリッドの互除法の仕組みを具体的に理解し、手計算での演習を通じてその有用性を確認。
擬似コードの実装力向上
- 擬似言語で表現されたロジックを、実際のプログラミング言語（JavaやPythonなど）で実装するスキルが向上。
プログラムのデバッグ能力
- 条件分岐やループの正しい使い方を学び、正しいコードを効率的に書けるようになる。
数学とプログラミングの融合
- 数学的な概念（最大公約数）をアルゴリズムに落とし込む力を養う。

応用事例

暗号理論
- RSA暗号などの公開鍵暗号方式では、最大公約数の計算を通じて素因数分解や互いに素（coprime）の概念が使用される。
数値計算
- 数学や物理学で扱う分数の計算や単位変換の際に、最大公約数を使った簡略化が必要。
プログラム最適化
- ループや条件分岐の効率的な設計の学習を通じて、より効率的なアルゴリズム設計の基礎を学ぶ。
分数演算の実装
- 分数計算において、分母と分子を最大公約数で簡略化する際に使用。
アルゴリズム学習の導入
- 基本的なアルゴリズムの理解から始め、より高度なアルゴリズムやデータ構造の学習につなげる。

まとめ
本問題は、ユークリッドの互除法を題材に、数学的な考え方とプログラミングの融合を図る教育的な課題です。このアルゴリズムは単に最大公約数を計算するだけでなく、効率的な計算方法やその応用可能性を学ぶうえで非常に重要です。本問題を通じて得られた知識やスキルは、暗号理論や数値計算など多くの実世界の問題に活用できます。

以上。

基本情報技術者試験〔科目B〕演習 2022年サンプル問題 問4（文法問題）

いいなと思ったら応援しよう！

基本情報技術者試験〔科目B〕演習　2022年サンプル問題　問4（文法問題）