プログラミングの実践
変数・配列・関数を使い、簡単なアルゴリズムを書く。
- 変数と配列の値を追跡できる
- 初期値と繰り返し範囲を説明できる
- 境界条件を含むテストを考えられる
このレッスンの擬似コードでは配列の添字は1から始め、for i = 1 to n は両端を含みます。← は右辺を計算して左辺の変数に代入する記号で、等式ではありません。実際の言語では添字が0から始まる場合もあるため、規則を先に確認しましょう。
よく出るアルゴリズム
- 合計・平均: ループで累積する
- 最大値探索: 先頭を仮の最大値にし、より大きい値が出たら更新
- カウント: 条件を満たしたらカウンタを +1
- ソート: 隣接交換（バブルソート）など。バブルソートの最悪時間計算量は O(n²) だが、すべての整列法がこの計算量ではない
配列 data = [5, 3, 8, 1] の最大値を求める擬似コードを示せ。
解答・解説
`max ← data[1]` `for i = 2 to 4` ` if max < data[i] then max ← data[i]` → **max = 8**
累積と条件の追跡
data = [5, 3, 8, 1] のうち5以上の値の平均を求めたい。s ← 0、count ← 0から始め、各値が5以上ならsにその値を加え、countを1増やす。最終的なs、count、平均を求めよ。
解答・解説
5で (s, count) = (5, 1)、3では変化なし、8で (13, 2)、1では変化なし。合計13、個数2なので平均は13 ÷ 2 = **6.5**。配列全体の個数4では割りません。
| 読んだ値 | s | count |
|---|---|---|
| 初期状態 | 0 | 0 |
| 5 | 5 | 1 |
| 3 | 5 | 1 |
| 8 | 13 | 2 |
| 1 | 13 | 2 |
関数は処理を名前のついたまとまりにする仕組みです。引数で値を受け取り、戻り値で結果を返します。例えば「空でない数値配列を受け取り最大値を返す関数」なら、入力の条件と結果を明確にして再利用できます。通常の例だけでなく、要素1個・全要素が負・同じ値の繰り返しもテストします。
data = [−5, −3, −8] の最大値を0で初期化すると何が起きるか。修正方法も述べよ。
解答・解説
どの要素も0より大きくないため、配列にない0が答えになってしまいます。先頭の−5で初期化すれば、次の−3で更新され、正しい最大値**−3**が得られます。
s ← 0、i ← 1 とし、i ≤ 3 の間「s ← s + i、i ← i + 1」の順で繰り返す。終了時のsとiを求めよ。
解答・解説
各反復後の (s, i) は (1, 2)、(3, 3)、(6, 4)。i = 4で条件が偽になるので、**s = 6、i = 4**です。
5以上の値の平均を求める例題に data = [1, 2, 3] を与えるとどうすべきか。
解答・解説
count = 0なので0で割らず、「該当なし」を返すなどの分岐を入れます。条件を満たす値がない入力は大切な境界テストです。