2009年春改訂
基本情報技術者試験
ってか色々変わっちゃうよね。どうしよう、範囲広くなるらしいし。
もっと早く取るべきだったんじゃないの俺？
まーいっか！
範囲が広かろうが狭かろうが情報系の人間なんで受かって当然なんすよ
今受けたら多分落ちるけどorz
授業午後から
なのに俺学校来たの朝9時orz
いーもん！標準C++読むからいーもん！
はぁ、家帰って寝たい
スピード勝負
アルゴリズムに大切なことは
・わかりやすい
・メモリ使用量が少ない
・速い
・スタイリッシュ＆エレガント←
4つ目要るのか？
そげなことは置いときまして
『100万個のデータに対して、線形探索と二分探索ではどちらが速いのか？』
って問題があるわけですが、まぁ考えるまでもなく二分探索でしょう
データ数n、探索する数mの時、
線形探索の場合はO(nm)
二分探索の場合は、探索前にソートする必要があるのでO(nlogn) + O(mlogn)
ぶっちゃけ、探索数が少ないときは線形探索の方が速いんだよな
探索数が少ないとき、二分探索全体では（ソートする時間） > （探索する時間）だからだろうね
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <mmsystem.h>
const int SEARCH = 500000;
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main(void)
{
int *data;
int search[SEARCH];
int i, j, count = 0;
FILE *fp;
int start, end;
// for (i = 0;i < 1000000;i++)
// printf("%d\n", rand()%5000000);
data = (int*)malloc(sizeof(int)*1000000);
fp = fopen("rand_data.txt", "r");
srand(10);
for (i = 0;i < SEARCH;i++)
search[i] = rand()%5000000;
for (i = 0;i < 1000000;i++)
fscanf(fp, "%d", &data[i]);
/*
///////////////////////////////////////////////////
count = 0;
start = timeGetTime();
for (i = 0;i < SEARCH;i++) {
for (j = 0;j < 1000000;j++) {
if (search[i] == data[j]) {
count++;
break;
}
}
}
end = timeGetTime();
printf("liner search\n");
printf("Match : %d\n", count);
printf("Time : %d msec\n", end-start);
///////////////////////////////////////////////////
*/
start = timeGetTime();
count = 0;
qsort(data, 1000000, sizeof(int), cmp);
for (i = 0;i < SEARCH;i++) {
if (bsearch(&search[i], data, 1000000, sizeof(int), cmp) != NULL)
count++;
}
end = timeGetTime();
printf("quick sort + binary search\n");
printf("Match : %d\n", count);
printf("Time : %d msec\n", end-start);
///////////////////////////////////////////////////
return 0;
}
たしてたして
C++の授業で使う教科書は『C++＜オブジェクト指向について』なので、図書館で適当に借りてきましたよ
やさしいC++（の初版orz）
とりあえず、家に帰ってから目を通してみたけど明日返そうと思う（笑）
やさしい！本当にやさしい！でもやさしさだけじゃダメなんだぜ！
プログラミング関連の本は2ヶ所に分かれていたのを忘れておりました、片方の本棚には基本的なのがいっぱいで、もう片方のにはマニアックな本が置いてあります。そっち側のやつとってこりゃ良かったぜ
っていうかcinとcoutはオブジェクトだったんすね。なんか演算子的なモノかと思ってたんですけど、cinはistreamオブジェクトでcoutはostreamオブジェクトなんですってー
そいで、ファイル操作には派生クラスのifstreamとiostreamを使う、というわけね
Perlはリファレンスが絡んできたあたりからソースが見づらくなってくるのでとりあえずお預けにしてます
オートマトン理論の演習もしなくちゃな
レポートの印刷もしなくちゃな
言語の定義例
記号列xにおいて、xR = xを満たすものと回文と呼ぶ。
L = ｛ x | x ∈Σ* , xR = x｝
回文の再起的定義を書きなさい
【解】
(1)，εは回文である。
(2)，x ∈Σ*が回文なら、任意のa ∈Σに対して、axaは回文である。
(3)，上の(1),(2)で定義される記号列のみが回文である。
この解は正しいか？
正しくない。多分・・・
Σ = { a , b , c , … , z } とする。
εは回文なので(2)を利用すると、aa、bb、ccなどの回文ができる。
さらに続けると、abba、cdeffedcなどの回文が数多く出来る。
しかし、この定義では奇数長の回文（abaなど)は出来ない。
よって正しくない。
多分。
(1)の条件を、「εと長さ1の記号列は回文である」にすればいいのかな？
明日の授業でわかると思う。
それにしても、カントールの対角線論法がいまだによくわからない
まぢ鬼盛り
親知らずの治療に行ってきたよ！
開口一番（口を開けただけに）
『親知らずでっかいねぇ～』
でかいですかそうですか
『顎もでっかいねぇ～』
でかいですかそうですか
『顎のレントゲンとったけど、顎骨が大きいからあんまりよく写んなかったね』
でかいからですかそうですか
案の定虫歯でしたけどね
『君の親知らずちゃんとした形してるから余計磨きにくいんだろうね』
『普通の人の2倍ちかい大きさだよ』
って言われた
そのあとはガリガリ削って、型とって、パテみたいなのを削ったところに鬼盛りして帰ってきました。
抜かなくて良いって！良かったね！
また今度行ったときにかぶせてもらおう