| 第１種情報処理技術者試験 |
1999年度 ＝ 平成11年度 |
午前 |
問5 |
次の流れ図は、最大値選択法によって値を大きい順に整列するものである。＊印の処理（比較）が実行される回数を表す式はどれか。
ア n-1
|
n(n - 1)
イ ────
2
|
n(n + 1)
ウ ────
2
|
エ n2
|
イ
本アルゴリズムは、＜交換＞ループの中に＜最大値＞ループが入っている２重のループ構造となっています。問われている＊印の処理は、内側の＜最大値＞ループが繰り返されるたびに1回ずつ実行されます。
＜交換＞ループでは、iの値が1からn-1まで増えていきますので、内側の＜最大値＞ループが実行される回数は次のようになります。
- i=1のとき … n - 1回
- i=2のとき … n - 2回
- （中略）
- i=n-2のとき … 2回
- i=n-1のとき … 1回
したがって、合計回数は次のようになります。
1 + 2 + … + (n - 2) + (n - 1) = n(n-1) / 2
