基本情報技術者試験の科目BをJavaとPythonのプログラムで考える　No.14

基本情報技術者試験で出題されるプログラム言語が疑似言語に変更されましたね。合格に向けて学習を進めるにおいては、やはり普段から使っているプログラム言語に置き換えて考えてみたいですよね。
このサイトでは、IPA情報処理推進機構で公開されている科目Bのプログラミングの問題を中心に、疑似言語をJavaとPythonのコードに置き換えて解説していきます。
１日１問の解説を発信していく予定です。基本情報技術者試験の合格を目指されている方のお役に立てれば幸いです。

---

基本情報技術者試験 科目 B サンプル問題（2022年12月公開）

https://www.ipa.go.jp/shiken/syllabus/henkou/2022/ssf7ph000000h5tb-att/fe_kamoku_b_set_sample_qs.pdf

問４　最大公約数を求める

このプログラムは最大公約数をユークリッドの互除法という手法で求めています。

 最大公約数とは？

最大公約数とは、2つの数に共通する約数の中で一番大きい数のことです。たとえば、12と18の最大公約数は6です。なぜなら、12と18の両方に共通する約数（1, 2, 3, 6）の中で一番大きいのが6だからです。

ユークリッドの互除法とは？

2つの数の最大公約数を簡単に見つける方法です。この方法では、次のステップを繰り返します：

① 大きい方の数を小さい方の数で割ります。余りを求めます。
② 小さい方の数と余りを比べます。今度は、小さい方の数を「大きい方」とし、余りを「小さい方」とします。
③ 余りが0になるまで、この手順を繰り返します。
④ 最後に余りが0になったときの「小さい方の数」が最大公約数です。

では、24と36の最大公約数を求めてみましょう。
・ まず、36を24で割ります。36 ÷ 24 = 1 余り 12
・ 次に、24を12で割ります。24 ÷ 12 = 2 余り 0

余りが0になったので、このときの「小さい方の数」は12です。したがって、24と36の最大公約数は12です。

１．Javaのコードで考えてみよう

package kamokuB;

public class R4_Sample04 {

	// 最大公約数を求めるメソッド
	static int gcd(int num1, int num2) {
		int x = num1;
		int y = num2;
		
		while( x != y) { // ２つの値が同じになるまで繰り返す
			if(x > y) {
				x = x - y;
			}else {
				y = y - x;
			}
		}
		return x;
	}
	
	public static void main(String[] args) {
		
		// ユークリッドの互除法で最大公約数を求める
		int a = 36;
		int b = 60;
		
		// 36と60の最大公約数12を求める
		System.out.printf("%dと%dの最大公約数＝%d",a,b,gcd(a,b));
		
	}
}

２．Pythonのコードで考えてみよう

# 2022年12月公開問題4

# 最大公約数を求めるメソッド
def gcd(num1, num2):
    x = num1
    y = num2
    
    while x != y:  # 2つの値が同じになるまで繰り返す
        if x > y:
            x = x - y
        else:
            y = y - x
            
    return x

# ユークリッドの互除法で最大公約数を求める
a = 36
b = 60
    
# 36と60の最大公約数12を求める
print(f"{a}と{b}の最大公約数＝{gcd(a, b)}")

いかがでしょうか。
ユークリッド互除法は最大公約数を求める有名な手法ですので、その手順を理解しておきましょう。