平成25年度 春期 午前 問7
基礎理論
アルゴリズムに関する問題
配列 A に対して次の手続を実行して，2 ≦ k ≦ 100 である素数 k だけを全て出力したい。a，b，c に入るループの初期値，終値，増分として，適切な組合せはどれか。
〔手続〕
for k = 2 to 100 step 1:
A[k] = 1;
for m = 2 to 10 step 1:
for k = [ a ] to [ b ] step [ c ]:
A[k] = 0;
for k = 2 to 100 step 1:
if A[k] ≠ 0:
print k;- アa＝2 ／ b＝m² ／ c＝1
- イa＝2m ／ b＝100 ／ c＝m
- ウa＝m ／ b＝m² ／ c＝m
- エa＝m² ／ b＝100 ／ c＝1
答えと解説を見る
✓ これが正解イa＝2m ／ b＝100 ／ c＝m
解説
倍数を消すループは 2m から端まで m 刻みです。
この手続は三つの部分に分かれています。最初に配列を全部 1 にして候補の印を立て、次に真ん中の二重ループで合成数の印を消し、最後に残った印を出力します。ですから真ん中の内側のループは、ある数の倍数だけをたどるものです。まず刻み幅を決めます。倍数を順に拾うのですから、増分はその数自身になります。1 ずつ動かしては倍数だけを狙えません。次に始まりです。その数自身は素数として残さなければなりませんので、二つ目の倍数から始めます。自分自身から始めると、素数の印まで消してしまいます。終わりは配列の端までです。途中で打ち切ると消し残しが出て、合成数が素数として印字されてしまいます。外側が 10 で止まるのは、100 以下の合成数が必ず 10 以下の約数を持つからです。この手順はエラトステネスのふるいと呼ばれる古典的なアルゴリズムで、そのループが何を数え上げたいかを一文で言えれば三つの空欄は同時に決まります。
ほかの選択肢はなぜ違うのか
- アa＝2 ／ b＝m² ／ c＝1：内側を 1 刻みで動かす形です。倍数だけを選べませんので、残すべき印まで次々に消えてしまいます。終わりも二乗までに限られ、配列の端に届きません。
- ウa＝m ／ b＝m² ／ c＝m：刻み幅は合っていますが、自分自身の位置から消し始めてしまいます。この形では 2 や 3 といった小さな素数の印が最初に消え、出力から抜け落ちます。
- エa＝m² ／ b＝100 ／ c＝1：二乗の位置から 1 刻みで端まで消す形です。倍数以外の位置まで印を消してしまいますので、残るはずの素数が大量に失われます。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成25年度 春期 応用情報技術者試験 午前 問7
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）