AP過去問 令和6年度秋期 午後 問3 プログラミング
AP 過去問題 午後に戻る。
AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。
AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。
令和6年度秋期 午後 問3 プログラミング(AIプロンプト向け)
■
令和6年度秋期 午後 問3 プログラミング(問題原文)
■素数を列挙するアルゴリズムに関する次の記述を読んで、設問に答えよ。
素数とは、2以上の自然数のうち、正の約数が1と自身だけである数のことである。
2以上の自然数Nに対して、N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお、本問では、配列の要素番号は1から始まり、要素数が0の配列を{}で表す。
|
〇整数型の配列: prime1(整数型: N) |
この関数prime1の時間計算量は、Nを用いて表すとO( ア )である。
[アルゴリズムの改良1]
素数の定義によって、2以上の自然数sについて、s自身を除くsの正の倍数uは、1とu以外にsも約数に含むので素数ではない。この性質を利用して関数prime1を改良し、次の手順で素数を列挙する関数prime2を考える。
(1) 2以上N以下の自然数について、全て “素数である” とマークする。
(2) 2以上N以下の自然数dについて、次の(a)、(b)を行う。
- (a) dが “素数ではない” とマークされている場合、何もしない。
- (b) dが “素数である” とマークされている場合、次の処理を行う
- ① dが素数であることを確定させる。
- ② d以上の自然数xについて、dをx倍した数を“素数ではない” とマークする。
関数prime2のプログラムを図2に示す。
|
〇整数型の配列: prime2(整数型: N) |
関数prime2は関数prime1と比較してメイン処理部の時間計算量を小さくすることができ、引数Nの値が同一の場合において、関数prime2の(L2)の行の実行回数は関数prime1の(L1)の行の実行回数以下となる。
[アルゴリズムの改良2]
4以上の偶数は全て2の倍数であるので、素数ではない。したがって2以外の素数を列挙するためには奇数だけを考慮すればよい。この性質を利用して、関数prime2に次の変更を加えた関数prime3を考える。
(1) 関数の戻り値として素数の一覧が格納されるprimesにあらかじめ2を格納しておく。 (2) いずれのループも奇数についてだけが実行されるようにする。 (3) 3以上の自然数2k+1が素数か否かをisPrime[k]で表すようにする。
関数prime3のプログラムを図3に示す。
|
〇整数型の配列: prime3(整数型: N) |
関数prime3は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。引数Nの値が同一の場合において、関数prime3の(L3)の行の実行回数は、関数prime2の(L2)の行の実行回数の半分以下となる。加えて、計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。
設問1 本文中の ア に入れる適切な字句を答えよ。
設問2 図2中の イ 、 ウ に入れる適切な字句を答えよ。
設問3 図3中の エ ～ カ に入れる適切な字句を答えよ。
設問4 prime1(20)、prime2(20)、prime3(20)をそれぞれ実行したとき、図1中の(L1)の行、図2中の(L2)の行、図3中の(L3)の行が実行される回数をそれぞれ答えよ。
回答・解説
プログラムが3つに分かれていて、それぞれの動きを理解しなければならないことと、問題文で数学的用語が使われるので、何を言っているか理解する力を試される問題です。素数の性質を明確に理解していない人は素数の仕組みを改めて考えることになる問題でもあったと思います。トレースする時間がかかるので中程度の高難度の間くらいの難易度かなと思います。管理人は、試験の最後に取り組んだのですが、時間がなくて焦って全然だめでした。ふふふ。悔しい。この程度の問題も解けずに撃沈するとはね。最初の一問だけサービス問題かなと思いました。楽に答えられましたが、他は適当に埋めたら、適当に間違ってました。そうそう感覚的に答えれる問題でもないわな。最後の実行回数なんかはトレースする時間がなければ、答えられるわけもなし。この1問に1時間くらいくれればとけてたと思う。
悔やんでもしょうがないので一問づつ、やっていきましょう。
設問1
prime1の時間計算量は、Nを用いて表すとO( ア )である。
の穴埋めなので、prime1関数のNが増えた時にどれくらいの計算量になるかを考える問題です。ループの部分に注目するとwhileが二重になっているということへの気づきが大事になってきます。そしてその繰り返し構造がどうなっているかを見極めるだけです。ループの設定を読み解いてみましょう。
一つ目のループは(dがN以下)となっています。Nは計算量のNと同じ位置づけなので最初に与えられる関数の引数Nです。後の問題で出てくるprime1(20)を基準に考えると、dは初期値が2なので、2から20までの計算量O(N)が一つ目のループだけの計算量といえます。dはループの終端で毎回1づつ増加するので、ループの回数は2～20までをステップ1づつで処理しています。
二つ目のループは(tがd未満)です。tは毎回、初期値が2にリセットされる一定の繰り返し開始値で、ステップ値は1です。dは2からはじまってNまでをステップ1づつ増加していく値です。未満なので、最初はt=2、終了条件は2未満なので0回で、1回と繰り返し回数が増えていってNが20の場合は最後の終了条件はd=20のときです20未満となります。
つまり、prime1(20)のNが20のときの例でみると一つ目のループと二つ目のループは以下のような仕組みで繰り返されます。
| ループ1のdの値 | ループ2が実行されるときのtの値 |
| 2 | |
| 3 | 2 |
| 4 | 2, 3 |
| 5 | 2, 3, 4 |
| 6 | 2, 3, 4, 5 |
| 7 | 2, 3, 4, 5, 6 |
| 8 | 2, 3, 4, 5, 6, 7 |
| 9 | 2, 3, 4, 5, 6, 7, 8 |
| 10 | 2, 3, 4, 5, 6, 7, 8, 9 |
| 11 | 2, 3, 4, 5, 6, 7, 8, 9, 10 |
| 12 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 |
| 13 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 |
| 14 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 |
| 15 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 |
| 16 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 |
| 17 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 |
| 18 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 |
| 19 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 |
| 20 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 |
という感じで、2回目の繰り返しの終了値がNではなく1づつ大きくなってNになるまでという仕組みなので、N2とまではいかないですが、計算量はN2に概ね従うことがわかります。具体的な繰り返し回数だけで見ると (N-1)(N-2)/2 で (N2-3N+2)/2という回数です。時間計算量として見る時はN2以外、つまり最も計算量に影響する値以外の具体的な回数は無視することになっています。したがって答えは
N2
です。Order(N2)のような表現方法がわかっていないとつらい問題だったと思いますが、直感的に答えれるのはせいぜいここまででしょう。具体的に繰り返し回数を計算するには、上記に示した表まで思い描く時間が必要です。表のようなものが繰り返し回数だとわかれば最後の問題にも答えられようものです。計算式を導き出せなくても、1+2+…+19
AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。
AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。
AP 過去問題 午後に戻る。