「AP過去問 令和6年度秋期 午後 問3 プログラミング」の版間の差分

提供：yonewiki
103行目: 103行目:
</table>
</table>
<div align="center">図2　関数prime2のプログラム</div>
<div align="center">図2　関数prime2のプログラム</div>
　関数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に示す。
<table width="100%" border="2" style="border-collapse: collapse;border-style: solid">
<tr>
  <td style="border: 2px solid;">
〇整数型の配列: prime3(整数型: N) </br>
　整数型の配列: primes ← {2}　　　 /*結果となる素数の一覧を格納する一次元配列 */</br>
　論理型の配列: isPrime ← {} 　　　/*isPrime[k]がtrueであれば2k+1が素数であることを</br>
　　　　　　　　　　　　　　　　　　表し、falseであれば2k+1が素数ではないことを表す</br>
　　　　　　　　　　　　　　　　　　一次元配列 */</br>
　整数型: c ← 3</br>
　整数型: d ← 3</br>
　整数型: t</br>
　while (c が N 以下)</br>
　　isPrimeの末尾にtrueを追加する</br>
　　c ← c + 2</br>
　endwhile</br>
　/* メイン処理開始 */</br>
　while (d が N 以下)</br>
　　if ( <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">エ</span> )</br>
　　　primesの末尾にdの値を追加する</br>
　　　t ← d × d</br>
　　　while (t が N 以下)</br>
　　　　isPrime[ <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">オ</span> ] ← false</br>
　　　　t ← <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">カ</span></br>
　　　endwhile</br>
　　endif</br>
　　d ← d + 2</br>
　endwhile</br>
　/* メイン処理終了 */</br>
　return primes</br>
</td>
</tr>
</table>
<div align="center">図3　関数prime3のプログラム</div>
　関数prime3は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。引数Nの値が同一の場合において、関数prime3の(L3)の行の実行回数は、関数prime2の(L2)の行の実行回数の半分以下となる。加えて、計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。
設問1　本文中の <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">ア</span> に入れる適切な字句を答えよ。
設問2　図2中の <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">イ</span> 、 <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">ウ</span> に入れる適切な字句を答えよ。
設問3　図3中の <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">エ</span> ～ <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">カ</span> に入れる適切な字句を答えよ。
設問4　prime1(20)、prime2(20)、prime3(20)をそれぞれ実行したとき、図1中の(L1)の行、図2中の(L2)の行、図3中の(L3)の行が実行される回数をそれぞれ答えよ。


　
　

2024年11月17日 (日) 18:33時点における版

AP 過去問題 午後に戻る。

AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。

AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

令和6年度秋期 午後 問3 プログラミング(AIプロンプト向け)

■

　

令和6年度秋期 午後 問3 プログラミング(問題原文)

■素数を列挙するアルゴリズムに関する次の記述を読んで、設問に答えよ。


　素数とは、2以上の自然数のうち、正の約数が1と自身だけである数のことである。

　2以上の自然数Nに対して、N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお、本問では、配列の要素番号は1から始まり、要素数が0の配列を{}で表す。


〇整数型の配列: prime1(整数型: N)
　整数型の配列: primes ← {}　　　 /*結果となる素数の一覧を格納する一次元配列 */
　論理型: isPrime　　　　　　　　 /*ループ内で着目している数が素数か否かを表す変数。
　　　　　　　　　　　　　　　　　　trueであれば、素数であることを表し、falseであれば
　　　　　　　　　　　　　　　　　　素数ではないことを表す*/
　整数型: d ← 2
　整数型: t
　/* メイン処理開始 */
　while (d が N 以下)
　　isPrime ← true　　　　　　　　/*仮で素数として扱う */
　　t ← 2
　　while (t が d 未満)
　　　if (d mod t が 0 と等しい)
　　　　isPrime ← false
　　　endif
　　　t ← t + 1
　　endwhile
　　if (isPrime が true と等しい)
　　　primes の末尾にdの値を追加する
　　endif
　　d ← d + 1
　endwhile
　/* メイン処理終了 */
　return primes
図1　関数prime1のプログラム


　この関数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)
　整数型の配列: primes ← {}　　　 /*結果となる素数の一覧を格納する一次元配列 */
　論理型の配列: isPrime ← {false} /*isPrime[k]がtrueであればkが素数であることを
　　　　　　　　　　　　　　　　　　表し、falseであればkが素数ではないことを表す
　　　　　　　　　　　　　　　　　　一次元配列 */
　整数型: c ← 2
　整数型: d ← 2
　整数型: t
　while (c が N 以下)
　　isPrimeの末尾にtrueを追加する
　　c ← c + 1
　endwhile
　/* メイン処理開始 */
　while (d が N 以下)
　　if ( イ )
　　　primesの末尾にdの値を追加する
　　　t ← d × d
　　　while (t が N 以下)
　　　　isPrime[t] ← false
　　　　t ← ウ
　　　endwhile
　　endif
　　d ← d + 1
　endwhile
　/* メイン処理終了 */
　return primes
図2　関数prime2のプログラム


　関数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)
　整数型の配列: primes ← {2}　　　 /*結果となる素数の一覧を格納する一次元配列 */
　論理型の配列: isPrime ← {} 　　　/*isPrime[k]がtrueであれば2k+1が素数であることを
　　　　　　　　　　　　　　　　　　表し、falseであれば2k+1が素数ではないことを表す
　　　　　　　　　　　　　　　　　　一次元配列 */
　整数型: c ← 3
　整数型: d ← 3
　整数型: t
　while (c が N 以下)
　　isPrimeの末尾にtrueを追加する
　　c ← c + 2
　endwhile
　/* メイン処理開始 */
　while (d が N 以下)
　　if ( エ )
　　　primesの末尾にdの値を追加する
　　　t ← d × d
　　　while (t が N 以下)
　　　　isPrime[ オ ] ← false
　　　　t ← カ
　　　endwhile
　　endif
　　d ← d + 2
　endwhile
　/* メイン処理終了 */
　return primes
図3　関数prime3のプログラム


　関数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)の行が実行される回数をそれぞれ答えよ。

　

回答・解説

　

AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。

AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

AP 過去問題 午後に戻る。

「https://wiki.yo-net.jp/index.php?title=AP過去問_令和6年度秋期_午後_問3_プログラミング&oldid=8459」から取得