新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題9をJavaにしてみました
2023 年 4 月からIPA (独立行政法人情報処理推進機構)の基本情報技術者試験の制度が変更されました。
ここでは、「基本情報技術者試験 科目 B のサンプル問題20問バージョン」の中から、アルゴリズムとプログラミングの問題を取り上げ、Javaのソースコードを示します。
新人エンジニア研修に参加されている皆様の参考になれば幸いです。
【Javaプログラム】
public class Q9 {
// Javaの配列が0から始まるため先頭要素に{}(空の配列)を追加しています。
static int[][] tree = { {}, { 2, 3 }, { 4, 5 }, { 6, 7 }, { 8, 9 }, { 10, 11 }, { 12, 13 }, { 14 }, {}, {}, {}, {},
{}, {}, {}, {} };
//本問で問われている手続
static void order(int n) {
if (tree[n].length == 2) {
order(tree[n][0]);
System.out.print(n + " ");
order(tree[n][1]);
} else if (tree[n].length == 1) {
order(tree[n][0]);
System.out.print(n + " ");
} else {
System.out.print(n + " ");
}
}
//以下はテスト
public static void main(String[] args) {
order(1);
}
}
【結果】
8 4 9 2 10 5 11 1 12 6 13 3 14 7 |
【プログラムの解説】
このプログラムは、二分木を表現し、その木をインオーダー順(中間順)で巡回して出力します。
インオーダー順とは、まず左部分木、次にルート、そして最後に右部分木を訪れるという巡回方法です。
以下がプログラムの概要です。
tree
という二次元配列を使用して二分木を表現しています。
この二分木の各要素は、その要素の子ノードを表すインデックスの配列として格納されます。
例えば、tree[1]
は {2, 3}
です。これは、ノード1の子ノードがノード2とノード3であることを意味します。
order
という再帰的なメソッドを使用して、インオーダー順序で二分木を巡回します。
インオーダー順序では、左の子ノード、親ノード、右の子ノードの順に処理を行います。order
メソッドは、引数n
に与えられたノードから巡回を開始し、再帰的に子ノードを巡回します。
main
メソッドでは、ノード1(木のルート)からインオーダー順序で巡回を開始します。
このプログラムを実行すると、二分木のインオーダー順序での巡回結果である 8 4 9 2 10 5 11 1 12 6 13 3 14 7
が出力されます。
投稿者プロフィール
-
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します!
この記事に間違い等ありましたらぜひお知らせください。
最新の投稿
- 新人エンジニア研修講師2024年12月25日新人エンジニア研修使える「アイスブレイク集」 45連発
- 新人エンジニア研修講師2024年12月25日新人エンジニア研修で教えたい「段落と改行、字下げ、行空けのルール」
- 新人エンジニア研修講師2024年12月25日フリーランスの講師の方向け 開業届とは?
- 新人エンジニア研修講師2024年12月25日フリーランスの講師の方向け 廃業届とは?