『C言語による最新アルゴリズム事典』

奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年，ISBN4-87408-414-1，2400円

大きな画像（1.1M）

1987年10月にPascalを使った『コンピュータ・アルゴリズム事典』を，1991年2月にその改訂版としてANSI C言語を使った『C言語による最新アルゴリズム事典』を出版しました（いずれも技術評論社）。そのサポートページをつくろうと思いながら多忙のためなかなかできませんでした。とにかく始めなければ……というわけで，サポートページまがいのものを作ってみました。

石田晴久ほか『コンピュータの名著・古典100冊』（インプレス，2003年）に選んでいただきました。100冊といっても日本人の書いたものは20％しかなく，たいへん恐縮しています。

Frequently Asked Questions

どの銘柄のC言語ですか？

ほぼ当時のANSI Cドラフトに基づいていますが，チェックには当時のTurbo Cを使いました。今はgccを使っているので，今ならもう少し違った書き方にしたと思うところもあります。

ソースコードの入手先は？

ここ に置いておきます。 algo.lzh がシフトJISコードのものです。

配布ソースコードのインデントが本と違うようですが？

すみません，当時は DOS 上の某エディタを使っていたのでタブが4桁になっています。タブを4桁の空白に直すための簡単なフィルタ detab.c を作っておきました（バグっていました ^^; ご連絡ありがとうございます）。

バグ

初刷のバグです。ほとんど直っているはずです。

扉裏:
UNIXは日本ではAT&T社の登録商標ではありませんでした. 日本マランツが高級オーディオアンプの名前に使っていたと思います.
p. ii, 凡例:
＼ (バックスラッシュ) は日本製のパソコンでは ￥ と表示される → これはフォント次第ですね. 正確な表現ではありませんでした.
p. 15, 円周率, 18行目:
a1 = 1, b1 = …… → a0 = 1, b0 = ……
なお21行目の式の第3辺の和で k = 0 の項だけは第2辺の流儀で計算します。
p. 48, 行列, 中ほど:
a[0] から a[9] まで → v[0] から v[9] まで
p. 50, 12行
「ncolは行の数」とあるのは「列の数」です (Thanks: 津留さん)
p. 65, circle.c，ellipse.c
ここをご覧下さい。
p. 74, 合同式, ディスケット記号のすぐ上:
O(log n) の時間で x が求められる. → O(log n) の時間で x が求められる [互除法によるアルゴリズムも O(log n) である].
p.82 本文最後の行
2/3 → 3/4 (Thanks: 首藤さん)
p.87
19行目「この両辺に c_k' を掛けて」の c_k' は ω^{-k'h} の間違いです。 k，k' の範囲が書いてありませんが 0,1,...,n-1 です。 最後から2行目の N は n です（プログラム中では N となっているものです）。 この N = 2^k の k は任意の整数という意味で，上で使った k とは無関係です (Thanks: 種石さん)
p. 99, 式の評価, プログラム eval.c 行22:
int sign; → int sign = '+';
p. 135 プログラム36行目
s > 1 → s >= 1 (Java版サポートページ「p.154 NormalRandom.javaリスト34行目」参照)
p. 145--, simplex.c
手抜きをしているところがあり，結果は必ずしも正しくありません。 どなたか直していただければ助かります。
pp. 152--153, 選択
このままでは i や j が配列の範囲を超えてしまうことがあります。 12行目は等号付き不等号にし，16〜17行目を if (i <= k) left = j + 1; if (k <= j) right = i - 1; に訂正します。
p. 153, 選択ソート, 1〜2行目:
安定である（……）→削除 プログラムリストの直前に「次に挙げる選択ソートアルゴリズムは安定でな い（安定にすることは可能である）
p. 154, 素因数分解, 3行目:
p が合成数 x の素因数なら... → 合成数 x は p ≦ ルートx を満たす素因数 p を持つ.
p. 159, 挿入ソートの解説中の Pascal コード（バグの例）
j := j + 1 は j := j - 1 の間違いです（いずれにしても間違いの例ですが ^^;）
p. 162, 対数, 11行目の式
右辺全体を2倍して下さい.
p. 184, getnum
エラーかどうかを errno で判断してしまっていますが，errno はもともと他の方法でエラーが起こったことがわかったときにエラーの種類を調べるために使うもので，エラーでなくても errno がセットされることがありえます。errno を使わないようにするのが望ましいのですが，リストの15行目で errno = 0; を挿入するだけでもとりあえずいいかもしれません (Thanks: 養老さん)
p. 212 weights.c の6行目
char side[2][3] = { "左", "右" }; は文字コードがUTF-8の場合は char side[2][4] = { "左", "右" }; としないと動作がおかしくなります。あるいはもっとわかりやすく char *side[2] = { "左", "右" }; とするべきでした。
p. 213 最下行
次の2行 → 行25，26 (Thanks: 土村さん)
p. 232, 71行
return p_beta(1 - p, n - k, k + 1); の間違いです。
p. 252, distsort.c リスト13行目
x = a[i] - MIN; b[--count[x]] = a[i]; に直してください.
p. 262，5行目
反値幅→半値幅 (Thanks: 丸山さん)
p. 263, ポリトープ法, リスト56行目:
kbest = kworst1 = 0; kworst2 = 1; 同じく63行目の > を >= に訂正します。
p. 283, 有限体, 下から7行目:
因数分解できない多項式をInd既約多項式きやくたこうしきという. → 因数分解できない多項式を既約多項式という.
p. 313
本文 log((1-x)/x) → log(x/(1-x)) プログラムのほうは正しくなっています。なお，乱数 rnd() がぴったり 0 になれば log(0) つまり -Inf になりますが，その対策は省略してあります。
p. 334, crc16.c 解説2行目:
(XMODEM方式) → 削除
p. 334, crc16.c 解説5行目:
XMODEM方式では → XMODEM方式にするには crc1() で
p. 340, 数式
積分の上限は ∞ ではなく x です (Thanks: 土村さん)
p. 344
間違っているわけではないものの，式の導出が一部ちぐはぐなところがあります。自明かもしれませんが，とりあえず。
p. 347, fft.c
nは2の整数乗に限る→n（≧4）は2の整数乗に限る
[参考] n=2のときは例えば次のようにして求められます： 
int fft2(int n, float x[], float y[])   /* n=2のFFT */
{
    float t;

    t = x[0];  x[0] += x[1];  x[1] = t - x[1];
    t = y[0];  y[0] += y[1];  y[1] = t - y[1];
    if (n == 2) {
        x[0] /= 2;  x[1] /= 2;  y[0] /= 2;  y[1] /= 2;
    } else if (n != -2) {
        return 1;  /* エラー */
    }
    return 0;  /* 正常終了 */
}
p. 347, fft.c 20-23行目:
無駄がありました。次のように書き換えられます： 
for (i = 0; i < n4; i++) {
   sintbl[n2 - i] = sintbl[i];
   sintbl[i + n2] = - sintbl[i];
}
p. 349 下
c63=3 → c61=3 (Thanks: 中島さん)
p. 357
Gauss-Jordan法のプログラムの「注」は無視してください（j = k + 1 をそのまま j = 0 に直すと結果が違ってきます）。
p. 359, gray2.c
飯田様からもっと良い方法を教えていただきました： 
unsigned int num_to_Gray(unsigned int x)
{
    return x ^ (x >> 1);
}

unsigned int Gray_to_num(unsigned int x)
{
    unsigned int ret = x;

    while (x >>= 1)
        ret ^= x;
    return ret;
}
p. 363, 下3行目
中辺 c2 (...)2 + ... + xn2 は括弧が抜けています: c2 ((...)2 + ... + xn2) が正しい式です (Thanks: 津留さん)
p. 368
bitio.c で変数 bitbuf はビット入力・ビット出力で共用しています。 圧縮・復号用には問題ありませんが，putbit(getbit()) のような使い方をするためには putbitbuf，getbitbuf のように二つに分ける必要があります（Thanks: 山田さん）
p. 375 表のすぐ下
np-1=39 → 29 (Thanks: 光成さん)
p. 399 mrnd.c
((1UL << 32) - 1) という書き方が2個所で使われていますが，素直に 0xffffffff と書くべきでした。 ANSI/ISO C/C++/C99 では unsigned long が32ビットの場合 1UL << 32 は undefined（未定義）とされています。 実際，x86 では << の右オペランドの下位5ビットしか有効でない実装が自然のようです。 (Thanks: 光成さん)
p. 400, Mandelbrot
「フランス→ポーランド」→「ポーランド→フランス」
p. 410, NP完全, 第3段落の最初:
ある問題が → クラスNPに属するある問題が
p. 410, NP完全, 第4段落の最初:
Yes, noで答える問題ではないが → Yes, noで答える問題ではない場合も含め
p. 415, eigen.c 17行目:
while (fabs...) → while (j > 0 && fabs...)
p. 420, shelsort.c 6行目: (これは重大なバグでした^^;)
h = 1; → h = 13;
p. 420, shelsort.c 7行目: (たいして違いはありませんが一応)
(h <= n) → (h < n)
p. 429, t 分布
上の二つの積分の積分区間が t から ∞ となっていますが，0 から t の間違いです。

追加情報

Last modified: