人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。この問題をC言語の勉強がてらやってみました。幅優先探索とか色々方法はあるみたいですが、A-starなんてアルゴリズムがあるらしく、折角なので調べながらやってみました。A* - Wikipedia #inclu…

http://www.geocities.jp/ky_webid/algorithm/022.htmlヒープソートです。木構造に見立てた？ソートのようです。読んでみたのですが、ややこしい・・・。もの凄いややこしいです・・・。ヒープの構築であるinsert_heap関数はわかりました。ですがヒープから…

http://www.geocities.jp/ky_webid/algorithm/021.htmlマージソートです。いっぱいありますね、ソートって。 マージソートの最大の特徴は、配列のような直接アクセス（配列であれば添字によるアクセス）ができないリスト構造であっても、ソートを行える点に…

http://www.geocities.jp/ky_webid/algorithm/020.htmlクイックソートの話です。もの凄いアルゴリズムですね。コレ。これを考え付いた人凄いです。普通こんなの思いつかないって。分割したデータは、中央に向かって探索、交換していき、再帰でそれを最後の要…

http://www.geocities.jp/ky_webid/algorithm/019.html凄く単調な暗号化ですね。文字をずらしたり置き換えたりするだけです。さっそく作ってみましょう。 #include <stdio.h> #include <string.h> int main (void) { char enc[100]; size_t i; int key = 3; puts("値を入力して</string.h></stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/018.html暗号というか単にXORが同じ演算を二回行うと元の値に戻ることを利用しただけのものですね。実際にプログラムを作って試してみましょう。 #include <stdio.h> #include <string.h> int main (void) { char enc[100]; size_t </string.h></stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/016.htmlいわゆるツリー構造と呼ばれる物です。概念としては良く分かりました。が、実際にどう実装するかのイメージがつきません。ということで今回は先に解答例をじっくり読んでどういったものかを理解した上で…

http://www.geocities.jp/ky_webid/algorithm/015.html前回に引き続き、ハッシュ探索のお話です。今回はオープンアドレス法という処理方法になります。チェイン法と違って、同じ格納位置が生成されたときに元のハッシュテーブルを拡張し、データの重複を防ぎ…

http://www.geocities.jp/ky_webid/algorithm/014.htmlハッシュの話が出てきました。LL等、他の言語では言語仕様として存在しているものですね。Cの場合は自分で実装しないといけません。どういう仕組みなのかちゃんと理解するためにもここはマスターする必…

http://www.geocities.jp/ky_webid/algorithm/013.html検索結果位置を保存しておくということですか、やってみます。リスト構造は循環リスト再実装 - (void*)Pないとで作った物を利用します。 #include <stdio.h> #include <stdlib.h> struct LIST { int data; struct LIST *nex</stdlib.h></stdio.h>…

文字列のポインタ配列をソートするにはどうしたらいいんだろうと思って実装してみた。 #include <stdio.h> #include <string.h> #include "mylib.h" void shell_sort (char **data, int array_size) { int h; int i,j; if ( array_size <= 1 ) { return; } for(h=1; h<array_size; h=h*3+1); for(h/=3;h>0;h/=3){ f</array_size;></string.h></stdio.h>…

循環リスト - (void*)Pないともう少しシンプルに実装し直してみます。前の時はlast変数を用意してリストへの追加が最後尾になるように実装したのですが、あまり必要なさそうなので今回は無しでやります。 #include <stdio.h> #include <stdlib.h> struct LIST { int data; struc</stdlib.h></stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/012.html逆方向にも参照できる双方向リストですね。循環リストの拡張でやってみます。 #include <stdio.h> #include <stdlib.h> struct LIST { int data; int last; struct LIST *next; struct LIST *prev; }; typedef struct LIST </stdlib.h></stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/011.html片方向の線形リストの最後の要素が、一番最初の要素を指すわけですね。似たような実装になるんでしょうか。とりあえず実装してみます。 #include <stdio.h> #include <stdlib.h> struct LIST { int data; int last; struct </stdlib.h></stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/010.htmlさてとうとうmalloc関数を使って動的に拡張していくタイプの処理に入りました。このあたりのリスト構造を極めれば今後割りと何でも作れそうな気がします。ということでここは何としてもキッチリと押さえ…

http://d.hatena.ne.jp/pknight/20090704/1246706552ちゃんとループするように再実装してみました。 #include <stdio.h> typedef struct { int data[100]; int end; int start; } queue; void enqueue (queue *q,int data) { if ( (q->end + 1) % 10 == q->start ) { </stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/009.htmlスタックとは違い、データの追加は後ろですが、データの取り出しは先頭からになります。 #include <stdio.h> typedef struct { int data[100]; int end; int start; } queue; void enqueue (queue *q,int data) {</stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/008.htmlデータの扱い方の話ですかね。簡単に言うと配列の後ろに追加、また後ろから削除、という感じでしょうか。とりあえず適当に実装してみます。 #include <stdio.h> typedef struct { int data[100]; int index; } st</stdio.h>…

http://www.geocities.jp/ky_webid/algorithm/007.html 二分探索法は、あらかじめ配列を昇順あるいは降順にソートしておくことが前提になります。そして、まず配列の中央にある要素を調べます。もし目的の値と異なっていれば、目的の値とその位置にある値と…

http://www.geocities.jp/ky_webid/algorithm/006.htmlソートの話は一旦置いておいて今度は探索アルゴリズム。 これは、データ列の先頭から末尾に向かって１つずつ探索していくアルゴリズムです。運良く、先頭近くで見つかれば非常に高速だし、運悪く、末尾…

http://www.geocities.jp/ky_webid/algorithm/005.htmlシェルソートのお時間です。 シェルソートは、ある一定距離だけ離れた要素同士で交換処理を行い、この距離を少しずつ縮めていき、最後には普通に挿入ソートを実行することでソートを行います。 なるほど…

http://www.geocities.jp/ky_webid/algorithm/004.html挿入ソートの実装です。 1番目と2番目を比較し、順番が逆であれば入れ換える。次に、3番目の要素を、正しい順に並ぶように「挿入」する。（挿入する際、右側のデータを後ろに一つずつずらす）この操作で…

http://www.geocities.jp/ky_webid/algorithm/003.htmlお次は選択ソートの話です。 データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す…

http://www.geocities.jp/ky_webid/algorithm/002.html バブルソートとはソートアルゴリズムの中でも基本中の基本。別名として単純交換法とか基本交換法と呼ばれるらしい。 バブルソートは、隣接する要素同士を比較し、目的の順序に並んでいなければ、その要…

http://www.geocities.jp/ky_webid/algorithm/001.htmlある値AとBを交換しようと思ったら一時変数に代入しないと交換できない work = a; a = b; b = work; 因みにPerlという言語の場合は一時変数を用意しなくても代入できる。 ($a,$b) = ($b,$a); 一時変数を…