HOME»基本情報技術者試験掲示板»平成19年春期  問14について
投稿する

平成19年春期  問14について [4049]

 モンローヒトウさん(No.1) 
タイトルにある問題はアルゴリズムに関する問題です。
問題内で示されるアルゴリズムの手順の一つ目、
「1.iを1からn-1まで1ずつ増やしながら行2~3を繰り返す」
がなぜ手順として必要なのか疑問を持ちました。

私のイメージでは、iが1から順に増えていく手順が無くとも、手順2,3を繰り返していれば、同様の機能を持ったアルゴリズムができそうな気がしました。
このアルゴリズム上で手順1が担っている役割はどういったもので、なぜこの手順が必要なのかわかる方いましたら教えて下さい!
2022.03.23 15:59
chihiroさん(No.2) 
FE プラチナマイスター
この投稿は投稿者により削除されました。(2022.03.23 18:08)
2022.03.23 18:08
chihiroさん(No.3) 
FE プラチナマイスター
単に配列を整列するだけであれば、
>1.iを1からn-1まで1ずつ増やしながら
この箇所は不要です(繰り返し回数をあらかじめ設定する必要はありますが)。この手順は、アルゴリズムの効率化が目的です。
解説にある、初回の処理後の文字列[1735]について考えてみましょう。
2回目の整列で、上の箇所を無視した場合、整列は以下のように行われます。
ただし、手順2を以下のように変更します。
>jをnから2まで減らしながら行3を繰り返す

①5と3の比較  5<3は成り立たないので交換はしない
②3と7の比較  3<7は成り立つので交換する  [1735]→[1375]
③7と1の比較  7<1は成り立たないので交換はしない
となり、2回目の整列終了後の文字列は[1375]となります。
上の処理において、③は不要です。なぜなら、1回目の処理でA[1]は必ず最小値となるため、A[1]とA[2]の交換は絶対に行われないからです。3回目の整列においても、A[1]<A[2]<その他となるため、A[2]とA[3]およびA[1]とA[2]の比較は無駄になります。つまり、
>1.iを1からn-1まで1ずつ増やしながら
この箇所は、無駄な比較処理を省くためのものなのです。これによって比較回数が減っていることを確認してみてください。
2022.03.23 18:07
chihiroさん(No.4) 
FE プラチナマイスター
補足です。比較回数を減らす箇所は正確には以下の2箇所です(両方が必要)。
>iを1からn-1まで1ずつ増やしながら
>jをnからi+1まで減らしながら
2022.03.23 18:27
返信投稿用フォームスパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop