『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. 213 最下行
次の2行 → 行25，26 (Thanks: 土村さん)
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. 334, crc16.c 解説2行目:
(XMODEM方式) → 削除
p. 334, crc16.c 解説5行目:
XMODEM方式では → XMODEM方式にするには crc1() で
p. 340, 数式
積分の上限は ∞ ではなく x です (Thanks: 土村さん)
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. 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)

追加情報

奥村晴彦

Last modified: 2007-12-16 15:53:12