ライフボート ln 種川 a ⅱ行 m 川計 Ma れ門 WATCOM FORTRAN 77 / 386 グマを使用して実現て、きます。 Fig. 1 整数型に対して long キーワードを指定 と WATCOM C / 386 を使用したミ 次に考えられる問題点は , 引数 long int ftnname(long int * , long int * , long int * ) : ックスドランゲージ開発における に関するものて、す。 一般に , C は値渡し (CaII-by-va 注意点について説明いたします。 Fig. 2 単なる文字列へのポインタを渡すプラグマ まず , ソースコードのシンボル lue) て、あり , FORTRAN は参照渡 c$pragma aux cname ” * parm (value) 名は , オプジェクトコードの中て、 し (CalI-by-reference) て、す。これ クセスしなければなりません。し イトを使用しますから , 整数型に は , FORTRAN サププログラムに は異なるシンポル名に変換される 対して C て、は long キーワードを指定 たがって , FORTRAN は文字デー 場合があるという点て、す。 引数を渡すためには値て、はなく , タの引数として , 文字列記述子へ するべきてす。たとえば Fig. 1 のよ WATCOM C / 386 コンパイラ 引数のアドレスを渡さなければな うにします。 Fig. 1 の場合 , 、、 ftnn のポインタを受けとらなければな は , デフォルトては変数名の前と らないということを示しています。 ame クは引数として三つの、、 longin りません。 WATCOM C / 386 て、は , ANSI 規 後ろにアンダースコア ( ) をつけ C と FORTRAN の間て、文字列引 t 〃へのポインタを持ち , 、、 longint 〃 ます。一方 , WATCOM FORTR 格に従って、、 & 〃文字はそれに続く 型の値を返すことになります。 数をやりとりするということは , AN77 / 386 は , シンポルを大文字に トークンのアドレスを意味します。 前述のふたつのフィールドを持つ C と FORTRAN の間て、整数の引 変換します。この不一致は , AUX たとえば , 数をやりとりするプログラム例を C の構造体を作成する必要がありま ftnname( &arg ) ・ プラグマを使って解決することが result す。最初のフィールドは , 文字デ 付録ディスクに収録します ( EXIC. のようにして呼び出すことになり て、きます。 ータへのポインタを含まなければ C と EXIF. FOR および EX2F. FOR プラグマ (#pragma) は , 互換性 ます。また , C の関数を FORTRA ならず , 2 番目のフィールドには , と EX2C ℃ ) 。 N から呼び出すときには , シンボル を実現するためのコンパイラディ 文字データ ( 文字列 ) は , 引数と 渡される文字列の長さを含まなけ レクテイプ ( 疑似命令 ) て、あり , コ 名の変換を指示したときに使用し して使用されるときには例外的扱 ればなりません。この構造体への ード生成のための情報を指定しま たプラグマを使って , コンパイラ いとなります。 C においては , 文字 ポインタは FORTRAN に渡されま す。 C から FORTRAN サププログ に値を渡すように指示します。 列という型はとくになく「文字の配 す。この方法を用いた C と FORTR ラムを呼ぶときには , 関数名の後 c$pragma aux cname ” * 列」として考えられています。文字 AN の間て、の文字列引数をやりと ろにアンダースコアをつけずに parm (value) 列はスカラ型の引数とは考えられ りするプログラムを付録ディスク parm (value) 〃によって , FOR 関数名を大文字に変換しなくては ないのて℃と FORTRAN とて、は異 に収録します (EX3F. FOR と EX3 TRAN コンパイラに対してアドレ なりません。これは , なった参照方法がとられます。 C ℃ ) 。 スてはなく値を引数として渡すこ #pragma aux ftnname " デフォルトて、は ,FORTRAN は C 言語て、は文字列の終端を示す のような C の AUX プラグマを使用 とを指示しています。 して実現て、きます。 ' へ文字は , コ 文字列を引数として渡すとき , 文 マーカ (EOS, End-Of-String) て、 一般に , 整数型の大きさ ( バイト 字列記述子のアドレスを渡します。 ある null 文字て、文字列を終わるの ンノヾイラにシンボル名、、 ftnname 数 ) は , 処理系に依存します。 FOR C の関数が通常の C の文字列を渡 て、 , メモリに文字列の長さを格納 を大文字に変化させ , アンダース TRAN ては整数型のデフォルトの してくるものとしているならば , しておく必要はありません。しか 大きさは , 常に 4 バイトてすが , C コアをつけないことを指示してい FOTRAN のプラグマによって正し し , FORTRAN て、は EOS マーカを ます。これによって , リンカが C の てはマシンに依存し , 16 ビットア 使用しないのて、 , メモリ上に文字 く文字列を渡せます。値渡しを指 ーキテクチャの C コンパイラて、は 2 デフォルトのシンポル名の変換結 列の長さを記憶しています。 FOR 示する WATCOM FORTRAN7 バイト整数てあり , 32 ビットアー 果て、ある、、 ftnname クを探すとい TRAN は文字データを扱うために 7 / 386 のプラグマを文字列に使用す キテクチャの WATCOM C / 386 て、 う , 潜在的な問題を解決て、きます。 文字列記述子と呼ばれる構造体を ると , 単なる文字列へのポインタ は 4 バイト整数て、す。 C て、関数のプ 逆に , C の関数を FORTRAN から 使用し , この構造体は , 文字デー ロトタイプ宣言をするときに、、 long を渡すようになります (Fig. 2 ) 。 呼ぶときは , 関数名の後ろにアン 文字列を定義する FORTRAN タへのポインタと文字データの長 ( 4 バイト尸ミ short ( 2 バイト尸など ダースコアをつけ , 小文字を大文 のメインルーチンとその文字列を さを示す符号なし整数とて、構成さ のキーワードを使用して , どの大 字に変換しないようします。これ 表示する C の関数の例を付録ディス れています。文字データヘアクセ きさの整数を使用するかを指定す は , クに収録します (EX4F. FOR と EX スするためには , FORTRAN はそ るともっとも安全てす。 c$pragma aux cname " * の文字データの文字列記述子にア 4C ℃ ) 。 のような FORTRAN の AUX70 ラ FORTRAN はデフォルトの 4 バ WATCOM C / 386 lnformation from CompiIer Makers 163

トしているのて、 , 問題はないのて、すが , IB 労しました。 IBM の AX や DOS / V 版を J ー 3100 て、使った M やそのほかの機種て、は基本的にキャラク PC 一 9801 版て、は , VRAM 操作するのは , ほうが機能的にもいいかもしれません。 タマップは英語しかサポートされておらず , メニュー枠のカラー表示や画面クリア , バ 日本語表示にはビットマップ方式になりま ックスクロール程度て、済みましたが , J ー 31 FMR (List 8 参照 ) す。それて、も , 速い CPU ならば , ある程度 00SS の場合 , CPU が遅く , 通常の文字表示 FMR て、は , PC ー 9801 と VRAM の構成やア スピードが出るのて、 , ビットマップて、も , て、も十分なスヒ。ードが出ず , 結局 , 文字の トリビュートビットが異なっています。 そこそこの回線スヒ。ードについていく FONT 展開からすべて自前て、処理すること また , IBM 互換機のように , 画面モード がて、きますが , CPU が遅いととても使いも になっていしまいました。また , 少して、も が複数あり , それに対する処理も増えてい 速くしようと , ほかとは違い Pascal て、はな のになりません。 ます。 く , アセンプラて、記述してあります。 しかし , 一応キャラクタマップて、対応て、 現在の J ー 3100 シリーズは , CPU のスヒ。ー J-3100(List 7 参照 ) きるのて、 , スピードなどは十分なパフォー J ー 3100 版て、は , 開発を J -3100SS ( 8086 / 8M ドも十分速くなっているのて、 , かえってム マンスが出たのて、 , そう苦労はなかったと HZ ) て、行ったため , 画面表示にいちばん苦 ダな処理が多くなっているかもしれません。 思います。また , FM 関係は BIOS がたくさ VRAM に関するプログラム部分 0F800 ) V 日 AM に関するプログラム部分 ( FMR ) List List procedure vram-colors(), Y, len: integer;col :vord;mode:byte) ; { カラー表示 VRAM 直接書き込み } Var procedure vram-colors(), y, len: integer;col:word;mode:byte) ; { カラ - 表示 VRAM 直接書き込み } LABEL vram_color_l, vram_color_2, vram_color_3, vram_color_4, Var word : begi n = (pred(y) *endvord + pred (x) ) shl 1 : if ( scrn-type = SCRN-24 ) then begin asm push push les di,vatr ad d CX, len mo V ax, COI mo V c 届 repz stosv POP POP end, end else begin push push DOV an d test jz test test jz les ad d c 届 inc mov and stosb OP POP PO P Xsave, Ysave, AttrSave . vord; : array [ 0..80 ] 0f byte; Dstr procedure ÅttrChg(yc lnteger) : Var lnteger; begi n fi llchar(Dstr, sizeof(Dstr), # $ 2 の : goto-xy(), Y 十 yc, の ; DstrClen] vith param dO begin CL ・ = $D7 : ES : = seg(Dstr) ; DX : : ofs(Dstr) ; Intr(EXTD, param) : lnteger : end : end; begi n asm bx, col bl, $ 07 vord ptr c01,V-RV vram_color_l bl, $ 08 vord ptr col, V-BL vram_co ー or ー 2 bl,$10 vord ptr COI, V-HL vram_co ー or ー 3 bl, $ 20 di, vram CX, len c l, $7E mov ah, 1 mo V d l, 2 mov EXTD int cl, $3D mov int EX TD Xsave, ax mo V Ysave, bx mo V end : AttrSave ・ニ GetColor; TextColor(c01) : = trunc(Ien/8 のー1: if ( dy く 1 ) then AttrChg( の else begin 1 en ・ = 80 : for j vram_col or ー 1 : vram_co ー or ー 2 : vram_co ー or ー 3 : ニ 0 to dy do AttrChg(j) ; end; asm vram_color 4 : 0 0 ャレ 0 cl, $7E mov ah, 1 mov dl,dl xor EXTD int cl, $2D mov ax, Xsave mov dx, Ysave mov EXTD int end; TextCOIor(AttrSave) : end, end , end, end : 154 C MAGAZINE 1993 2

C プロラマのための List 1 バイプ起動ユーティリティ (pipemain. c: 抜粋 ) List / * CTR い C 割込無視 int fi gnore-ctrlc / * ハ。イフ。処理ハ・ツフアオ - ハ・フロー int fbufover / * メモリ種別 int memtype = MEMMAIN; / * 入力ハ。イフ。処理ハ・ツフアへのホ。インタ * / char far *prdmem, / * 出力ハ。イフ。処理ハ・ツフアへのホ。インタ * / char far *pvrmem, / * 入力ハ。イフ。処理サイス・ハ・ツフアへのホ。インタ * / unsigned long *prdsiz; / * 出力ハ。イフ。処理サイス・ハ・ツフアへのホ。インタ * / unsigned long *pvrsiz; / * 入力ハ。イフ。処理ハ・ツファ位置 unsigned long lrdpos; / * 出力ハ。イフ。処理ハ・ツファ位置 unsi gned long lvrpos; *p i pemen[ 2 ] : / * ハ。イフ。処理月・ツフアへのホ。インタ ( 固定 ) * / void far unsigned long lpipesiz[ 2 ] / * ハ。イフ。処理ハ・ツフアサイス・ / * ハ。イフ。処理ハ・ツフアサイス・ unsigned long lpipemax = 円 PESI ZE , void dos3f( struct sirstk far * ). d0S40 ( struct sirstk far * ) : void interrupt $ifndef __TURBOC_ far $endif ne 町 21 ( struct sirstk sirarg ) svi tch ( s i rarg. ax > > 8 ) { case 0X25 if ( fignore_ctrlc & & ( sirarg. ax & 0xff ) break, -chain-intr( 引 d -21 ) : break, case 0X3f i f ( s i rarg. bx ! : FD 燼 Ⅱ prdmem - : NULL ) -chain-intr( 引 d -21 ) ; d0S3f( &sirarg ) ; break, case 0X40 if ( sirarg. bx ! : FDOUT Ⅱ pvrmem ニ NULL ) -chain-intr( 引 d ー 21 ) : d0S40 ( &sirarg ) : break, default chain-intr( 引 d ー 21 ) : break; 十 ーー 0 0 0 0 0 V) X X 0 = FALSE; : FALSE; / * チェーンするアト・レス #end i f int main( int argc, char *argv[] ) static char iret[] ニ { 0xcf } : char cmdnam[ PATHLEN ] ; char CO 引 ine[ 256 ] ; int indexrd indexvr int count, ret; if ( --argc Ⅱ **argv svi tch ( argv [ 0 ] [ 1 ] ) { case case m / * チェーンするアト・レスをスタックに積む * / ヨ ライトハント・ル 入力 ds:dx : ハ・ツフアのアト・レス cx = 書込みハ・仆数 bx ニファイル・ハント・ル 出力 ax : 書き込んだハ・仆数 void d0S40 ( struct sirstk far *pirarg ) if ( *pvrsiz 十 pirarg->cx 〉 lpipemax ) { ( unsigned ) ( lpipemax - *pvrs i z ) ; pirarg- 〉 ax / * ハ。イフ。処理ハ・ツフアオーハ・加 - fbufover = TRUE; } else / * 書き込んだハ・仆数 pirarg->ax ニ pirarg- 〉 memcpy( MK-FP( FP-SEG( P 響 ) + ( unsigned ) ( lvrpos 〉 > 4 ). FP_OFF( p 田 e 田 ) + ( ( unsigned )lvrpos & 0x0f ) ). MK_FP( pi rarg->ds, pirarg->dx ) , / * ハ。イフ。処理ハ・ツファ書込み pirarg—>ax ) ; / * 出力ハ。イフ。処理サイス・更新 *pvrsiz 十 = pirarg—>ax; / * 出力ハ。イフ。処理ハ・ツファ位置史新 lvrpos 十 : pirarg—>ax. / * キャリ - リセット pirarg- 〉 flags & : Oxfffe• / * retf * / / * IRET / * 起動コマント・名 / * コマンド・ライン / * 配列添字 / * 引数の取得 / * ハ。イフ。処理ハ・ツファ : メイン・メモリ = strtoul( &argv[ 0 ] [ 2 ] , NUL し 10 ) ; / * ハ。イフ。処理ハ・ツフア・サイス・ ( ( lpipemax + 15 ) / 0X10 ) * 0X10 : / * ハ。ラク・ラフ・サイス・に切り上げ ニ MEMMAIN; / * メモリ種別 : メイン・メモリ / * 使用法表示 / * CTR い C 割込無視 ? : T23 ) / * 割込へ・クタ 23h の設定を無視する / * 元の INT 21h ハント・ラを呼び出す / * 標準入力以外 ? / * 入力ハ。イフ。処理なし ? / * 元のは T 21h れント・ラを呼び出す / * リードハンドル lpipemax lpipemax memtype break, default usage() ; break, / * 標準出力以外 ? / * 出力れ。イフ。処理なし ? / * 元の燼 T 21h ハント・ラを呼び出す / * ライトハンドル —argc : 十十 argv; / * 元の INT 21h ハント・ラを呼び出す if ( argc usage() : return( 1 ) : / * 使用法表示 リードハンドル 入力 ds:dx ニハ・ツフアのアト・レス cx : 読込みハ・イト数 bx ニファイル吶ンドル 出力 ax : 読み込んだハ・イト数 VOid dos3f( struct sirstk far *pirarg ) ( lrdPOS 十 pirarg- 〉 CX く = *prdsi Z ) ? pirarg->cx pi rarg->ax / * 読み込んだハ・イト数 memcpy( MK-FP( pirarg->ds, pirarg->dx ). MK_FP( FP_SEG( prdmem ) + ( unsigned ) ( lrdpos > 〉 4 ) , FP_OFF( prdmem ) + ( ( unsigned )lrdpos & 0x0f ) ) , pirarg->ax ) : / * ハ。イフ。処理ハ・ツファ読込み / * 入力ハ。イフ。処理ハ・ツファ読込み位置更新 * / lrdpos 十 : pirarg->ax . pirarg->flags & : Oxfffe; / * キャリーリセット ワ 1 . DOS 3. x 以降で動作させてください . \n ” ) : if ( memtype : MEMMAIN ) { / * メモリ種別 : メイン・メモリ ? i f ( ( P i pemem [ 0 ] : ha Ⅱ OC ( ゆ i pemax, 1 ) ) : NULL Ⅱ ( pipemem[ 1 ] ー halloc( lpipemax. ー ) ) : NULL ) { puts_err( "pipenain ・メモリが足りません . \ 心 ) : return( 1 ) : -dos-setvect( Ⅷ T23 , ( void ( interrupt far * ) ( ) ) iret ) ; / * CTRL+C 割込無視 引 d ー 21 ニ _dos_getvect( T21 ) : / * 割込へ・クタ取得 -dos-setvect( T21 , ne 響 -21 ) : / * 割込へ・クタ設定 for ( cmdnam[ 0 ] --argc, 十十 argv ) { count if ( !strcmp( *argv, pipech ) Ⅱ argc pipemem[ indexvr ] : ニ 0 ? NULL ・ pvrmem argc / * 出力ハ。イフ。処理ハ・ツフアへのホ。インタ prdmem : count : 0 ? NULL pipemen[ indexrd ] , / * 入力ハ。イフ。処理ハ・ツフアへのネ。インタ &lpipesiz[ indexvr ] : / * 出力ハ。イフ。処理サイス・・ハ・ツフアへのホ。インタ : & ゆ i pes i z [ i ndexrd ] , / * 入力ハ。イフ。処理サイス・・ハ・ツフアへのホ。インタ ー p i pes i Z [ i ndexwr ] / * ハ。イフ。処理ハ・ツフア・サイス・リセット lrdpos ニ 0 し / * 入力れ。イフ。処理ハ・ツファ位置リセット * / lvrpos / * 出力ハ。イフ。処理ハ・ツファ位置リセット * / ー spavnl ( P_WAIT, cmdnam, cmdnam, co 引 ine, N 乢し ) ; ret i f ( ret puts_err( ” pipemain コマント・の起動に失敗しました . \ 心 ) ; break, pvrsi Z prdsi Z i f ( argc break , 十十 count; indexrd indexvr; indexvr = indexvr; cmdnam[ 0 ] } else if ( cmdnam[ 0 ] static char *pcomspec comline[ 0 ] $i fdef _TURBOC_ void _chain_intr( void ( interrupt far *inthdl ) ( ) ) / * 入力配列添字 / * 出力配列添字 / * 起動コマント・名リセット ニ NULL; / * 環境変数 COMSPEC へのホ。インタ * / / * コマンド・ライン リセット 新 MS-DOS プログラミング入門 101

な u 0 C + + クッションスレゼントキャンペーン ポーランドセンター加盟店にて実施 / ( ' 93 年 2 月 ~ 3 月末まで ) B 0 R ー A 0 TURBO 0 ◆ The レⅲ〇わト O Programming C も C + + も、初めがカンジ選ぶなら TURBO C + + 。 気軽に始められる Quick な C / C + + コンヾイラは、ポ - ランドだけ。 ANCI C 、 AT@T C + + に対応 / Turbo C + + は、 C と C + + 両方に対応した超高速 コンパイラです。 OS に関しても、 MS-DOS 版の 「 2nd Edition 」、 Windows 版の「 for Windows 」の 2 種類を用意。手頃な価格で、抜群の操作性と豊 富な機能を備えた、これから C / C + + プログラミング に挑戦しようという方には最適な入門ツールです。 ■快適な操作性を約束する統合開発環境 Turbo C + + は、開発に必要な編集・コンヾイル・リ ンク・テッグなどの作業を、マウス対応のオーバー ラッブマルチウインドウ上て、快適に実現する統合環 境を装備。その抜群の操作性は、 Turbo シリーズ がベストセラーを続けていることが証明しています。 ■気軽にエントリーできる手軽さがうれしい Turbo C + + の魅力は、なんといっても「手軽さ」。 いきたい。そんな方のために、ボ、一ランドはプロ 価格面て、の手軽さもさることながら、動作環境の面 フェッショナル向けの超高速最適化コンパイラ製品 も見逃せません。 2nd Edition なら 640KB 、 for 「 BORLAND C + + 」を用意。いって、も必要なとき、 Windows て、も 2MB 以上のメモリ容量て、作動。 プロ仕様のコンパイラにバージョンアップて、きます。 メモリ増設といった手間もコストもかけずに済みます。 ■上級者レベルへの移行も安心・スムーズです ■動作環境 ( 適応機種 ) Turbo C + + て、 C / C + + プログラミングを修得し ・ Turbo C + + 2nd Edition ・・・ NEC PC ー 9800 シリーズ ( ハイレゾモード対応、 LT は除く ) 、 た後、もっと高度なアプリケーション開発に挑戦して EPSON 286 / 386 シリーズ ・ Turbo C + + for Windows ・・・ NEC PC ー 9800 シリーズ、 PC ー 98 / H98 シリーズ、 EPSON 286 / 386 シリーズ、 IBM PS/55 シリーズ (DOS/V 対 応版のみ ) ※ MS-Windows Ver. 3.02 以上必要 ・価格 ( 本製品の価格には消費税は含まれません ) \ 20 , 000 Turbo C 十十 2nd Edition ・・ ¥ 29 , 800 Turbo C 十十 for Windows C + + 理解への近道・ビデオによる℃ + + 集中講座」 ポーランド社ディレクターの D. lntersimone が、豊富なプログラミング画面や アニメーションを駆使して、オプジェクト指向プログラミング言語 C 十十をてい ねいに分かりやすく解説。自宅にいながら、これからの言語 C 十 + が手軽に 学習できます。まさに " C + + プログラマへの最短距離 " となることでしよう。 THE WORLD OF 0 + ・価格 : \ 20 , 000 ( 税別 ) ※ A 日 Borland products are tradema 「 ks 0 「「 egistered trademarks Of BorIand lnternational, lnc. OBorland lnte 「 national, c. ※ Windows は米国マイクロソフト社の商標です。その他、商品名は一般に各社の商標です。 ボーフノト株式ネ土〒 151 東京都渋谷区笹塚 1-64-8 笹塚サウ = ビル TEL. 03-5350-9380 FAX. 03-5350-9369 、詳しくは功タ。グを = 請求くださ 0 、 く資料請求番号 F04 〉 T 1 0 1 4 5 2 5 0 2 0 9 8 7 雑誌 14325 ー 2 ◎ソフトバンク凸版印刷 Printed in Japan C + + セミナー実施中 / C 十十に関する基礎概念やプログラミン グ方法のセミナーを行っています。詳し くは下記までお問い合わせください。 ポーランド・トレーニングセンター受付 TEL. ( 03 ) 5350 ー 9366 FAX. ( 03 ) 5350 ー 9386 を 0 ーーー・ 0 II 川服Ⅲ川

List d. c C. C 1 : #include く stdiO. h 〉 2 : #include く stdlib. h> /*rand() のため * / 3 : #include く time. h> /*time() のため * / 4 : 5 : char *strC][4]={ { " じいちゃんが " " ぐうぐう " , " いびきをかいたので " , " ねむれなかった . 6 : { ”パイクが ". " ビンビン " , " 走ってきたので " , " かっこよかった . " } , 7 : { " ばあちゃんが " , " 寝ているじいちゃんを” , ”ふんづけたので " を”おかしかった . 8 : { " ぼくが” , ”早起きして” , ”散歩したので " , " 気持ちよかった . ” }. 9 : { " 夜の料理が " , " スーパーミラクル " , " 豪華だったので " , " おいしかった . " } , { " 文を " , " 作るのが” , ”面倒なので” , ”手抜きした . ” } , {NUL し NUL し NULL, NULL}, 12 : 15 : VOi d syaberu(char *s) printf( ” %s ” ,s); 20 : main() int max; / * 発言データの数 * / 22 : 23 : i nt i : 24 : for (max=0;strCmax] C0]!=NULL;max + + ): / * 発言データの数を数える * / 25 : puts ( " ー伊香保の旅の出来事ー " ) : 26 : srand((unsigned int)time(NUL い ): / * 乱数を初期化 . 時間を乱数のたねにする * / 27 : 28 : while(l) { 29 : for ( i = 0 : i く 4 ; i + + ) { 30 : syaberu(str[rand()%max] [i]) ; 32 : putchar('%n'); 33 : 34 : 1 : #include く stdiO. h> 2 : #include く stdlib. h> /*rand() のため * / 3 : #include く time. h> /*time() のため * / 4 : 5 : char *strC) [ 4 ト { { " じいちゃんが " , " ぐうぐう " , " いびきをかいたので " , " ねむれなかった . " } , 6 : トばあちゃんが " , " 寝てるじいちゃんを " , " ふんづけたのでä', " おかしか。た . 7 : 8 : " ぼくが " , " 早起きして " , " 散歩したので " , " 気持ちよかった . " } , 9 : " 夜の料理が " , " スーパーミラクル " , ' 豪華だったので " を " おいしかった . " } , " 文を " , " 作るのが " , " 面倒なので " , " 手抜きした . " } , NULL, NULL, NULL, NULL}, 15 : void syaberu(char **s) / * ここが d. c と違っているところです . * / printf("%s",*s); 18 : } 20 : main() int max; / * 発言データの数 * / 22 : 23 : for (max=O; *strCmax] ! : N 乢し max + + ) : 25 : 26 : puts ( " ー伊香保の旅の出来事 -- " ) : srand((unsigned int)time(NULL)); / * 乱数を初期化 . 時間を乱数のたねにする * / 28 : 29 : while(l) { 30 : for ( i ニ 0 : i く 4 : i + + ) { syaberu(str[rand()%max] + i ) : 32 : 33 : putchar('\n') : 34 : 35 : / * 発言データの数を数える * / ケてみせたのは , どうやら『この手紙が本 に載るのて、読者の心をゆさぶってやろう』 という策略だったようだ。 ところて、 , 今月は吉夫君のプログラムに 勘違いがあるようだが , 皆さんは見つける ことがて、きるだろうか。 【追伸 ( 丹羽信夫より ) 】 皆さん , ロバート氏との勉強会に参加し ませんか ? 氏の勉強の助けとなる教材プ ログラム ( 迷走プログラム ? ) に , 楽しい解 説をつけてぜひ送ってください。応募作は 付録ディスクまたは誌面にて可能なかぎり 紹介し , 掲載作には薄謝を進呈いたします。 送り先 : C マガジン編集部 「迷走プログラミング係』 または , ノヾソコン通信 NIFTY-Serve PFD01142 ( 丹羽信夫 ) までお願い します。 かならず , 本名と住所をお知らせください。 なお , 応募作には手を入れる場合があり ますのでご了承ください。 ろと見ているばかりでした。無理にその場 から引っ張ってきましたが , じいちゃんは 佐々木吉夫 イヤそうでした。 追伸 : 伊香保プログラム改造型を送ります。 b. c です。文章の中身も組み換えるよ うにしてみました。おふざけです。 文字配列の個数をかぞえるようにし たので配列のデータの個数を気楽に 増やすことができます。 NULL という のはデータ最後のしるしのために入 れておきました。これでも , いちお うは工夫しているんですよ。 数日後今度は吉夫君だけの手紙が届いた。 丹羽さん。伊香保プログラム , あまりお もしろくなかったかもしれませんけど , ほ は学校の勉強も不得意ですし。考えるのが くなりにまた改造してみました。 c. c です。 佐々木吉夫 苦手です。 d. c でも同様に動くのですが , 違いがよくわ その後 , 町て、ロバート氏と出会ったが , かりません。前のと同じく文字列表示のと 変わりなく元気なように見えた。 どうやら ころを別の関数として追いやったのがちょ 心配無用のようた。ただ , 「楽しみにしてい っとぜいたくな特徴ですが , ここで char * た C マガ読者の皆さんからの迷走プログラム * s などとして引数を受けているところがわ が今回 1 本も応募されなかった」ということ からず苦労しました。ポインタは中学生の てちょっとさみしそうだった。吉夫君にポ ほくには荷が重いのかもしれません。ばく ノ ' 丹羽信夫の迷走プログラミング 169

れ以外の関数は見えても意味がないのて、あ る。そこて、 , 外部から呼び出す関数以外を static とし , 隠蔽するためにひとつのファイ ルにまとめたのだ しかし結果としては BPlus の処理を記述 するソースファイルが 90K バイトにもなって しまい , あまりおもしろくない。さらに検 討が必要て、あるといえよう。 BPL は現在最新バージョンが 52 て、ある が , 細かい変更により不規則に更新されて いる。最新のソースプログラムは NIFTY- Serve のプログラマーズフォーラム (FPRO G) て、公開されているのて、 , あまりおもしろ くないプログラムて、あるが , 参照していた だければ幸いて、ある ( 編集部注 : 1992 年 12 月 12 日現在のものを付録ディスクに収録した ) 。 BPIus のプロトコルの仕様概略はすて、に 述べたのて , 以下は , ポイントとなる処理 がどのように記述されているかを中心にい くつかの処理を例に説明をする。 バ , ット処理 ( 受信 ) いうまて、もなくもっとも重要な処理がパ ケットの送受信処理て、ある。 BPL の中て、 は , wait for acknowledge という関数がパ ケット受信処理になる。 BPIus の処理の中 て、もっともややこしい処理なのだが , ドキ ュメントを参考にして , てきるだけ忠実に 書いたつもりのものが List 2 て、ある。しか し , C のプログラムとして見ると , あまり美 しい構造とはいえないようて、ある。 構造としては , while ループの中て、 , デー タを受信して , それによってバケットが完 成したり , ACK や , そのほかコントロール コードを受け取れば , 受信データに応じた 処理を行うという感じて、ある。 sts という変 数が終了条件になっている。 あまり美しくない点を指摘すると , まず , チェックサムを計算する処理のために , < c hecksum > という変数がアドレス渡しとし 62 C MAGAZINE て使われていること。 1993 2 という変数を外に見せたくないために こは , < checksum > List 3 : 5 : 6 : 9 : 10 : 13 : 14 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 32 : 33 : 35 : 36 : 37 : 38 : 39 : 40 : 43 : 44 : 45 : 46 : 48 : 49 : 50 : 52 : 53 : 54 : 55 : 56 : 58 : 59 : 60 : 62 : 63 : 64 : 66 : 68 : 69 : 76 : * packet を受け取った場合は、 1 を戻す。内容は current-packeto * ack が得られたら、 0 を戻す。 2 : / * ACK 待ち状態の FSA wait for acknowledge 関数 sts ニ s-resend-packets() : case S_Resend-Packets: break; sts s-send-enq() ; case S_Send-ENQ. break, s ts = 0 : s_send_ack(); case S_Send_ACK : break; sts = s-send-nak ( ) : case S_Send-NAK : break; sts = s-verify-packet() , case S-Ver i fy-Packet : break , sts s-veri fy-cks(checksum) : case S-Vei fY-CKS : break. sts s-veri fy-crc(checksum) , case S-Ver i fY-CRC: break; sts = s-get-crc(&checksum) ; case S_Get_CRC: break; sts = s-get-check(&checksum) : case S_Get-Check: break; sts = s-get-data() : case S_Get_Data: break; sts = s-dle-b-seen() : case S_DLE_B_Seen. b reak ; StS = s_dle_seen(receive) : case S_DLE_Seen: break ; sts = s_get-dle(receive) : case S_Get_DLE: svitch (acknovledge-status) { vhile (sts > = の { after-enq = 0 : int sts UWORD checksum; 7 : STATIC int wait_for-acknovledge(int receive) * error の場合はく 0 break; if (sts = FINISH) { sts = acknovledge-status return Sts; = S-Verify-Packet ? 1 : 0 :

ける n クイーンの解の個数 ( 対称性は考慮し ていません ) をまとめたものて、す。 この表にあるように , n = 15 のときて、約 2 00 万個 , n = 17 のときて、約 9000 万個の解があ り , n が増えれば解の個数はさらに爆発的に 増加します。これて、は解の個数を数えるだ けて、も膨大な時間がかかりますし , まして やそれを解くことはて、きそうもないことて、 す。つまり , 100 クイーンの全解探索を行う ことはあまりにも無謀なことて、あり , 解を ひとつ求めることに目標を変更したほうが 賢明といえます。 n クインの全解探索は n = 17 くらいが限度である しかし , 解をひとつ求めればよい しても , 100 クイーンの解を求めることは容 易て、はありません。筆者は「高速版」のプロ グラムて、 n を増加させながら調べてみました (TabIe 3 参照 ) が , n = 29 くらいが我慢て、き る限界のようて、した。つまり , 最初のひと つの解だけを求めるにしても , 100 クイーン の解を求めるためには , 前回紹介した「高速 版」のプログラムてはまったく不十分て、す。 時間のかかる理田 解の探索に ークした部分て、す。それぞれ順に解説して 疑似コードの中にコメントとして A, B とマ をわざと省略した部分があります。それは , てすが , このアルゴリズムには詳細の動作 クトラックによる n クイーンのアルゴリズム まず List 1 をご覧ください。 List 1 はバッ していないかを調べてみることにしましよ はありませんよね。どこかて、ムダな計算を 理て、もありますが , それては改善の見込み 言て、片づけるのは簡単て、すし , 一面の真 うか。遅いのはバックトラックの宿命さの ンプログラムはなぜ時間がかかるのて、しよ それて、は , バックトラックによる n クイー こて、 , Fig. 1 をご覧ください。これは , 8 クイーンを解く過程を図解したものてす。 ここに示す局面は列 = 1 , 2 , 3 の試行を終 え , 列 = 4 に置くクイーンを決めようとして いるところて、す。列 4 に置くクイーンの決め 方によって , プログラムのスピードが変わ ってきます。まず , 普通版のプログラムて は , 行 = 1 ~ 8 を順にチェックして , チェッ クに合格したところにだけクイーンを置こ うとするものて、す。 Table 3 n クイーンの解をひとつ求めるのに要する時間 28 195 29 104 30 実行時間 20 10.9 27 30.0 単位 CPIJ : 日 03 日 6SX / 1 6MHz コンパイラ : LSI C ー 86 Ve 「 . 3.30 試食版 e ー se 解の表示 : i f ( すべて列にコマを置いた ) void backtrack(col) List 1 n クイーンを解くアルゴリズム rov にコマを置く : if (rov は条件を満たす ) { for ( 未使用の行 rov すべてについて ) / * A * / / * 列 c にコマを置き得る行 rov を探す * / n クイーンのアルゴリズム ( 抽象化したもの ) rov に置いたコマを戻す , backtrack(col + 1 ) : / * 次の列の試行 (B) * / col を試行済みにする : col = 未試行の列のひとっ : se { 解の表示 : i f ( すべて列にコマを置いた ) void backtrack(level) List 2 から削除する のうち未削除のものを双方向リスト c 引列 , ro 行の利き筋にあたる行 for ( 未試行の列すべてについて ) { クイーンを置く (c 引列 , rov 行 ) Li st 3 クイーンを置く rov に置いたコマを戻す ; / * まだクイーンを置いていない列の試行 * / backtrack(level + 1 ) : rov にコマを置く : for (col 列の中でクイーンを置くことのできる行 rov すべてについて ) { 82 ことにしましよう。 C MAGAZINE 1993 2

Table 2 にテストしたソースと各処理系に MS ー DOS の予約したソフトウェア割り込み DOS / 4G に付属しているユーティリティ pm info の出力結果て、ある。この中の Protected/ よるコンパイル結果を示す。これは単純な ( おもに int21h システムコール ) ての OS カーネ 関数呼び出しの最適化を調べたものて、ある Real switch rate の値からわかるとおり , ルを呼び出すことにより実現されている。 が , レジスタ呼び出しをしている MS-C と W この切り換えには少なからず時間がかかる。 WATCOM C のオプジェクトのように ATCOMC て、は非常に洗練された出力が得 したがって , プログラムが文字表示を多用 DOS 工クステンダ上て、動作するシステムの られた。 f00 ( ) の最終行、、 return j ; 〃を add すると速度低下を引き起こす。たとえば Li 場合も , そのようなシステムコールが発生 1 ( ) へのジャンプにまて、最適化したのは WA した時点て、検知され , 通常はプロテクトモ st 3 のような文字が多く表示されるプログラ TCOM C だけて、あった。 ードて、動いているところをリアルモードに ムを実行させると , Table 3 のようにリアル モードとプロテクトモードて、顕著な速度の List 2(a—c) は , List 1 のような末尾再帰 戻し , 引数などを MS-DOS に橋渡しし , 終 呼び出し関数を各処理系て、コンパイルした 了後再びプロテクトモードに戻る , という 差が生じる。 MS-DOS のシステムコールにかぎらず , 結果て、ある。関数 kakutani( ) は数学の角谷 形て、 DOS カーネルを利用している。 Fig. 6 は 予想 ( 正の奇数 n を 3 倍して 1 を足し奇数にな るまて、 2 て、繰り返し割る , という操作を繰り Fig. 6 P Ⅶ NFO プログラムによるマシン診断 ( 外部スロットプロテクトメモリ ) 返すと 1 になるという予想 ) を , 使わなくて もいいのにわざわざ再帰呼び出しを使って t 算させるものて、ある。 さすがにどの処理系もわざと書いた n 十 1 十 n * 2 を 3 * n 十 1 とみなして計算しているが , djgcc はこの計算を一命令にまて最適化して いる。また関数末尾の再帰呼び出しはその 関数自身の先頭へのジャンプに最適化て、き るのだが , MS - C は意外にもそれをしていな い。したがって , 引数によっては実行時に stack overflow が生じた。さらに MS-C は S I レジスタをムダに使っている。 List 2 ー (c) のアセンプリソースのコメント にも記述したが , WATCOMC の生成する オプジェクトは最適とまて、はいかないが , かなり洗練されていて比較的コンパクトて、 あるようだ。 ただし , このような軽めのソースて、も , 参考に付け加えた究極のマニュアル最適化 の結果 (List 2-(d)) と比べるとまだまだ青い こまて、やれというのはちょっと酷な気も するが・・・ DOS 工クステンダを使う うえでのウィークポイント プロテクトモード / リアルモード 切り換えのオーバヘッド MS-DOS において , ファイル入出力や文 字表示などの基本オペレーティング機能は Protected M0de and Extended Memory Performance Measurement ー 3. 95 Copyright 1988 , 1989 , 1990 bY RationaI Systems, lnc. DOS memory Extended memory CPU is 16. 2 MHz 80386. K bytes configured (according t0 BIOS). 4096 640 363 3072 K bytes available for DOS/16M programs. (DOS/16M memory range 1024K to 4096K ) 3. 1 ( 6. 5 ) MB/sec word transfer rate (vait states) . MB/sec 32-bi t transfer rate (wait states). 3. 8 ( 13. の MB/sec word transfer rate [Static COIumn]. 5. 1 ( 2. 5 ) MB/sec 32-bit transfer rate CStatic COIumn]. 5. 1 ( 8. 5 ) Overall cpu and memory performance (non-floating point) for typical DOS programs is 2. 43 土 0. 19 times an 8MHz IBM PC/AT. Pr0tected/ReaI switch rate = 5285 / sec ( 189 usec/switch, 112 up + 76 down), using DOS/16M switch mode 1 (NEC 9801 ). 一三ロ 0 LO 0 一 . り 0 -4 ・ 0 4 — 6 6 00 Fig. 7 P Ⅶ NFO プログラムによるマシン診断 ( 内蔵プロテクトメモリ ) Protected M0de and Extended Memory Performance Measurement Copyright 1988 , 1989 , 1990 bY Rational Systems, lnc. CPU is 22. 9 MHz 80486. DOS memory Extended memory K bytes configured (according tO BIOS). 11136 640 K bytes available for DOS/16M programs. 289 10240 (DOS/16M memory range 1024K t0 11264K ) MB/sec word transfer rate (wait states) . 5. 4 ( 5. 5 ) 5. 4 ( 5. 5 ) MB/sec 32-bi t transfer rate (wait states). 10. 8 ( 5.5 ) 10. 8 ( 5. 5 ) MB/sec word transfer rate CStat ic Column]. 9. 4 ( 2. の 9. 4 ( 2. の MB/sec 32-bit transfer rate CStatic C01umn]. 18. 8 ( 2. の 18. 9 ( 2. の Overall cpu and memory performance (non-floating point) for typical DOS programs is 3. 59 士 0. 50 times an 8MHz IBM PC/AT. Protected/Real svitch rate = 8387 / sec ( 119 usec/switch, 71 up + 48 down), using DOS/16M svitch mode 1 (NEC 9801 ). ー 3. 9 5 ( ? ) ことがおわかりいただけると思う ( まあ , 72 C MAGAZINE 1993 2

ラスラと書けるようになりたいものてす。 一方 , これまて、何度も述べているように バックトラック法に基づくアルゴリズムは 指数関数的な実行時間を要することがある ため , 高速化を工夫しなければならないケ ースが多くあります。しかも n クイーンの例 て、見てきたように , 目覚ましい高速化を行 うためには問題固有の性質を利用すること がぜひとも必要になります。 , バックトラックを道具として使い こなせない状態て、あれば , バックトラック を使うだけて、精一杯て、 , 上述のような高速 化まて、はとても頭が回らないてしよう。バ ックトラックの習熟をお勧めする所以はこ こにあります。バックトラック法の応用範 囲は非常に広いのて、 , 身近な問題をバック トラック法によりどんどん解いてみること により , 習熟度を深めていただきたいもの て、す。 力なものなのて、 , 次回も引き続きこのテー ックトラック法の高速化としては非常に有 ③と④について説明しました。これらはバ ということになります。この中て、 , 今回は ④試行の順序を工夫する ③ムダな候補を生成しないようにする ②順列の生成を高速化する ( 双方向リスト ) ①テストの過程でテストする して今まて、出てきたものをまとめると , さて , バックトラックの高速化の手法と 出版 筧ほか , 『プログラミングセミナー』 , 共立 波書店 石畑清 , 『アルゴリズムとデータ構造』 , 岩 参考文献 マについて解説する予定て、す。 Themsky(T) , 「 7bits 女王多くして」 , fbi t 』 V01. 20 , No. 11 , 共立出版 , 1988 Li st 6 head[i]. prev = &headCi - head[i]. next = &headCi + 1 ] ; for (i head[0]. prev = &head[N] ; headCi]. n-node = N; head[ i]. col-no set-column(&head[i]) : head CN]. next = &head[0] : col-t *min-col (col-t *head) COl_t *p, *min-p; = INT_MÅX : int min_c / * クイーンを置ける位置の * / / * 最も少ない列を返す * / for (p = head->next; P ! = head; P = p->next) if (p->n-node く min-c) { / * マス目を一つ候補リストから削除する * / VOid deletel(col-t *CP, int current-col' int r) ー p->n-node ; return min—p; min—p min_c node-t *rp; if (r く 1 Ⅱ r > N) return ; = &cp->node_header[r] : if (rp->free = rp—>free current_col ; cp- 〉 n—node--; rp—>next->prev rp->prev; rp—>prev->next rp->next; / * どの列の試行時に削除したかを記録 * / / * 双方向リストからの削除 / * この列におけるマス目の数を減らす * / int r) void insertl(col-t *CP, int current-col, / * マス目を一つ候補リストに再挿入する * / node-t *rp; if (r く 1 Ⅱ r > N) return ; rp = &cp->node-header[r] ; i f (rp->free = current-col) { rp—>free rp—>prev->next rp—>next->prev cp->n-node 十十 ; / * どのコマの利き筋でもない状態にする * / / * この列におけるマス目の数を戻す / * 双方向リストへの再挿入 / * col-no 列 , ro no 行のクイーンの * 利き筋のマス目を候補リストから削除する void delete-elements(int col-no, col-t *cp; for ()p = head->next; CP ! deletel(cp, deletel (cp, deletel (cp, int = head, col_no, rov_no 十 col_no, rov— COI no, rov_ rov_no) ・ CP = cp->next) { col-no) : cp->col -no - cp->COl-no 十 col-no) : 88 年 C MAGAZINE 1993 2 / * c 引ー no 列 , ro を一 no 行のクイーンの void reinsert-elements(int col-no, int ro を - no ) * 利き筋のマス目を候補リストに再挿入する

て、はクイーンを左から順に置いていきまし たが , 左から順というのは必ずしも最良の 試行順序て、はなく , もっと効率のよい試行 順序が存在します。また , ある列の上て、ク ィーンを置く位置を決めるときは , 条件を 満たす位置を探し回るのて、はなく , もっと ダイレクトにクイーンを置ける位置を求め る方法が存在するはずて、す。具体的な方法 概略設計 については次節て、検討します。 度に決めることはて、きないのて、 , 順に詳細 ければならないことがあります。全部を一 ムを設計するためには , いろいろと決めな 前節て、議論した内容に沿ってアルゴリズ 化していくこ 84 C MAGAZINE 1993 2 て、すね。したがって , クイーンを置くこと になります。これは Fig. 1 を見れば一目瞭然 置くことのできる行は列ごとに異なること 斜めの利き筋を考慮すると , クイーンを えてみましよう。 利き筋も考慮て、きるようなデータ構造を考 ことに相当しますが , これに加えて斜めの は , クイーンの横方向の利き筋を考慮する 管理しました。未使用の行に着目すること 着目して , 未使用の行を双方リストにより 前回示した「高速版」て、は , 未使用の行に いところて、す。 く見つけることのて、きるデータ構造がほし のて、 , このような条件を満たす行 r 。 w を素速 てについて for 文内の処理を行うことになる 中でクイーンを置くことのできる行 row すべ めの for 文の実現方法て、す。ここて、は co 冽の まず考えなければならないことは , 8 行目 す。 略を練るためには List 1 よりも適していま 化されているのて、 , アルゴリズムの基本戦 リズムは List 1 と似ていますが , より抽象 ンのアルゴリズムを示します。このアルゴ 討から行うことにします。 List 2 に n クイー ますは , おおざっぱなアルゴリズムの検 のできる行は列ごとに管理することにしま す。メモリ消費量が増加しますが , 高速化 のためにはしかたありません。具体的には , 列ごとにクイーンを置くことのできる行を 双方向リストて、持つようにすればよいて、し よう。この列ごとに管理された双方向リス トのイメージを Fig. 3 に示します。また , 双 方向リストについては前回詳しく解説した ばかりなのて、 , ここて、は解説を省きます。 次に , List 2 の 6 行目に出てくる未試行の 列のひとつの決め方について検討します。 これは前述のようにその列にクイーンを置 くことのできるマス目がいくつあるかによ り決めるのがよいて、しよう。クイーンの置 けるマス目が 0 個という列がひとってもあれ Fig. 3 チェス盤のテータ構造 行 ば , それ以上の試行は無意味て、あり , だま ってリターンするしかありません。また , クイーンの置けるマス目がひとっしかない という列があれば , その場所には自動的に クイーンを置くのがよいことになります。 て、は , すべての列について , クイーンを 置くことのて、きるマス目がふたつ以上ある ような場合はどうて、しようか。この場合に は , クイーンを置くことのできるマス目の いちばん少ない列から試行するのがよさそ うて、す。 Fig. 2 て、見ていただいたように , ク ィーンを置くことにより , ほかの列の試行 パターンを大幅に狭めることがてき , ひい ては試行錯誤の回数を減らすことがて、きる と思われるからて、す。