コンピュータサイエンス入門 第四章 超個人的解答
多分来週出せない ＼(＾o＾)／
プログラム組まないといけないから、時間的に間に合わないと思う。
というわけで、来週は試験があるのでパスできるものはパスして、試験に集中する。
2008/05/25 19:58
ソートとか検索とかは、ネットで適当なアルゴリズムを何かに実装してやるとして。暗号と符号化は、手で処理しても問題なさそうですね。
プログラムを組んで確かめるところは後の勉強の教材にすることにして、第五章を始めることにした。じゃないと来週も忙しいから出す機会が消えるかもしれないので。
2008/05/31 17:46
今週の月曜には出せなくて、来週出すべくがんばってます。
後はソートの時間測定ぐらいかな。アルゴリズム実装します。
2008/06/01 14:51
もうじき完成。印刷し終えたら内容を追記したいと思います。
解答一覧
4.1
4.2
１． 計算できない問題の例を考えてください。
Ans.
任意のプログラムが停止するかどうかを決定する問題（停止問題）、別々に作られた２つのプログラムが全く同じである（同じデータを入力した解き同じ結果を出力する）ことを調べる問題（同値問題）がある。
4.3
１． 最大公約数を求めるアルゴリズムが正しいと信じられるかどうか、いくつかのデータを使って確かめてください。
Ans.
いくつかの条件で計算をしてみる。結果は全て正しかったので、正しいと信じられる。def gcd(a,b): while b != 0: a, b = b, (a % b) return a num1 = input('1st num: ') num2 = input('2nd num: ') print gcd(num1,num2)実行結果
gcd(1,2) = 1
gcd(3,6) = 3
gcd(10,15) = 5
gcd(16,72) = 8
gcd(27,36) = 9
4.4
１． 整数の配列をソートするプログラムをいくつかのソート方法で作成して、実際にかかる時間を計測してください。
Ans.
挿入ソート、クイックソート、をそれぞれ比較する。１から100のランダムな数値が格納されている配列を、それぞれのソートアルゴリズムにかけて、処理にかかった時間を計測する。
Pythonでそれぞれのソートアルゴリズムを作成。アルゴリズムを1万回実行してかかった時間を計測する。5回測定して、出力された値から小数点第二位までで切り捨てた値を採用し、平均の秒数を出した。
結果、挿入ソートは約24.91秒、クイックソートは約6.78秒の時間を要した。結果一覧
結果は全て秒単位である。
回数と合計 挿入ソート クイックソート 配列100個 1回目 25.16 6.81 2回目 24.93 6.76 3回目 24.85 6.79 4回目 24.73 6.77 5回目 24.89 6.77 平均 24.91 6.78 4.4.1で使用したプログラムのソースコード（Python）
：挿入ソート#メインルーチン def InsSort(n, a): i = 1 for i in range(1, n): temp = a[i] j = i - 1 while j >= 0 and a[j] > temp: a[j+1] = a[j] j -= 1 a[j+1] = temp #処理を実行 def main(): #ランダムな配列を100個用意 import random #anumに配列の数を入力 anum = 100 array = [0 for i in range(anum+1) ] for i in range(anum): array[i] = int(random.random() * 100 + 1) #配列の長さを取得 alen = len(array) #メインルーチンを実行 InsSort(alen, array) #実行時間計測用 from timeit import Timer t1 = Timer(setup='from __main__ import main', stmt='main()') print t1.repeat(5,10000)
4.4.1で使用したプログラムのソースコード（Python）
：クイックソート#メインルーチン def qsort(a, left, right): x = a[(left + right) / 2] i, j = left, right while 1: while a[i] < x: i += 1 while x < a[j]: j -= 1 if i >= j: break a[i], a[j] = a[j], a[i] i += 1 j -= 1 if left < i - 1: qsort(a, left, i - 1) if j + 1 < right: qsort(a, j + 1, right) #処理を実行 def main(): #ランダムな配列を100個用意 import random #anumに配列の数を入力 anum = 100 array = [0 for i in range(anum+1) ] for i in range(anum): array[i] = int(random.random() * 100 + 1) #配列の長さを取得 alen = len(array) #メインルーチンを実行 qsort(array, 0 , alen-1) #実行時間計測用 from timeit import Timer t1 = Timer(setup='from __main__ import main', stmt='main()') print t1.repeat(5,10000)
２．様々なパターンのデータを作成してクイックソートでソートし、実際にかかる時間を比較してください。
Ans.
ランダムに数値が格納されている配列を、それぞれ10個、100個、1000個を用意する。クイックソートで処理した時間を計測する。
配列に格納されている数値はそれぞれ1から始まり、10、100、1000までとした。5回測定して、出力された値から小数点第二位までで切り捨てた値を採用し、平均の秒数を出した。
使用したプログラムは、4.4.1のクイックソートのソースコードを利用した。結果は以下のようになった。結果は全て秒単位である。
結果一覧
利用した配列 10個 100個 1000個 1回目 0.63 6.81 87.03 2回目 0.63 6.76 87.33 3回目 0.57 6.79 85.99 4回目 0.58 6.77 85.49 5回目 0.57 6.77 85.71 平均 0.596 6.78 86.31
4.5
１． 多数の数の配列から特定の数を検索するプログラムを線形探索か２分探索のいずれかで作成してください。
Ans.
Pythonを利用して、1から100までの数値がランダムに格納された100個の配列を線形検索（リニアサーチ）するプログラムを作成。
変数anumに配列の個数を指定、変数skeyに検索する値を入力する。
4.5.1で作成したプログラムのソースコード（Python）
#メインルーチン def linear_search(a, key): #print youso i = x = 0 for i in range(len(a)): if a[i] == key: x = i break return x #処理を実行 def main(): #ランダムな配列を100個用意 import random #anumに配列の数を入力 anum = 100 array = [0 for i in range(anum+1) ] for i in range(anum): array [i] = int(random.random() * 100 + 1) #検索する値を入力 skey = 1 #処理を実行 print "array", array, "search key is", skey ls = linear_search(array, skey) print "linear search, found array number is",ls #実行用 if __name__ == '__main__': main()
２．シーザー暗号で、K=3として「Hello, dogs」を暗号化してください。
Ans.
K=3の場合、A=D、b=eのように３文字ずらすものである。
「Hello, dogs」を暗号化すると、 「Khoor, grjw」 となる。
3. Lempel-Ziv符号化を使って「The rain in Spain falls mainly on the plain」を符号化してください。
Ans.
Lempel-Ziv符号化とは、あるアルファベットの集まりが、文章中に繰り返されている場合、最初の集まり以降は省略できるものである。
「The rain in Spain falls mainly on the plain」を符号化すると、「he」と「in」"ain", "ain（半角スペース）" "the（半角スペース）" が省略可能であるので、
「The rain <3.2> Spa<6.2> falls ma<11.2>ly on <3３.2> pla<14.2>」
- 修正
「The rain <3,3>Sp<9,4>falls m<11,3>ly on <34,4>pl<15,3>」
となる。
- 訂正、修正 2008/06/28 22:57:26
この問題について意見をもらいましたので、修正しました。
アスキー デジタル用語辞典にて、例文と同じものがありましたのでそれに沿って修正しておきました。僕の解答は全く合っていないようです。
（Thanks！ microsoftさん）
以下のサイトは詳しく書かれていますので、一度ご確認してもらえるといいと思います。
- 追記：2008/07/05 19:03:56
今、アスキーの用語辞典をみたらリニューアルしたらしく詳細に解説をされていた内容が無くなっていましたので報告。
なので、解答に解説を加えて置きました。なお、この例文は、ミュージカル「マイフェアレディ」で使われている劇中歌の一文のようです。
