プログラミング演習II

最終レポート課題

1.レポートの趣旨


プログラミング演習の授業の成果を確認し,出席と通常のレポートによる成績評価に加味するた
めに,レポート提出の機会を設けた.したがって,以下のような人はぜひ提出すること.
・プログラミング演習で身につけたことを評価してほしい人
・欠席や遅刻あるいはレポートの提出遅れや未提出があり,その分を挽回したい人


2.提出方法と期限


通常のレポートと同様に
~/Lisp/Report
のディレクトリに指定されたファイル名のファイルを置く
IMAGE image/pro-ex01.gif


3.レポートの書式(よく読むこと)


提出するレポート名は
IMAGE image/pro-ex02.gif
である.
IMAGE image/pro-ex03.gif
例:
t960000龍谷太郎
(1行空白)
(以下,レポート本体)


レポート本体は,以下の課題中に書かれているファイル名のファイルを順番にすべてマージした

IMAGE image/pro-ex04.gif

ただし,個々のファイルについて,内容の確認を行う場合もあるので,すべてのファイルを同じ
ディレクトリに残しておくこと.特に,
Lispのプログラムファイル(*.lisp)は,ロードすれ
ばそのまま実行できる状態で残しておくこと.


4.レポート課題


IMAGE image/pro-ex05.gif


自然数N以下の素数をすべて求めて表示するLispのプログラムを作成しなさい.ただし,以下の
方法に従うものとする.


実行例:
USER>(prime 20)
(2 3 5 7 11 13 17 19)
#実際に作成するプログラム名は何でもよいが,提出の際には指定のファイル名にすること


素数を求めるアルゴリズムとしては次のような方法がよく知られている.
N以下の素数をすべて求めたいとする.2以上N以下の整数をすべて書き並べておく.最小の数2
は素数である.2の倍数をすべて消す.残った最小の数3は素数である.3の倍数をすべて消す.
残った最小の数5は素数である.5の倍数をすべて消す.以下同様に続けていく.最後に残った
ものはすべて素数である.


このアルゴリズムをLispのプログラムで実現するにはいくつかの方法が考えられ,たとえば,2
から
Nまでのすべての数のリストを作り,そのリストから2,3…と素数の倍数を消していく方法
もあるが,計算機のメモリを多く使い,非効率的なので,あまり賢明とはいえない.
ここでは,「6の倍数に着目する方法」を用いるものとする.
6の倍数の前後の数,つまり,6の倍数−1と6の倍数+1は2や3の倍数ではなく,逆にそれ
以外の数は2か3の倍数であり,素数ではない.そこで,まず6の倍数の前後の数を素数の候補
としてリストにする.
しかし,これらの数も大きくなると,5以上の素数の倍数となっている場合もあるので,それら
の数を除いてやる.素数の候補のリストに素数以外の数が含まれているかどうかは,5以上の素
数の平方が
Nより大きいかどうかで判断できる.
(ヒント:メインの関数だけでなく,下請けの仕事をするサブの関数をいくつか定義するこ
と.)
(提出用のファイル名:
report.a1.lisp


出力例として,1000までの素数を表示させ,ファイルにすること.
(ファイルにする方法:表示した結果をマウスの左ボタンでコピーし,エディタに中ボタンでペー
ストして,ファイル名をつけて保存する.)
(提出用のファイル名:
report.a1.out


プログラムの説明(日本語)を書いたものをファイルにすること.
(提出用のファイル名:
report.a1.doc


IMAGE image/pro-ex06.gif


A-1以外の適当な方法で(つまり,「6の倍数に着目する方法」を用いず),自然数N以下の素数
をすべて求めて表示する
Lispのプログラムを作成しなさい.
ただし,「2から
Nまでのすべての数のリストを作り,そのリストから2,3…と素数の倍数を消
していく方法」などを用いて
1000までの素数を求めようとしても,前述の通りメモリ不足とな
る.そのような場合は,どのぐらいの大きさの素数まで求めることができるかをレポートにする
こと.


この場合の提出用のファイル名は,それぞれ以下の通り.
Lispプログラム:report.a0.lisp
出力結果:report.a0.out
プログラムの説明:report.a0.doc


IMAGE image/pro-ex07.gif


A-1と同様のプログラムをループ(loop)形式で作成しなさい.テキストの6章や8章などを参
照のこと.


この場合の提出用のファイル名は,それぞれ以下の通り.
Lispプログラム:report.a2.lisp
出力結果:report.a2.out
プログラムの説明:report.a2.doc