コンピューターアルゴリズム 11/1 の宿題のドラフト

大学

よーしパパ頑張って釣っちゃうぞー。

問1

与えられた数が素数であるかどうかを検査するプログラム PrimaryNumber.java（文字コード：Shift_jis, 改行コード：DOS/WIN）を完成させよ。なお，自然数 n が素数であるかどうかは，2〜n-1 の自然数で割り切れるかどうかで検査する。上記ソースコードは穴あきソースコードとなっているので，適宜埋める形で所望の機能を実現せよ。提出は「穴を埋めたソースコード」＋「実際にそのプログラムを走らせた結果」を示したファイル（text or PDF）を提出せよ。

解答

5340bef71b622da638f1004ab6b39635 *PrimaryNumber.java

ソースコードのMD5 ハッシュを晒すので、あとはこれのコリジョンを探せばいいと思うよ(・∀・)

問2

とある中学校の各クラスの学生数が与えられている（ソースコード参照）。
あ）全学年，全クラスを通して得られる１クラス当りの平均生徒数
い）各学年毎に得られる（その学年の全クラスを通して得られる）１クラス当りの平均生徒数
う）各クラス毎に得られる（３学年を通して得られる）１クラス当りの平均生徒数
を求めるためのプログラム ClassSize.java を完成せよ。穴埋めソースコードとプラグラム出力結果を一緒に示したファイルを提出すること。

解答

ソースコードをBase64エンコードしたので、Base64デコードすればいいと思うよ。

Ly8gibqLTILMg06DiYNYjVyQrILwguCCwop3jVqCyZHOgrWCxIFDCi8vIIJQ
gUSRU4p3lE6BQ5FTg06DiYNYgvCSyoK1gsSTvoLnguqC6YJQg06DiYNYk5aC
6ILMlb2Lz5C2k2uQlAovLyCCUYFEimWKd5ROloiCyZO+gueC6oLpgWmCu4LM
ineUToLMkVODToOJg1iC8JLKgrWCxJO+gueC6oLpgWqCUINOg4mDWJOWguiC
zJW9i8+QtpNrkJQKLy8gglKBRIplg06DiYNYloiCyZO+gueC6oLpgWmCUop3
lE6C8JLKgrWCxJO+gueC6oLpgWqCUINOg4mDWJOWguiCzJW9i8+QtpNrkJQK
Ly8ggvCLgYLfgr2CooFCCi8vIILIgqiBQ2NsYXNzIILGgqKCpJJQjOqCzZdc
lvGM6oLIgsyCxY5ngqaCyIKigr2C34FDiMiJuoLFgs2BQ2dyb3VwLCCDT4OL
gVuDdoLGgqKCpAovLyCSUIzqgvCDToOJg1iCzJHjgu2C6ILJl3CCooLEgqKC
6YFCCi8vCi8vICAgICAgICCCUJFngUCCUZFngUCCUpFngUCCU5FngUCCVJFn
Ci8vICCCUJROICAgIDMzICAgIDM1ICAgIDM0ICAgIDMyICAgIDM2Ci8vgUCC
UZROICAgIDM0ICAgIDMzICAgIDM1ICAgIDMzICAgIDMxCi8vgUCCUpROICAg
IDMxICAgIDMyICAgIDM2ICAgIDMwICAgIDM1Ci8vCgoKLyoKPSCPb5fNjIuJ
yiA9CgojQXZlcmFnZSBudW1iZXIgb2Ygc3R1ZGVudHMgaW4gYSBncm91cC4K
MzMKI0F2ZXJhZ2UgbnVtYmVyIG9mIHN0dWRlbnRzIGZvciBlYWNoIGdyYWRl
LgozNCAzMyAzMwojQXZlcmFnZSBudW1iZXIgb2Ygc3R1ZGVudHMgZm9yIGVh
Y2ggZ3JvdXAuCjMzIDMzIDM1IDMyIDM0CgoqLwoKY2xhc3MgQ2xhc3NTaXpl
IHsKICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiggU3RyaW5nW10gYXJncyAp
IHsKICAgIGludFtdW10gc2l6ZSA9IHsgeyAzMywgMzUsIDM0LCAzMiwgMzYg
fSwKICAgICAgICAgICAgICAgICAgICAgeyAzNCwgMzMsIDM1LCAzMywgMzEg
fSwKICAgICAgICAgICAgICAgICAgICAgeyAzMSwgMzIsIDM2LCAzMCwgMzUg
fSB9OwoKICAgIGludFtdIGdyYWRlID0gbmV3IGludFszXTsgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgICAvLyBncmFkZVtpXSA9IIp3lE4gaSCCzJGN
kLaTa5CUCiAgICBpbnRbXSBncm91cCA9IG5ldyBpbnRbNV07ICAgICAgICAg
ICAgICAgICAgICAgICAgICAgICAgLy8gZ3JvdXBbaV0gPSCDT4OLgVuDdiBp
IILMkY2QtpNrkJQKICAgIGludCAgIHN1bTsgICAgICAgICAgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgICAgICAgICAvLyCKd41akVORzILMkY2QtpNr
kJQKICAgIGludCAgIGksIGo7CgogICAgZm9yKCBpID0gMCA7IGkgPCBncmFk
ZS5sZW5ndGggOyBpKysgKSAgZ3JhZGVbaV0gPSAwOyAgIC8vIJR6l/GCzI+J
ivqJuwogICAgZm9yKCBpID0gMCA7IGkgPCBncm91cC5sZW5ndGggOyBpKysg
KSAgZ3JvdXBbaV0gPSAwOyAgIC8vIJR6l/GCzI+JivqJuwogICAgc3VtID0g
MDsKCiAgICBmb3IoIGkgPSAwIDsgaSA8IDMgOyBpKysgKSB7ICAgICAgICAg
ICAgICAgICAgICAgICAgICAgLy8gaSA9IIp3lE6CzCBpbmRleAogICAgICBm
b3IoIGogPSAwIDsgaiA8IDUgOyBqKysgKSB7ICAgICAgICAgICAgICAgICAg
ICAgICAvLyBqID0gg0+Di4Fbg3aCzCBpbmRleAogICAgICAgIGdyYWRlW2ld
ICs9IHNpemVbaV1bal07CiAgICAgICAgZ3JvdXBbal0gKz0gc2l6ZVtpXVtq
XTsKICAgICAgICBzdW0gKz0gc2l6ZVtpXVtqXTsKICAgICAgfQogICAgfQoK
ICAgIFN5c3RlbS5vdXQucHJpbnRsbiggIiNBdmVyYWdlIG51bWJlciBvZiBz
dHVkZW50cyBpbiBhIGdyb3VwLiIgKTsgICAgIC8vIJFTineUToFFg0+Di4Fb
g3aC8JLKgrWCvYJQg0+Di4Fbg3aTloLogsyVvYvPineQtpCUCiAgICBTeXN0
ZW0ub3V0LnByaW50bG4oIE1hdGgucm91bmQoKGZsb2F0KXN1bSAvIChncmFk
ZS5sZW5ndGggKiBncm91cC5sZW5ndGgpKSApOwoKICAgIFN5c3RlbS5vdXQu
cHJpbnRsbiggIiNBdmVyYWdlIG51bWJlciBvZiBzdHVkZW50cyBmb3IgZWFj
aCBncmFkZS4iICk7IC8vIIp3lE6VyoLJjKmCvYJQg0+Di4Fbg3aTloLogsyV
vYvPineQtpCUCiAgICBmb3IoIGkgPSAwIDsgaSA8IDMgOyBpKysgKSB7CiAg
ICAgIFN5c3RlbS5vdXQucHJpbnQoIEludGVnZXIudG9TdHJpbmcoTWF0aC5y
b3VuZCgoZmxvYXQpZ3JhZGVbaV0gLyBncm91cC5sZW5ndGgpKSArICIgIiAp
OwogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKCk7CgogICAgU3lzdGVt
Lm91dC5wcmludGxuKCAiI0F2ZXJhZ2UgbnVtYmVyIG9mIHN0dWRlbnRzIGZv
ciBlYWNoIGdyb3VwLiIgKTsgLy8gg0+Di4Fbg3aVyoLJjKmCvYJQg0+Di4Fb
g3aTloLogsyVvYvPineQtpCUCiAgICBmb3IoIGkgPSAwIDsgaSA8IDUgOyBp
KysgKSB7CiAgICAgIFN5c3RlbS5vdXQucHJpbnQoIEludGVnZXIudG9TdHJp
bmcoTWF0aC5yb3VuZCgoZmxvYXQpZ3JvdXBbaV0gLyBncmFkZS5sZW5ndGgp
KSArICIgIiApOwogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKCk7CiAg
fQp9Cg==

俺超優しい！

問3

与えられた配列の最大値，最小値を求めるプログラム MaxMin.java を完成し，結果の出力と一緒に提出せよ。

解答

ソースコードをちょっと加工してまーしゃるだんぷした。まーしゃるだんぷってキャッシュとかに便利だよね。

\004\010[x\"\a//\"-\227^\202\246\202\347\202\352\202\275\224z\227\361\202\314\215\305\221\345\222l\201C\215\305\217\254\222l\202\360\213\201\202\337\202\351\201B\"\a//\"\fdata[0]\"G\202\360\202\334\202\270\201C\215\305\221\345\222l\201C\215\305\217\254\222l\202\314\214\363\225\342\202\306\202\265\202\304\215l\202\246\201C\221\274\202\314\221S\227v\221f\202\306\224\344\212r\202\265\202\310\202\252\202\347\201C\"\a//\"!\215\305\217I\223I\202\310\215\305\221\345\201C\215\305\217\254\222l\202\360\223\276\202\351\201B\"\a/*\"\006=\"\t\217o\227\315\"\006=\"\010MIN\"\006=\"\0063\"\010MAX\"\006=\"\a95\"\a*/\"\nclass\"\vMinMax\"\006{\"\vpublic\"\vstatic\"\tvoid\"\nmain(\"\rString\"\targs\"\006)\"\006{\"\010int\"\tmin,\"\tmax,\"\ai;\"\nint\"\tdata\"\006=\"\006{\"\01039,\"\01022,\"\01095,\"\01019,\"\a9,\"\01065,\"\01018,\"\01025,\"\01028,\"\01079,\"\a3,\"\01013,\"\01051,\"\a35\"\a};\"\010min\"\006=\"\rdata[0];\"\a//\"\006i\"\a==\"\0060\"\010max\"\006=\"\rdata[0];\"\a//\"\006i\"\a==\"\0060\"\tfor(\"\006i\"\006=\"\0061\"\006;\"\006i\"\006<\"\020data.length\"\006;\"\010i++\"\006)\"\006{\"\a//\"\0061\"\a<=\"\006i\"\a<=\"\rlength-1\"\aif\"\r(data[i]\"\006<\"\tmin)\"\010min\"\006=\"\rdata[i];\"\aif\"\r(data[i]\"\006>\"\tmax)\"\010max\"\006=\"\rdata[i];\"\006}\"\030System.out.println(\"\t\"MIN\"\006=\"\006\"\"\006+\"\010min\"\a);\"\030System.out.println(\"\t\"MAX\"\006=\"\006\"\"\006+\"\010max\"\a);\"\006}\"\006}

問4

与えられた配列に対して，値の大きい順に並べ替えるプログラム Sort.java を完成し，結果の出力と一緒に提出せよ。

解答

これはまたバブリーなソートですね、と思ったらWikipediaの方法よりもスワップが少ないようになっている。

バブルソートとは、簡単に実装できるからと、潤沢に計算資源を使いまくるバブル全盛の日本のような豪快さからバブルソートと呼ばれる(大嘘)。しかし不安定なバブル経済とは違って安定ソートである。

バブルソート - Wikipedia

今度はソースコードをシーザー暗号にしてみた。

48%彡・・・・・戀・盲・・窯・爺・・伯・塲・杢・・・44%ifyf`5b%33%ifyf`qjslym26b%・盲・・豆・妹提・遅・・・44%〓・・・帽毛・・・・・通爺窯・炊・・・44%〓・・・通爺窯・%ifyf`5b%・・託松・・・ifyf`5b%・通爺窯・・・・・・・44%〓・塗・・・・・-ifyf`6b33ifyf`qjslym26b.・盲・・通爺窯・炊・・・44%〓・・・通爺窯・%ifyf`6b%・・託松・・・44%栽質・・・・霧・・・4/B%杯慥%B>:%<>%;:%:6%8>%8:%7=%7:%77%6>%6=%68%>%8/4hqfxx%Xtwy%€%%uzgqnh%xyfynh%{tni%rfns-%Xywnsl`b%fwlx%.%€%%%%nsy%%%rf}1%rf}dnsij}1%yru@%%%%nsy%%%n1%o@%%%%nsy`b%%ifyf%B%€%8>1%771%>:1%6>1%>1%;:1%6=1%7:1%7=1%<>1%81%681%:61%8:%・%%%%ktw-%n%B%5%@%n%A%ifyf3qjslym26%@%n00%.%€%%%%%%%%44%5%AB%n%AB%qjslym27%%%%%%rf}%B%ifyf`nb@%%%%%%rf}dnsij}%B%n@%%%%%%ktw-%o%B%n06%@%o%A%ifyf3qjslym%@%o00%.%€%%%%44%n06%AB%o%AB%qjslym26%%%%%%%%nk-%rf}%A%ifyf`ob%.%€%%%%%%%%%%rf}dnsij}%B%o@%%44%通爺窯・・・・・・・・綻票%%%%%%%%%%rf}%B%ifyf`ob@%%44%通爺窯・綻票%%%%%%%%・%%%%%%・%%%%%%nk-%rf}%C%ifyf`nb%.%€%%%%%%%%yru%B%ifyf`rf}dnsij}b@%%44%搾謄墻蕗・通爺窯・壟冥%%%%%%%%ifyf`rf}dnsij}b%B%ifyf`nb@%%%%%%%%ifyf`nb%B%yru@%%%%%%・%%%%・%%%%ktw-%n%B%5%@%n%A%ifyf3qjslym%@%n00%.%€%%%%%%%%%%44%爺・・伯・啾騰%%%%%%%%X~xyjr3tzy3uwnsy-%ifyf`nb%0%'%'%.@%%%%・%%%%X~xyjr3tzy3uwnsyqs-.@%%・・

問5

教科書p.128（第六章の最後）にこんなことが書いてある。

  • 6- 1-2でも述べたように「，」（カンマ）を使うと，for文の初期化式と更新式に複数の文を記述することができます。この時，更新式に文を複数記述すると，判定式でfalseになった時（forループが終了する時）にも処理を実行させられます。例えば，1から1000までの足し算を行なうプログラムは，次のように書くことができます。
    • for( i = 1 ; i < 1000 ; x += i, i++ ) {
  • さて，上記の教科書の記述に対して問題です。上記の記述は正しいかどうか，頭で考えよ（実際にプログラムを書いて動かすのではなく）。仮に誤っている場合「どこが誤っているのか」及び「何故，そのような誤りを彼はしたのか」を推測せよ。

解答