ー須■ から P ' Q ' の垂線方向に距離 v だけ延ばした X) の加重平均をとってやればよいて、しょ 点を X ′としています。 フ。すなわち , ・ u く 0 DIST = ・ 0 坙 u 坙 1 ・ u > 1 今度はべクトルの組が複数になった場合 という計算式て、 X ' が求まります。 DIST は第 2 式に示すように , 点 X と線分 こて、 , 新は i 番目のべクトル組の重み て、す。べクトルの組それぞれについて , 則 Q との距離て、す。 0 坙 u 坙 1 なら , X からの垂 て、 , 次の計算式て、求めます。 己の方法て、 X から X ' を求め , その変位 ( X ' 線の足が線分上にあるのて、 , 距離は v の絶対 正しい 1 次変換 Fig. 2 座標の決め方 QI ー PI 「 a 十 DIST Pil ・ は一 0 い・ iWl(X'i—X) 複数のべクトルによる変形 1 三ロ List を り・タ . 。あの一 式換換メる 列変変ラめ 行逆逆パ求 十 X ・ 0 十し・ , + し Q) をレ・ 0 O ↓し 0 ーより朝 00 -4 れ 0 ー 8 0 ー 1 ワ 00 0 src 当・・■ ・第■第第 隙間が生じる List 現実的な 1 次変換 1 : double det = a * d ー b * c; 2 : i f (det ! = の { double ad ニ d / det; double bd : -b / det; 3 : -c / de t : doubl e dd = a / de t : 4 : double cd / / 生成画像の幅と高さ hd を求める (int)max(fabs(a*w + b*h), fabs(a*v-b*h)) : int wd (int)max(fabs(c*v+d*h), fabs(c*v-d*h)) : i n t hd = Pixel* dst ニ new Pixel[wd * hd]; 8 : for (int yd = 0 : Yd く hd; yd + + ) 9 : for ( i n t xd = 0 : xd く : xd + + ) { 〃画像の中心を原点にする int xd2 = xd ーⅶ / 2 : 13 : i nt Yd2 ま yd - hd / 2 : i nt x = ( i n t) ()d * xd2 + bd * yd2) + / 2 ; i nt Y = ( i n t) ()d * xd2 + dd * Yd2) + れ / 2 ; 〃範囲のチェック 16 : if ( 0 く = x & & x く & & 0 ← Y & & y くれ ) 17 : dst[yd * + xd] ニ src[y * 十 X] : 18 : e ー se dst[yd * 記 + xd] 20 : 22 : } Fig. 3 バラメータの決め方 1 1 (b,d) 1 次変換 1 0 0 Fig. 4 モーフィングの原理 Fig. 5 2 枚の画像の合成 0 Pb Qb 0 ・ Qa X ・ P ・ 原画像 0 生成画像 48 C MAGAZINE 1993 7

C 言語プログラミングレッスン という形の if 文の意味は , 次のようになりま す。 条件 1 が成り立つ →処理 A 条件 2 カ城り立っ →処理 A 条件 1 も条件 2 も成り立たない →処理 B つまり , 次の if 文とまったく同じ意味を持っ ています。 if ( 条件 1 ) { 処理 A else if ( 条件 2 ) { 処理 A 「または」 Fig. 5 このように書く 0 0 0 0 0 0 0 ) 0 0 0 0 YES if 条件 1 』 条件 2 条件 1 NO 条件 2 処理 A else { YES 処理 B NO 処理 B 処理 A もう一度初めから読む 現在の時刻 ( 「時」だけでよい ) 【問題】 をキーポードから入力すると , 午前中→「おはようございます」 正午 →「お昼です」 午後 →「こんにちわ」 →「こんばんわ」 夜 それ以外→「時刻の範囲を越えていま とそれぞれ表示するプログラムを書い てださい。ただし 午前中 0 時から 11 時 正午 : 12 時 午後 : 13 時から 18 時 夜 : 19 時から 23 時 とします。 解答は本稿の最後にあります。 Fig. 7 List 4 をコンバイルすると・・・ A> lcc list4. c 15 : syntax error near ' ド list4. c 15 : syntax error near ' ) ' list4. c list4. c 15 : Warning: useless expresslon 15 : syntax error near ' ) ' list4. c syntax error near ' else' list4. c 17 : syntax error near ' 〉 ' list4. c 17 : list4. c 17 : Warning: useless expresslon 17 : syntax error near ' ) ' list4. c syntax error near ' else' list4. c 19 : syntax error near ' end Of fi list4. c 24 : else else { 処理 B 先に進む ササイズ よろしいて、すか。ちなみに縦棒い ) は「バー それて、は問題て、す。今回学んだことを使 ティカルライン」や「パイプ記号」 , また「オ って , 次の問題を解いてみてください。今 ア」と呼ばれています。 また , とくに縦棒ふたっ ' ' Ⅱ ' ' は「繙血」 回まて、のレッスンて、学んだ知識だけて、必ず 解ける問題なのて、挑戦してみましよう。 や「ロジカルオア ( logicalor ) 」などと呼ばれ い きなりテキストエデイタに向かって書いて ています。私はⅡのことを「または」と呼んて、 もいいて、すが , いったん紙に鉛筆て、書いて います (Fig. 5 ) 。 List 3 の実行結果は Fig. 6 みることをお薦めします。書きあがったら になります。 自分の手て、コンパイルして動かしてみまし if ( よくわからないⅡ疲れた ) { ー休みして , Fig. 6 List 3 の実行結果 A> lcc list3. c 11d @link. i A> list3 降水確率を入力してください : 1500 降水確率は 1500 % です。 100 の間ですよ。 降水確率は 0 いってらっしゃい。 A> list3 降水確率を入力してください : ー 10 降水確率は一 10 % です . 降水確率は 0 100 の間ですよ。 いってらっしゃい。 A> list3 降水確率を入力してください : 50 降水確率は 50 % です。 傘を忘れずにね。 いってらっしゃい。 ー凵 ST4 ℃をコンバイル ー凵 ST3 ℃をコンバイル ー凵 ST3. EXE を実行 凵 ST3. EXE の実行結果 ー凵 ST3. EXE を実行 凵 ST3. EXE の実行結果 ー凵 ST3. EXE を実行 凵 ST3. EXE の実行結果 工ラーメッセージ C 言語入門講座 83

実践アルコリ路解法のテクニック st 1 の実行過程て、は , 同じ計算を何度も行っ ていることになります。 fib ( 4 ) が 1 回 , fib ( 3 ) も 2 回 , fib(2) は 3 回 , fib(l) は 5 回 , そう , この fib (n) の呼び出し回数もフイボナ ッチ数列になっています。おもしろい現象 て、すね。 ともかく List 1 が遅い原因ははっきりしま した。 List 1 は再帰呼び出しの過程て、同じ計 算を何度も行っており , そのために必要以上 のムダな計算をしているのて、す。このムダ を取り除くエ夫はないものて、しようか。 一般に , 上記のような「ムダ」をなくすた めには , 次のふたつの方法が考えられます。 ①ムダな計算の起こらない手順を見つける ②一度計算した値を表として記憶しておき , ニ度目以降はその表により値を求める こて、紹介する「表計算法」は②に相当す る方法て、す。「表」を活用することによりム ダな再計算をなくせば , 演算時間は向上す るはずて、す。この具体的な手順については 表計算法て 1 厂・ 次の節て、解説します。 連想計算法 「計算によりフィポナッチ数列を求める」と の初期化が省略て、きるのて、便利て、す。また , ばなんて、もよいのて、すが , 0 にしておくと「表」 ありえない数を使います。 0 以下の数てあれ 現している値は , フィポナッチ数列として しておくというものてす。 List 2 て、「空」と表 求めてその値を返すとともに , 表にも格納 値を返し , 空 ( 未計算 ) て、あれば計算により 空て、なければ ( 計算済みて、あれば ) その表の して示します。見てのとおり , 表を調べて この具体的な手順を List 2 に疑似コードと す。 の表に記憶した値を直に返すというものて、 た値を表に記憶しておき , 二度目以降はそ ることにしましよう。それは , 一度計算し そのもっとも直接的な方法について考察す いろな方法が考えられます。この節て、は , ズムを高速化する」とーロにいっても , いろ 「表を用いてフィポナッチ数列のアルゴリ フイボナッチ数列を求めるプログラム i n t f i b ( i n t n ) return 1 ; e lse i f (n = return 1 ; e ー se re turn f i b (n ー 1 ) + f i b (n ー / * n く 0 の場合のチェックは省略した * / 9 : 8 : 7 : 6 : 5 : 4 : 3 : List . 1 TabIe 1 フイボナッチ数列を求めるプログラムの実行時間 実行時間 24 2 5 26 1 .3 2.1 3.4 単位 : 秒 , CPU : 80386SX / 16MHz , Fig. 2 fib ( 5 ) の呼び出しグラフ fib(4) 27 28 29 5.4 8.8 14.2 コンバイラ : Tu 市 0 C 十十 1 ℃ 1 fib(5) fib(3) fib(2) fib(l) fib(O) fib(l) fib(l) fib(2) fib(O) fib(2) fi b ( 1 ) fib(3) fib(O) fib(l) 表計算法によるフイボナッチ数列の求め方 List 2 3 : f i b ( n) 2 : i n t tabl e [ 表の大きさ ] : 5 : 8 : 9 : if (table[n] ! ニ空 ) return tabIeCn]; e lse { / * 計算済みの場合 * / / * 表の値を返す * / f ニ計算によりフィポナッチ数列を求める : tabIeCn] return f, / * 表に格納する一方で * / / * 求めた値を返す * / 書いた部分は , List 1 をそのまま流用すれば よいて、しよう。 これらの考察を元に , List 2 の疑似コード を C 言語のプログラムに詳細化したものを L 静的な変数は , 明示的な初期化を指定しな として利用しています。ご存じのように , あるように , 表 (table) は初期値 0 を「空」の値 明は簡略にとどめます。まず , リストにも 疑似コードをなぞっていますのて、 , その説 ist 3 に示します。 List 3 はおおむね List 2 の い場合は , 暗黙に初期値 0 が仮定されます。 これ自体は C 言語文法の初歩て、すが , この性 質を積極的に利用している場合は List 3 のよ うにコメントとして明示しておいたほうが , よいスタイルといえるて、しよう。 また , ふたつの関数 fib naive ( ) と fib ( ) は相互に呼び出しあっていますが , この関 係を「相互再帰」と呼びます。相互再帰など というと難しそうて、すが , 要は List 2 を忠実 になぞっているだけて、あることを確認して 実践アルゴリズム戦略解法のテクニック 87

p が 0 より小さい , コンヒ。ュータって , 本当に融通がききま やる必要があるのて、す。「降水確率は 0 ~ 100 の間て、すよ。」というのはエラーメッセージ または せんね。プログラムを書くというのはこの p が 100 より大きい 融通のきかない相手 , コンヒ。ュータに手と の一種といえるて、しよう。 という条件になるのて、す。「または」という り足とり作業の手順や細かい条件を教えこ List 2 を修正したのが List 3 て、す。 List 2 のはふたつの条件を結びつけ , そのふたっ む作業にほかなりません。慣れるまて、はな と List 3 の違いはどこにありますか ? Lis のうち , どちらか一方て、も ( 両方て、も ) 成り かなかたいへんな作業になりますが , 一歩 t 3 のポイントは初めの if の条件にありま 立っていればよい という新しい条件を作 一歩進んて、いきましよう。 す。 るものなのて、す。 さて , List 2 の間題点をかたづけてしまい 100 く p ).. if (p く 0 Ⅱ もう一度いいましよう。 この条件はいままて、見たパターンと違いま ましよう。 List 2 の間題点はなんだったかと いうと , 「降水確率が 0 より小さいときに す。不思議な縦棒い ) がふたっ並んて、いま if ( 条件 1 Ⅱ条件 2 ) { ューザに誤った入力て、あることを知らせて す。 PC ー 9801 のキーボードや画面上て、は " げ 処理 A くれない」ということて、した。降水確率を入 はなく " げとなっています。この縦棒ふた 力するときに手がすべって 1500 とかー 10 と つ ( Ⅱ ) は , 日本語て、いえば「または」という か , ありえない値を人間というものは入力 意味を持っ演算子て、す。つまり , してしまうものて、す。プログラムはそれに p く 0 Ⅱ 100 く p 対して適切なエラーメッセージを表示して は , 日本語て、読むと , Fig. 3 List 1 の実行結果 A> lcc listl. c 11d @link. i A 〉 listl 降水確率を入力してください : 50 降水確率は 50 % です。 傘を忘れずにね。 いってらっしゃい。 A 〉 listl 降水確率を入力してください : 0 降水確率は 0 % です。 傘はいりません。 いってらっしゃい。 A 〉 listl 降水確率を入力してください : 100 降水確率は 100 % です。 傘を忘れずにね。 いってらっしゃい。 A> listl 降水確率を入力してください : 1500 降水確率は 1500 % です。 傘を忘れずにね。 いってらっしゃい。 else { 処理 B 傘プログラムの完成 List ー LISTI ℃をコンバイル ー凵 STI . EXE を実行 LISTI . EXE の実行結果 ー凵 STI . EXE を実行 LISTI . EXE の実行結果 ー凵 STI . EXE を実行 LISTI . EXE の実行結果 ー凵 STI . EXE を実行 LISTI . EXE の実行結果 1 : #include く stdi0. h> 2 : #include く stdlib. h> 3 : 4 : #define MAX—LINE 5 : 6 : main() buf[MAX_LINE] : Char 8 : int p; 9 : 10 : printf ( ”降水確率を入力してください : " ) ; 11 : gets(buf) : 12 : p = atoi (buf) : 13 : printf ( " 降水確率は Xd % % です。 \ 心 , p); 14 : if (p く 0 Ⅱ 100 く p) { 15 : 100 の間ですよ。 %n ” ); printf( ”降水確率は 0 17 : else if (P 〉 = 5 の { printf ( " 傘を忘れずにね。 *n"); 19 : 20 : else ( printf(" 傘はいりません。 *n"); 22 : 23 : printf ( " いってらっしゃい。” ); 24 : 128 間違い探し List 1 : #include く stdiO. h> 2 : #include く stdlib. h> 3 : 4 : #define MAX—LINE 5 : 6 : main() bufCMAX LINE] : 8 : Char 朝 9 : int p; 10 : printf ( " 降水確率を入力してください : " ) ; 11 : gets(buf) ; 12 : 0 = atoi(buf) ; 13 : printf(" 降水確率は Xd % % です。 p); 14 : if (p く 0 凵 100 く p) { 15 : 100 の間ですよ。 *n"); printf(" 降水確率は 0 16 : else if (p = 〉 5 の { 17 : printf ( " 傘を忘れずにね。 }n"); 18 : else { printf(" 傘はいりません。 }n"); 20 : 21 : printf ( " いってらっしゃい。” ): 22 : 23 : } Fig. 4 List 2 の実行結果 A> lcc list2. c 11d @link. i A 〉 list2 降水確率を入力してください : 1500 降水確率は 1500 % です。 降水確率は 0 1 圓の間ですよ。 いってらっしゃい。 A 〉 list2 降水確率を入力してください : ー 10 降水確率は一 10 % です。 傘はいりません。 いってらっしゃい。 128 ー凵 ST2 ℃をコンノヾイル ー凵 ST2. EXE を実行 凵 ST2. EXE の実行結果 ー凵 ST2. EXE を実行 凵 ST2. EXE の実行結果 82 C MAGAZINE 1993 7

着目してほしい goukei=sumup(&x) ・ 引数が , x て、なく &x となっている。一般 , 配列 x に対して , ・・・配列の先頭要素へのポインタ ・・・配列 ( 全体 ) へのポインタ て、ある。 したがって , 配列名 x を単独て、記述した場 合は , & x [ 0 ] の略記法とみなされるのだ ( C olumn 4 ) 。 【重要】配列 x に対して , x は配列の 先頭要素へのポインタ ( & x [ 0 ] ) であり , & x は配列そのものへのポインタである。 x と &x は , そもそも型が異なるのて、 , ま ったく別物て、あるが , 原則としてその値は 同一て、ある。 ( 2 ) 受け取る配列の型 List 2 と List 4 の sumup 関数を利用する上 て、の , 決定的な相違は以下の点にある。 List 2 の sumup 関数は , 配列の先頭要素 へのポインタを受け取るため , いろい ろな大きさの配列を取り扱うことがで きるが , List 4 の sumup 関数は , 大きさ が 4 である配列しか受け取ることができ 関数利用者にとって , この違いは重要て、 ある。 ある大きさの配列のみを受け取る関数と いうのは , かなり型づけの強いものて、ある。 「ある大きさの配列しか受け取りたくない」 という場合は多くないて、あろう。したがっ て , 一般には List 4 のようなプログラムにお 目にかかることはない 大多数のプログラマは , 配列の大きさを になっている。 int 型は基本型て、あり , それ 示す番兵を , あまり意識することなく利用 にポインタを適用して派生したのが int * 型 している , と先ほど述べた。同様に , 皆さ て、ある。配列や構造体も , 派生の一種て、あ んは無意識のうちに ( ? ) , 関数の引数とし る。これらの導出は , 原理的には無限に組 多元配列 て List 4 のように配列へのポインタを利用し み合わせることがて、きる。 int 型にポインタ ているのて、ある。 それは , いかなる局面て、 C 言語には , いくつかの基本型があり , そ を適用した型に対して , さらにポインタを あろうか ? こから派生型を導出することがて、きるよう 適用すると int * * すなわち "int へのポイン Column3 不完全型 配列を「正しい」型として扱う局面では , といった具合で , 大きさを指定する必要の その大きさは必ずわかっていなければなら ないこともある。このような , 大きさ不明 ない。しかし , ほかのソースファイルで定 の配列 , 内容 ( メンバ ) 不明の構造体・共用 義された配列を利用するための宣言は , 体を不完全型と呼ぶ。 extern int X [ ] Column4 配列名 ソースプログラム中に , 配列名が単独で intx [ 10 ] ; 現れた場合 , それは & x [ 0 ] のことである と説明したが , 例外が存在する。それは , p 「 intf("%u*n", sizeof(x) ) : は 20 と出力する。もし x を & x [ 0 ] と解釈す sizeof 演算子の被演算数として現れた場合 だ。もし int 型が 2 バイト , int へのポインタ るコンバイラであれば , 3 と出力するかもし 型が 3 バイトであれば , れないが , それは AN 準拠ではない。 配列の全要素の値を合計する ( 配列へのポインタ ) List 1 : double sumup(double (*x)C4]) 6 : 7 : int main(void) double goukei ; double x ロ = { 1.5 , 3. 7 , 0.4 , 15.6 } : = sumup(&x) ; goukei printf( ”合計 =%fYn ” 20 : } int double sum for (i return (sum) : i 十十 ) goukei); return ( の : 元配列とポインタ 126 C MAGAZINE 1993 7

C 言語プログラミングレッスン if 文について学んだところて、 , 簡単なプロ グラムを読んて復習してみましよう。 傘プログラム いったほうがいいかを教えてくれるプログ List 1 は降水確率を入力すると傘を持って ラムて、す。 50 と入力すれば ( そして最後にキーを押 ルし , 実行した結果は Fig. 3 のとおりて、す。 列を整数に変換するものて、した。コンパイ ts は文字列を入力するもの。関数 atoi は文字 した関数をいくっか使っています。関数 ge させることカイきます。 List 1 て、は前号説明 ているのて、 , 安心してコンパイルし , 実行 今度は完全なひとつのプログラムになっ 傘はいりません。 と表示し , 0 と入力すれば , 傘を忘れずにね。 せば ) , れがプログラムになっていないかぎり , コ あるあなたが知っているだけのことて、 , そ くてはならない , というのはプログラマて、 さい。入力される数字が 0 ~ 100 の範囲て、な としかできない , ということを覚えてくだ ンピュータはプログラムに書かれているこ んてことはコンビュータは知りません。コ は 0 ~ 100 の値て、入力しなくてはならないな 入力される数字が降水確率て、あり , それ と表示されます。これはなぜて、しよう。 傘を忘れずにね。 答えてはくれません。なぜか , は 0 ~ 100 の間て、入力してください」と親切に という異常な値を入力した場合 , 「降水確率 と表示します。けれども・・・・・・あれれ , 1500 文章のパターン , 「 if... else 」という C 言語の構 文について説明しました。 if ( あなたは疲れている ) { ー休みする , else { 先を読み進む , 、丿工ーション 条件 2 も満たさないとき に if が続いています。 List 2 の構造を簡単に てす。ここて、は if... else …の else 以下に , さら まいました。この部分を修正したのが List 2 List 1 て、は 1500 % の降水確率が許されてし 「 if 文」の連鎖 たしているからて、す。 示されたのは , if 文の条件 ( p > = 50 ) を満 表示されるのて、す。「傘を忘れずにね。」と表 から「降水確率は 1500 % て、す。」などと平然と ンヒ。ュータには理解されないのて、す。て、す 書くと , if ( 条件 1 ) { 条件 1 を満たすとき 条件 1 は満たさず else { 条件 2 を満たすとき 条件 1 は満たさず else if ( 条件 2 ) { 条件 2 は p > = 50 条件 1 は p > 100 てください ということになります。 List 2 とよく見比べ せん。すべてきちんと明示的にプログラム もコンピュータに常識を期待してはいけま て、あるなどということは常識て、す。けれど 人ならば , 降水確率は 0 % から 100 % の間 となるて、しよう。 「傘はいりません。」 50 % 未満ならば , 「傘を忘れずにね。」 100 % 以下で 50 % 以上ならば , 「降水確率は 0 ~ 100 の間ですよ。」 降水確率が 100 % より大きいならば , らば , て、すね。 List 2 の動作を日本語て、説明するな こて、 , ちょっと注意しておきます。条 等号を入れるかどうか ? に書かなくてはならないのて、す。 件を書く場合 , 等号 ( = ) を入れるかどうか には細心の注意を払ってください たとえ ば , p > 100 p > = 100 このふたつの条件の違いはわかりますか ? このふたつの条件はほとんど同じ内容て、す が , たった一点 , 変数 p の値が 100 のときだ け違いが生じます。 p の値が 100 のとき , p > 100 は成り立たず , p > = 100 は成り 立ちます。 日本語て、 , このふたつの条件はそれぞれ p は 100 より大きい p は 100 以上 と区別して呼ばれます。条件式を見るとき には , 等号が入っているかどうかを注意し ましよう。また「より大きい」と「以上」は意 識して使い分けるようにしましよう。同様 に「より小さい ( 未満 ) 」と「以下」も使い分け これて、あなたは「 18 歳未満お断わり」を C 言 「または」を表現するには してください 条件が ( 年齢 < = 18 ) て、はないことを確認 お断わり ; if ( 年齢く 18 ) { 語ふうに書くことがて、きます。 C 言語入門講座 81 チェックが抜けてしまっていたのて、した。 クは入っていましたが , 0 より小さい場合の てす。しかし , 100 より大きい場合のチェッ List 2 はちゃんとそう書いたつもりだったの ムにそう書いてやらなくてはなりません。 ピュータは知りません。きちんとプログラ 降水確率は 0 ~ 100 の間だってことはコン て表示してしまうのて、す。 プログラムは平然と「傘はいりません。」なん は一 10 を入力してみると・・・・・・やつばりこの 示されるようになりました。しかし , 今度 確かに「降水確率は 0 ~ 100 の間て、すよ。」と表 として 1500 を誤って入力してしまった場合 , この実行結果 ( Fig. 4 ) を見ると , 降水確率 ところて、 ,List 2 はこれて、完全なのて、しょ

60 て、すから , 求める解も 2 , 540 , 160 以下にな っているはずて、す。 以上の考察を元に , パズルを解くための もっとも基本的なアルゴリズムに基づくプ ログラムを作成しました。 List 6 がそれて、 す。 List 6 の要点は関数 factsum て、す。この 関数により階乗和を計算し , それが元の整 数と等しければ求める解になっていること になります。 List 6 は単純て、わかりやすいのて、すが , 探 索を終了するのに約 24 分 ( 386SL / 25MHz ) か かります。単に答えを求めるだけて、あれば この程度の速度て、も十分て、すが , プログラ マの心情としてはもっと高速な解法が欲し くなりますね。次の節て、は , このパズルの 表計算法に基づく高速化について検討する ことにします。 List 6 } ⅶⅱ e (d > の : return sum, -4 ・ LO ー - 8 00 0 1 よワ 0 っ 0 ・ - 、リ叮ー っ 0 90 ワ朝ワ 0 っ 0 っ 0 00 っ 0 ワ 0 り 0 り 00 00 00 long i, maxnum; ニ fact(9) * 7 : maxnum for(i ー 0 : i く = maxnum; i 十十 ) if(factsum(i) printf(" 解 = %ld%n ” return 0 : / * 探索の上限を求める * / / * 階乗和と自身が等しければ * / / * 解として表示 * / Fig. 4 マクロなムダ ( 1 ) 上位桁はほとんど 末尾桁は頻繁に 変化しない 変化する 1 0 0 0 0 0 0 1 1 0 0 0 0 0 2 1 0 0 0 0 0 3 変化の少ない上位桁について , いちいち階乗和を 計算するのはムダである。 表計算法によって高速化が行えるのは , 要は同じ計算を何回も行っている場合て、す。 List 6 について , 「同じ計算」を繰り返してい る部分がないか , 検討してみましよう。 まず真っ先に目につくのは , 階乗の計算 を何度もやり直していることて、す。階乗の 計算は 0 ~ 9 の 10 通りしか行わないのて、すか ら , あらかじめ計算して一覧表にしておけ ば , ムダな計算を避けることがて、きます。 これは典型的な「表計算法」の応用といえま す。 こて、調べたのは一桁の計算の部分て、 , いわばミクロな部分についての改良て、すが , List 6 をよく調べてみるともっと広い範囲て、 冗長な計算を繰り返しているのて、す。これ はいわばマクロなムダといえます。一般的 な経験則として , ミクロな改良よりもマク ロな改良のほうが , はるかに効果が大きい ことが知られています。以下 , これについ て検討します。 まず Fig. 4 をご覧ください。この図は探索 の過程を図示したものて、すが , ご覧のよう , 上位桁はほとんど変化していない 高速解法の検討 表計算法に基づく数学パズルのプログラム list7. c List 7 1 : / * f ⅱ e ニ 2 : 3 : # i nc lude 4 : # i nc lude 6 : #define TABLE-SIZE 1000 7 : 8 : long f-tabIe[10]; 9 : long factsum-tabIeCTABLE-SIZE] ; / * 階乗和の一覧表 * / 11 : / * 階乗を求める関数 1 3 : long fact(int n) return 1 : 20 : 21 : / * f ー ta い e を初期化する。 * f ー ta い e は一桁の階乗の表である。 22 : 23 : 24 : void init-f-table(void) 25 : { 26 : 27 : 28 : 29 : } 30 : 31 : / * factsum-table を初期化する。 * factsum-table は " 000 " から " 999 " までの階乗和の表である。 32 : 33 : 34 : void init-factsum-table(void) く stdio. h> <l i m i ts. h 〉 e ー se return fact(n for (i = 0 : i く 10 : i + + ) f-table[i] : fact(i); 90 C MAGAZINE 1993 7

[ 特集 ] グラフィックを操る 画像処理 プログラミング は , ループと数値演算に関する最適化をか に 3 x 3 のラブラシアンの場合のプログラム ~ 水 ~ 青 ~ 紫 ~ 赤というように一周します。 を示します。 10 ~ 12 行目て、原画像用のメモ けて , 少して、も高速になるようにします。 RGB と HSI の変換方法は手続き的な処理 リを確保し , 1 行読み込むごとに , 24 ~ 26 行 なのて、 , 言葉て、説明するよりも , プログラ 目て、示すように循環させるようにします。 ムリストを見たほうがわかりやすいて、しょ こうすれば , 少ないメモリて、処理を行うこ う。 List 7 て、 , RGB → HSI の変換は rgb2hsi ( ) , とがて、きるのて、す。 HSI → RGB の変換は hsi2rgb ( ) という関数 オペレータを作用させる処理は , 局所的 カラー画像て、は , 通常 , 赤 (R), f*(G), を用います。 に見ると四重のループになり , 計算量が膨 青 ( B ) の 3 原色の濃淡値によって 1 ヒ。クセルを Photo 12 に , この変換を使って処理した 大になります。 表現します。しかしながら , 場合によって 画像を示します。ここて、は , 画像を HSI に変 とくに , ガウシアンや Marr-Hildreth オペ RGB の表現て、は不便な場合があります。 換し , 彩度の平方根を取って強調してから レータなど , 巨大なマスクて、は , 処理時間 RGB に戻しています。このため , 全体に色 が非常にかかります。そのため , 高速化の が濃くなっているのがおわかりいただける ための工夫が必要て、す。 て、しよう。 係数があらかじめわかっている場合には , 人間の感性に合った色の表し方に , 色相 ・係数が 0 の部分は計算式からはぶく ( H ) 彩度 ( S ) 明度 ( I) の三つのパラメータによ ・対称性を利用して , 同じ係数をかけるピ るものがあります。明度は 0 なら黒て、 , 大き クセルについてはそれらのピクセル値の いほど明るくなります。彩度が 0 の色を無彩 フィルタリングの手法には , もつばらグ 和をとってから係数をかけるようにして , 色といい , 白 ~ 灰色 ~ 黒のことをいいます。 レイスケール画像を対象にしたものがあり , 乗算回数を減らす 明度が 0 なら彩度も 0 になります。色相は 0 が カラー画像の RGB 値を独立にグレイスケー 赤て、 , 60 度 ( 3 ラジアン ) ごとに赤 ~ 黄 ~ 緑 などの最適化を行います。コンパイル時に レとみなして処理しても , 意味のある結果 モサイク処理 ラブラシアンの計算 色の変換 RGB ←→ HSI 変換 カラー→グレイスケール変換 List List 1 : void laplace() 〃入力ファイルのオープン 3 : FILE* sfp ニ fopen( . 4 : i f ( ! sfp) { / / 工ラー処理 6 : 7 : / / 原画像バッフアの確保 8 : uchar* src[3] ; 9 : src[0] ー nev ucharCw] : src[l] ー ー nev uchar[w] : srcC2] = new uchar[w] : if (!srcC0] Ⅱ !src[l] Ⅱ !src[2J) { 〃工ラー処理 . 15 : i n t ⅶ : を一 2 ; / / 生成画像の幅 16 : i n t hd ニ h ー 2 : / / 生成画像の高さ / / ( オペレータの高さ ) - 1 行読み込み fread(src[l], 20 : l, 第 sfp); fread (src [ 2 ] , 1 , 矍 , sfp); for ( i n t yd = 0 : yd く hd : yd + + ) { 22 : / / 読み込みパッフアを循環させる 23 : = src[0] : 24 : uchar* swp src[0] ニ srcCI]; src[l] = src[2]; 25 : src[2] = 26 : SWP; / / 1 行読み込み 27 : fread(src[2], 1 , 町 sfp); 28 : 29 : for ( i nt xd = 0 : xd くⅶ : xd + + ) { 30 : / / オペレータによる計算 dst[yd * hd + xd] : (int)src[0][xd] + (int)src[l][xd ー 33 : - 4 * (int)src[l][xd] 34 : + (int)src[l][xd + 1 ] + (int)srcC2]Cxd]; 35 : 36 : 38 : 39 : 40 : 冫ー 一一 X V) 十 a. O ー 0 X E 「し 1 より 0 00 -4 ・れ 0 ー 8 LiSt 油絵効果 1 : uchar h i s t [ 256 ] : / / ヒストグラム用パッファ 2 : / / 領域の大きさ 3 : $de f i ne MS I ZE 9 4 : int wd ー MS I ZE + 1 ; 5 : int hd ー MS I ZE + 1 : 6 : for ()d = 0 : yd く hd : yd + + ) 7 : f 0 r ( xd : 0 : xd く : xd + + ) { 8 : / / MS I ZE x MS I ZE 領域のヒストグラムを求める 9 : int maxh 0 , maxi : memset((char*)hist, 0 , 256 ) : for ( i n t i = 0 : i く MS I ZE ; i + + ) 12 : for (int j = 0 : j く MS IZE : j + + ) { uchar pixel i n t vo t e ニ + + h i s t [ p i xe 冂 : / / maxi 最大頻度の農淡値 if (vote 〉 maxh) { maxh VOte; maxi pixel; 20 : dstCyd * 面 + xd) delete[] src[0] : deIeteC] src[l]; deleteC] src[2] : max グラフィックを操る画像処理プログラミング 53

ープロクラミンク道場 Dr. 望洋の たのだ。 せつかくだから List 5 を , もう少しポイン タらしく記述してみよう。それが List 6 て、あ 配列の各行の合計を表示する ( ポインタ表記 ) List 1 : void sum(double (*x)C3], 6 : 7 : 8 : 15 : int main(void) double goukei; double x ロ [ 3 ] = 20 : 22 : 23 : 24 : 25 : int n) int 問募集 本連載て、は , 読者からの質問にお答えし , また希望に応じてプログラムの添削も行う。 下記必要事項を明記の上 , フロッピーディ スクにて応募していただきたい ( 短い質問て、 あれば , 書面のみて、可 ) 。 なお , 応募いただいたフロッヒ。ーディス クは返却て、きないことや , 個人的な質問に は一切お答えて、きないことをあらかじめご 了承されたい どんな小さな疑問て、も結構なのて、 , 気後 れせずに , 応募していただきたい ( ただし , 特殊な題材よりも , 一般性の高い題材を優 先的に取り上げることを , あらかじめご了 ポインタて、あり , すなわち「、、 int クを要 け上は配列の表記を用いているが , 受け取 承願いたい ) 。 素とする大きさ 3 の配列」へのポインタ っているのはポインタて、あり , これは「、、 int" ( 1 ) 氏名・住所・電話番号 て、ある。これは , Fig. 2 ー ( b ) の濃い網掛 を要素とする大きさ 3 の配列」へのポインタ ②匿名希望の有無 / ペンネーム け部て、あり , 決して , x [ 0 ] [ 0 ] へのポイ て、ある。 ( 3 ) 質問・相談事項 ( なるべく具体的に ) ンタて、はない したがって , sum 関数の頭部 宛先 もちろん , 渡瀬さんが悩んだのも無理の void sum(double x [ ] [ 3 ] 〒 103 東京都中央区日本橋浜町 3 ー 42 ー 3 ない話て、ある。 1 元配列の例て、説明したよう をポインタらしく書き直すと , ソフトノヾンクスクウェア , 配列 x に対し , x すなわち &x [ 0 ] と &x void sum(double (*x) [ 3 ] ソフトバンク ( 株 ) 出版事業部 int n) となる。ここて、の、、 double ( * x ) [ 3 ] 〃は見た C マガジン編集部 は , 型は違うものの , ポインタは同じ値を 「 Dr. 望洋のプログラミング道場』係 ことがあるはずだ。それもそのはず , List 4 持つのだから。 て、使ったものて、ある。これて、 , 先ほど述べた 今回の冒頭て、も強調したように , C 言語に おいて , 「型」は非常に重要なものて、ある。 「皆さんは無意識のうちに ( ? ) , 関数の 参考文献 たとえば long 型と float 型がともに 4 バイトて、 引数として List 4 のように配列へのポイ [ 1 ] 平林稚英 , 『 ANSI C 言語辞典』 , 技術評 ある処理系て、あっても , その中身の解釈の ンタを利用しているのである。」 論社 , 1989 仕方がまったく異なるのと同様に , &x [ 0 ] の意味がわかったて、あろう。多元配列の受 [ 2 ] 柴田望洋 , 『秘伝 C 言語間答ポインタ と &x [ 0 ] [ 0 ] はまったく異なるのだ。 け渡しのときに使っていたのて、ある。 編』 , ソフトバンク , 1991 きちんと理解した上て、使っていた人はそ 多元配列とポインタ [ 3 ] 柴田望洋 , ℃プログラマのための C 十十 れほど多くないと思う。 List 5 を示したとき 最初にも説明したように , 関数の引数と 入門』 , ソフトバンク , 1991 の , して配列そのものを受け渡しすることはて、 「本連載の読者であれば , 大まかには理 きず , その先頭要素へのポインタを受け渡 解できるであろう。」 しばたばうよう ( 工学博士・九州大学工学部化学機械工学科 ) の、、大まかにクは , こういった事情からだっ す。したがって , List 5 の sum 関数は , 見か 0 ワ 0 •n 1 三ロ 0 く夏合 十 2 sum) : 0 っ 0 ^ 0 0 リ 0 ワ 0 8 0 , 1 -4 ー sum(), 4 ) : return ( の ; int n) 128 C MAGAZINE 1993 7

ていく際の助けになります。 この部分は前回のものと本質的に同等のも います。理論的にはそれて、よいのて、すが , 前回の Window クラスから子ウインドウの のて、す。 現実て、は有限個のウインドウしか扱えませ 追加がおもな変更になっています (Fig. 2 ) 。 子ウインドウと , 自分と同列のウインド ん。上限と下限はどのように設定し , ある 自分を所有している親ウインドウが owner に ウの 2 種類のリストが交錯してやや混乱しま いは判定したらよいて、しようか。 なります。自分の所有している子ウインド すがじっくり考えて理解しましよう。 子ウインドウの限界というか , いちばん ウのいちばん始めのものへのポインタが fir 最後のウインドウというのは別に間題なく st て、す。自分が owner の始めに位置している リストの先を NULL にて、も落としてしまえ なら , 自分自身は owner → first ( ) になると ばすぐ解決します。しかし , 始まりのウィ いうことてす。 last(), findWindow(), f ウインドウが入れ子構造になっているこ ンドウはどうて、しよう。前回は winT 叩とし ront ( ) , insert ( ) , remove ( ) は , いずれも とは理解していただけたて、しようか ? あ て例外的な変数を使用して初めの一撃とし 自分の所有しているウインドウに対しての るウインドウに注目すると owner ウインドウ て使用しました。 どうせならこのいちばん アクセスとして作成します。 next ( ) , prev が上にあり , first<' 始まる子ウインドウが下 最初のもウインドウて、あったほうが気持ち ( ) は自分と同階層のウインドウの次 , また に連なっているのがイメージて、きると思い がいいて、しよう。 DeskTop クラスを導入し は前のウインドウを返します onext ( ) はメ ます。そのイメージは上にも下にも無限の たい動機はそんなところて、す。そのための ンバ変数 nextWindow を単に返すだけて、す。 ウインドウが連なっているものになると思 始まりのウインドウを ( 伝統的に ) DeskT 叩 日 ect クラスから導出した Window クラス DeskTo p クラス List 6 旧 / / 座標系変換 virtual POint toLocal(Point src) : virtual POint t0G10baI(P0int src); / / 枠を描く virtual void drawFrame() ; / / 同レベルの次又は前の windo 響 Window *next() : Window *prev() ; / / 子ウインドウ関係 Window *last(); Window *findWindow(const POint p) ; Window *front(Window *wp) ; Window *insert(Window *wp) : Window *remove(Window *wp) ; / / マウス処理 virtual void handleMouse(const P0int P) / / 点をうっ virtual VOid putPixel(Point P, byte C010r ) ; class Window : public Rect public: Window *owner; Window *first; Window *nextWindow; / / コンストラクタ Window(const Rect& bounds) ; virtual Window() { shutDown() ; virtual void shutDown() ; 〃 window の枠を設定 void setBounds (const Rect& bounds) : / / 枠を取得 Rect getBounds ( ) ; / / 枠を正規化 void regular() : / / parent / / child Fig. 2 子ウインドウの連鎖 Fig. 3 すべての Window は DeskTop の上にある DeskT0 p NULL ・ nextWindow fi 「 St ・ nextWindow first ・ nextWindow fi 「 st ・ nextWind0W fi 「 St U LL ・ nextWindow first ・ nextWindow ULL first IJ LL ULL NULL ※順番はサンプルとは違います 72 C MAGAZINE 1993 7