分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

流れ図をトレースしていくと比較後に行われる処理によって変数xの値は下表に示すように増加していきます。比較条件となるxに注目すると以下のような規則性に従って増加していることに気が付きます。

• (1回目) 0＝0
• (2回目) 1＝1
• (3回目) 3＝1＋2
• (4回目) 6＝1＋2＋3
• (5回目) 10＝1＋2＋3＋4
• (6回目) 15＝1＋2＋3＋4＋5
• (7回目) 21＝1＋2＋3＋4＋5＋6
• x＝1＋2＋3＋…n

1からnまでの数列の和の計算方法については以下のように考えます。

1～10までの和が、

　1＋2＋3＋4＋5＋6＋7＋8＋9＋10
＝(1＋10)＋(2＋9)＋(3＋8)＋(4＋7)＋(5＋6)
＝11×5
＝55

として計算できるように、1～nまでの和は、

　1＋2＋3＋…＋n
＝(1＋n)×(n÷2)
＝n(n＋1)／2

という式で表すことができます。

nに適当な値を代入し「n(n＋1)／2＞5000」となる閾値を考えると、n＝100 の時点で式の値が5050となり5000を超えることがわかります。

　99(99＋1)／2＝99×100÷2＝4950
　100(100＋1)／2＝100×101÷2＝5050
　101(101＋1)／2＝101×102÷2＝5151

上の表から考えるとxの値が「1＋2＋3＋…＋100」と同値になるのは101回目比較後の処理時となり、ループを抜け手続きが終了するのは次の102回目の比較後になります。

したがって手続きが終了するまでに行われる比較回数はに102回が適切です。