Fisher-Yatesのシャッフルアルゴリズムをc言語で実装 配列の要素をランダムに並べ替える手法として、Fisher-Yatesのシャッフルアルゴリズムが有名ですね。 ランダムに選ばれた配列の要素を、配列の末尾の要素・・・
「データ構造」の記事一覧
[c言語]素数をプログラミングで求めてみる
[c言語]素数をプログラミングで求めてみる 素数は、1より大きな整数で、1と自分自身以外に約数を持っていない(1と自分自身以外の自然数でも割り切れない)数です。 まずは、下記のように、計算量が大きくなりますが、素直に1と・・・
[c言語]ナップザック問題を動的計画法でコーディング
再帰を使った場合 参考:[c言語]フィボナッチ数列を動的計画法でコーディング 容量Wmaxのナップザックに、N個の品物を入れる。 品物iの重さがw[i] 価値がv[i]であるときに、容量Wmaxを超えない、 かつ、価値が・・・
最大部分配列問題をc言語で実装してみる
全探索での実装 下記のように2重ループ処理をして、全探索をします。 全ての組み合わせの合計値を順次算出して、最大値を更新していきます。 getMax()については、別途関数として実装しています。 サンプルコードを参照して・・・
[c言語]フィボナッチ数列を動的計画法でコーディング
再帰を使った場合 参考:[c言語]ナップザック問題を動的計画法でコーディング 下記がサンプルコードになります。 f(n)からf(n-1)とf(n-2)を再帰的に呼び出します。 重複計算もあって、n=45で13秒かかってい・・・
[c言語]バイナリーサーチ(二分探索)のサンプルコード
バイナリーサーチ(二分探索) まずは、下記のように、ソート・ユニークされた配列を対象にします。 int arr[MAX] = {1,3,5,6,7,9,10,11,22}; バイナリーサーチは、サーチ対象の中央を起点とし・・・
隣接リストで幅優先探索をc言語で実装(サンプルコードあり)
幅優先探索をc言語で実装 隣接リストで、上記の経路を表現します。 深さ優先探索の時と経路は同じにしています。 参考:[c言語]隣接リストで深さ優先探索を実装 #define ROW_MAX 6 #define COL_M・・・
[c言語]隣接リストで深さ優先探索を実装
隣接リスト 今回は、上記の経路(有向グラフ)を、隣接リストで表現します。 #define ROW 6 #define COL 3 int pathList[ROW][COL] = { {0}, {2, 3, 0}, {4・・・
ハッシュテーブルをc言語で実装(サンプルコードあり)
ハッシュテーブルをc言語で実装 今回は下記のようなハッシュ関数を採用することにしました。 とてもシンプルです。 キーとなる入力文字列の各文字のアスキーコードの和を求めて、ハッシュテーブルのテーブルサイズで割った余りをハッ・・・
連結リスト(双方向)でpushとpopをc言語で実装(サンプルコードあり)
連結リスト(双方向)でpushとpopをc言語で実装 連結リスト(双方向)でpushとpopをc言語で実装してみました。 下記の記事で、連結リスト(片方向)でpush/popを実装しています。 参考:連結リスト(片方向)・・・