アルゴリスム – 最大値を探す。(一番大きい値はどれ？)

要素の中から最大値を探す

要素1, 要素2, 要素3, ・・・ 要素n

まずは、人間がn個の要素の中から最も大きい値を探すには、どのような手順で探すか考えてみましょう。

1. 最初に要素1と要素2を比較して大きい値の方を控える。
2. 次に控えた値と要素3を比較して大きい値の方を控える。
3. さらに2で控えた値と要素4を比較して大きい値の方を控える。

これを要素nまで繰り返すと一番大きい値を探し出せます。

このアルゴリズムでは、1つ目の処理と2つ目以降の処理に違いがあります。1つ目の処理では要素1と要素2を比較しています。2つ目以降の処理では控えた値と要素を比較しています。

2つ目以降の処理は同じ手続きなので、この部分を反復処理させれば要素の個数が増えても対応できそうですね。

プログラミングのアルゴリズムを考える場合、もう一工夫してアルゴリズムをすっきりさせます。

1. まず、要素1が最大値と仮定して変数maxに代入します。
2. 次に、変数maxと要素2を比較して要素2の値のほうが大きい場合、要素2の値を変数maxに代入します。

2の処理を要素nまで繰り返すと変数maxには最も大きい値がセットされます。

最小値を探す手順も、探す値が最大値か最小値かの違いだけで同じ手順になります。

アルゴリズムのイメージ

最大値を探すイメージは以下の図のようになります。

[最大値を探す]

要素値の範囲が2桁の整数値で構成されている等、要素の範囲が決まっている場合、さらにアルゴリズムをすっきりさせる事ができます。

例えば、最大値を0で初期化する、最小値を100で初期化するなど要素の範囲外の値をセットする。

[最大値を探す2]

foreachなど便利な制御構造をサポートしているプログラミング言語では最大値を0で初期化するやり方のほうがすっきり記述できると思います。

サンプルコード

最大値を探すアルゴリズムを以下のプログラミング言語で紹介します。

• Tcl
• Python

Tcl

[サンプル：max.tcl]

#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"

# n個の要素の中から最大値を探す。

# arr : 数値リスト
#  n  : 要素数
#  i  : 要素のindex
# max : 最大値

array set arr {0 31 1 22 2 53 3 14 4 45}
set n [array size arr]

set max $arr(0)    ;# 要素0の値を暫定で最大値とする
set i 1            ;# 1で初期化

while {$i < $n} {
    if {$arr($i) > $max} {
        set max $arr($i)
    }
    incr i
}

parray arr
puts "一番大きい値は $max です。"

[実行例]

$ ./max.tcl
arr(0) = 31
arr(1) = 22
arr(2) = 53
arr(3) = 14
arr(4) = 45
一番大きい値は 53 です。

[リスト、foreachを使った例：max2.tcl]

#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"

# n個の要素の中から最大値を探す。

# lst : 数値リスト
# max : 最大値

set lst {31 22 53 14 45}

set max 0    ;# 数値0を暫定で最大値とする

foreach x $lst {
    if {$x > $max} {
        set max $x
    }
}


puts "数値リスト: $lst"
puts "一番大きい値は $max です。"

[実行例]

$ ./max2.tcl
数値リスト: 31 22 53 14 45
一番大きい値は 53 です。

Python

[サンプル：max.py]

#!/usr/bin/env python3

# n個の要素の中から最大値を探す。

# lst : 数値リスト
#  n  : 要素数
#  i  : 要素のindex
# max : 最大値

lst = [31, 22, 53, 14, 45]
n = len(lst)

max = lst[0] # 要素0の値を暫定で最大値とする
i = 1        #  1で初期化

while i < n:
    if lst[i] > max:
        max = lst[i]

    i += 1

print(lst)
print('一番大きい値は {0} です。'.format(max))

[実行例]

$ ./max.py
[31, 22, 53, 14, 45]
一番大きい値は 53 です。

[forを使った例：max2.py]

#!/usr/bin/env python3

# n個の要素の中から最大値を探す。

# lst : 数値リスト
# max : 最大値

lst = [31, 22, 53, 14, 45]

max = 0    # 数値0を暫定で最大値とする

for x in lst:
    if x > max:
        max = x

print(lst)
print('一番大きい値は {0} です。'.format(max))

[実行例]

$ ./max2.py
[31, 22, 53, 14, 45]
一番大きい値は 53 です。