応用情報技術者試験の午前問題の前半の方にアルゴリズムとプログラミングの範囲にプログラミングの問題があります
問題を解いてみた感じだと
プログラミングに必要なデータ構造やデータ型の知識、プログラムの特性が問題になってます
更にJava、JavaScriptの機能や記述の説明ですね
正直、大学で3年情報系を勉強してきましたがこの範囲は全然わかりませんでした
プログラムの特性だけならなんとかなりそうですが、言語の説明となると難しいですね
そこまで詳しく勉強できていませんでした
範囲が広すぎると思います
というわけで本題のこの範囲を勉強する必要があるかどうかですが
勉強しなくていいと思います
応用情報技術者試験ドットコムにも8問しかないので主題頻度はかなり低いです
さらに今年の春に出題されているので次に出題されるのは2～3年あとになると思います
出ての1問なので捨てましょう
でも再帰プログラムとかデータ型の特徴は他の範囲にも関係してそうなので勉強しておいてもいいと思います
前の金土日がツタヤのレンタルDVD半額期間でハリウッドのゴジラとジャスティスリーグを借りた
昨日ジャスティスリーグ見ようとしたら日本語吹き替えも字幕もない
ありえないでしょう
せっかく楽しみにしてたのに話の内容が全く理解できないのであきらめてゴジラ見ました
うーん
ちゃんと確認せずに借りた俺も悪いんだけど日本のレンタルショップでなんで日本人が見れないDVD置いてんだったて話ですよ
クソがァ！
ちなみにゴジラは思っていたより怪獣バトルがなくてちょっと物足りなかった
キングオブモンスターではもっとバトルがあるのを期待してます
今日は大学もバイトもオフの日
午前は部屋の掃除してちょっとお昼寝
起きてから1時間サイクリング
クソ暑かった
30度超えてたらしい
まだ五月なのにね
五月と言えば初鰹が旬らしい
日本酒とカツオのたたき買って晩酌ですわ
明日はバイト
また暑いみたい
熱中症に気を付けようね
探索法
探索とはｎ個の入力データから値ｘと一致するデータを見つける操作のこと
線形探索
データの先頭から一つずつチェックしていく探索方法
最短で探索が完了するのはデータの先頭に探索する値が格納されている場合で時間計算量はO(1)
最長で探索が完了するのはデータに探索する値が含まれていない場合で時間計算量はO(ｎ)
データが大きくなればなるほど実行時間も長くなる
2分探索法
データがなんらかの順で並んでいるときに利用される
例えばデータが昇順で配列されているとき、探索したいデータと配列の真ん中のデータを比較する
データが等しければそこで探索は終了
データが探索したいデータより大きければ真ん中より前半を、小さければ真ん中より後半を同様に探索する
このように配列の半分にして、その前半か後半をまた半分に、そのまた前回か後半を半分にしていき探索を行う
平均時間計算量はO(logn)（説明は省略）
ハッシュ法
ハッシュ法はハッシュ関数によってデータが格納された配列に適用できる
ハッシュ関数とはhash(x)と表され、例えばhash(x)=(xをデータ数×1.5で割った余り)のような形で定義される
格納の例としては
ハッシュ関数で求めた値が3だったとき、添え字が3の配列をチェックする
この配列が空なら格納し、空でないなら次の配列(3＋1)をチェックする
これを繰り返し格納場所を見つける
ただし、配列のデータ数(入力データ×1.5)が決まっているので配列の最後まで行って格納場所がない場合は先頭に戻る
探索では格納と同様にハッシュ関数を用いて得られた値の添え字の配列をチェックする
探索する値と配列に格納されているデータが異なる場合は次の配列をチェックする
時間計算量はハッシュ関数によって変化する
ハッシュ関数で得られる値が重ならないような関数であれば時間計算量はO(1)
最後に
この3つの探索法では線形探索＞2分探索法＞ハッシュ法の順で実行時間が短い
しかし、データ数によっては2分探索法もハッシュ法もそんなにかわらず高速
ソートとは
与えられたデータを決められた順で並べ替えること
選択ソート
