【アルゴリズム入門 Q035】最大値の探索

こんにちは。ECF代表のヒガです。

本記事では初心者向けアルゴリズムの演習問題を紹介しています。日頃のプログラミング学習にご活用ください。

はじめに

アルゴリズムとは、コンピューターに行わせる計算手順のことです。自在にプログラムを作るには、プログラム言語の文法の知識とともにアルゴリズムの考え方を身につけることが必要になります。

アルゴリズム技法習得の肝は「繰り返し」の活用です。この連載では、簡単な題材で繰り返しを使うアルゴリズムの基本パターンを練習していきます。

演習問題の一覧や勉強スタイルについてのアドバイスはこちらからどうぞ。

【プログラミング初心者向け】アルゴリズム入門演習問題集〜繰り返しをマスターしよう！

こんにちは。ECF代表のヒガです。プログラミング初心者向けアルゴリズム演習問題の連載記事まとめです。日頃のプログラミング学習、講義、研修等での演習にご活用ください。「繰り返しアルゴリズム」をマスターしようアルゴリズムとは、コンピューターに行...

Q035 最大値の探索

配列に格納された数値データのうち、最大値とその格納位置（添字）を表示させてください。なお、同じ値が複数の配列要素に格納されている場合は、添字が小さい方を表示させてください。

初期値として {68, 55, 72, 93, 87} を使って整数型（Javaではint型）配列を準備した場合の実行例は次のとおりです。

配列で最大値「93」と、その要素の添字「3」が表示されます。

ヒント

もちろんQ034の最小値の探索が参考となります。というより、ほぼ同じです。「何が違えば最大値が求まるか」という視点で考えるといいでしょう。

【アルゴリズム入門 Q034】最小値の探索

こんにちは。ECF代表のヒガです。本記事では初心者向けアルゴリズムの演習問題を紹介しています。日頃のプログラミング学習にご活用ください。はじめにアルゴリズムとは、コンピューターに行わせる計算手順のことです。自在にプログラムを作るには、プログ...

解答例と解説

考え方

あえてQ034の最小値の探索と同じ説明をしてみます。しっかり理解されている方は読み飛ばしOKです。逆にまだピンときていない方はもう一度じっくりと読んでみましょう。

まずは今回の主題である最大値の探索ループを考えてみましょう。ループということで、まず最初に「何を繰り返す」かを考えます。

人力で配列を前から順に見ながら最大値を探すことを想像してみましょう。具体的に {6, 4, 8, 2, 10} という配列データで考えます（より理解しやすくするために、実行例とは違う例にしてみました）。

1番目の要素「6」はとりあえず開始時の暫定最大値とします。
「6」と2番目の要素「4」を比較します。「6」の方が大きいです。
「6」と3番目の要素「8」を比較します。「8」の方が大きいです。暫定最大値の更新です。
「8」と4番目の要素「2」を比較します。「8」の方が大きいです。
「8」と5番目の要素「10」を比較します。「10」の方が大きいです。暫定最大値の更新です。
以上より、最終の確定最小値は「10」とわかりました。

説明がイメージしやすいように「暫定最大値」という表現をしてみました。前から順に比較するうちに、暫定1位が次々変わるイメージです。そして、手順2〜5が繰り返しの手順となりそうです。

手順1は繰り返しの手順というよりは、手順2から繰り返すための前準備みたいなものと見なせます。一旦暫定の最大値を「6」としておき、この値と2番目以降の要素を比較していきます。比較して配列要素の方が大きいときには暫定最大値を更新します（手順3と手順5）。

ということで、

暫定最大値と配列のデータ要素を比較する
- 配列のデータ要素の方が大きい場合、暫定最大値を更新する

という条件分岐を繰り返すことになります。

全体を箇条書きでまとめると、

配列の1番目のデータ要素を暫定最大値とする（値やその添字を管理する）
次の動作を配列の2番目の要素から最後の要素まで繰り返す
1. 暫定最大値と【カウンタ変数】番目のデータ要素を比較する
  1. 【カウンタ変数】番目のデータ要素が大きい場合、暫定最大値（値やその添字）を更新する
ここまでの暫定最大値＝最終確定の最大値とその添字を表示する

という流れになります。1番目の要素は暫定最大値として準備していますので、2番目の要素から繰り返しが始まります。

具体的な変数の割当については、次のフローチャートを確認してください。

フローチャート例

探索ループは暫定最大値更新の条件分岐を繰り返す、という形になっています。

なお、このフローチャート例では暫定最大値を管理するために変数maxValueを使用していますが、この変数とは別に暫定最大値が格納された配列要素の添字（変数maxIndex）を管理しているため、効率を考えると不要です。変数maxValueは配列要素a[maxIndex]で置き換えることができます。

Javaでの実装例

public class Q035 {
    public static void main(String[] args) {
        int[] a = {68, 55, 72, 93, 87}; // 操作対象配列の宣言と初期化
        
        int maxValue = a[0]; // 暫定最大値
        int maxIndex = 0; // 暫定最大値の添字
        
        for (int i = 1; i < a.length; i++) { // 探索ループ
            if (maxValue < a[i]) { // 暫定最大値より大きいか
                maxValue = a[i]; // 暫定最大値を更新
                maxIndex = i; // 暫定最大値の添字を更新
            }
        }
        System.out.println(maxValue);
        System.out.println(maxIndex);
    }
}

Javaでは配列の添字は「0」からスタートしますので、カウンタ変数iの初期化や継続条件式は、上記のフローチャートからはそのように変更しています。配列の要素の添字は0から4（要素数 - 1）なので、0から4までの5回の繰り返しです。

上のフローチャートとの対応からプログラム実装例の流れを確認しましょう。

参考に、以下は変数maxValueを使用しない実装例です。

public class Q035_2 {
    public static void main(String[] args) {
        int[] a = {68, 55, 72, 93, 87}; // 操作対象配列の宣言と初期化
        
        int maxIndex = 0; // 暫定最大値の添字
        
        for (int i = 1; i < a.length; i++) { // 探索ループ
            if (a[maxIndex] < a[i]) { // 暫定最大値より大きいか
                maxIndex = i; // 暫定最大値の添字を更新
            }
        }
        System.out.println(a[maxIndex]);
        System.out.println(maxIndex);
    }
}