Josephus problem(ジョセファスの問題)
いまN人が集団自殺しようとしているとして、まず全員が円陣に並び、その円の中のM番目の人を順に処刑する。一人死ぬと取り除かれ、円の大きさが1へることになる。
今N=9(つまり全員で9人)M=5(つまり5番づつ)とする。処刑される順番を求めよ。
解き方
円陣を引き伸ばして考えると全員で9と言うことは最後の一人になるまで9+8+7+6+5+4+3+2+1=45回隣に移動する。そこでいわゆる循環リストを円陣に見立てて割り当てる。
#include<stdio.h> #include<stdlib.h> struct node{int key;struct node *next;}; main() { int i,N,M; struct node *t,*x; scanf("%d %d",&N, &M); t=(struct node *)malloc(sizeof *t); t->key=1;/*1番目の番号付け*/ x=t; for(i=2;i<=N;i++) { t->next=(struct node *)malloc(sizeof *t); t=t->next; t->key=i;/*番号付け2番からN番まで*/ } t->next=x; /*最後の次は最初へ・・循環させる。*/ while(t!=t->next)/*t->next==tとなれば後一人しかいないということ*/ { for(i=1;i<M;i++) t=t->next;/*死のルーレットM-1番目でストップ*/ printf("%d\n",t->next->key); /*次はあなたの番*/ x=t->next;/*殺人個室へ連れて行かれるところ・・*/ t->next=t->next->next; /*円の中では彼は居なかったことになる。*/ free(x); /*殺害*/ } printf("%d\n",t->key);/*最後の一人を表示*/ }
非常に解読が面白いクイズだった。
①-2スタック
メモリの項で散々スタックの説明をしたがリストを使ったスタックの実装について説明する。
データ構造として最も重要なスタックだが、基本的な操作は2つだけで、プッシュとポップと言う概念からなる。プッシュはリストで言えば項目の挿入であり、ポップは項目の取出しである。
スタックを使った算術式を述べると
仮に
5*(((9+8)*(4*6)+7)と言う式
9+8をやってから4*6をやり続いて掛け算をしてから7を加え、最後に5を掛ける。
この手順をオペラントも含めて並べてみると
- 5を入れる。
- 9を入れる
- 8を入れる
- 9+8の答えを入れる
- 4を入れる
- 6を入れる
- 4*6の答えを入れる
- 9+8の答えと4*6の答えを掛けたものを入れる
- 7を入れる
- 9+8の答えと4*6の答えを掛けた答えに七を加える
- 5を掛ける
この手順をpushとpopで表すと
- push(5);
- push(9);
- push(8);
- push(pop()+pop());
- push(4);
- push(6);
- push(pop()*pop());
- push(pop()*pop());
- push(7);
- push(pop()+pop());
- push(pop()*pop());
こうなる。
pushとpopを除いて算術式で書くと
598+46**7+*
こうなることが分かる。
これをreverse Polish notation(逆ポーランド記法)もしくは後置記法と呼ぶ。
(これに対し通常の書き方をinfix(中置記法)という。)
逆ポーランドの利点は括弧が必要ではないことに尽きる。
これによりプッシュ、ポップの2つだけで簡単に算術式が書ける。
この一連の操作をリストを用いて実現する。
Eukleides(ユークリッド)のアルゴリズム
Elements(原論)の中の解法を用いて既約分数(これ以上割れない分数)を計算する。
難しく書いたが要するに
最大公約数は何か?と言う回答を吐き出すプログラムを作れればよい。
解答に至る手順として最大公約数(Greatest Common Divisor。以下gcd)を求めればそれを分子、分母共に割ってやればおのずと既約分数が出てくる。
さて、最大公約数を求める能率的な方法として古代ギリシャ人の解法を用いる。
これは「分母と分子を比べ分母が大きいなら分母と分子の最大公約数が分子と分母-分子の最大公約数に等しい。」ということに基づく。
混乱しないように例を挙げると、200/300という分数の最大公約数は200と100の最大公約数と等しいということだ。ただ、世の中こんなに単純な最大公約数ばかりではない。
そこから考えて、分母ー分子で出てきた答えを使えないだろうか?
さらに分子で引くと同様に「(分母ー分子)と分子ー(分母ー分子)の最大公約数」が「分子と分母-分子の最大公約数」に等しいのは分かる。
即ちこれを繰り返していけばいずれ引く値が同じになるところまで来る。
例として85/136は分母ー分子=51。85-51=34。51-34=17。34-17=17。17-17=0//
見やすくする為、一般化した式で書けば
- 分母をuと置き分子をvと置く。
- vとu-v {但しu>v}のgcdはuとvのgcdに等しい。
- u-vとv-(u-v){但しv>(u-v)}のgcdはvとu-v{但しu>v}のgcdに等しい。
- この動作を繰り返していき引く数と引かれる数が等しくなったときその数がuとvのgcdとなる。
ただ、これは常に引かれる数のほうが小さいと言う前提がある。
引かれる数の方が引く数より大きくなってしまった場合、
仮に41/161など161-41=120など。v<(u-v)となってしまったらプログラム内でその2つをひっくり返す動作(スワップ処理)をしなければならない。
一番簡単な処理として
- temp=a;
- a=b;
- b=temp;
と言うaとbの入れ替え動作があるので知っておくと便利。
では同様に6536/7144は分母ー分子=608。6536-608=5928。5928-608=5320。5320-608=4712。4712-608=4104。4104-608=3496。3496-608=2888。2888-608=2280。2280-608=1672。1672-608=1064。1064-608=456。608-456=152。456-152=304。304-152=152 152-152=0//
合っていてよかった。2888や456なんかが出てきてくれて嬉しい。ともかくこんな感じである。gcdは152。
プログラム例は
#include<stdio.h> int gcd(int u,int v) { int t; while (u>0) { if(u<v) {t=u;u=v;v=t;} /*swap処理*/ u=u-v; } return v; } main() { int x,y; while(scanf("%d %d",&x,&y)!=EOF) { if(x>0&&y>0) printf("x=%d y=%d gcd=%d\n",x,y,gcd(x,y)); } } 結果 6 4 x=6 y=4 gcd=2 200 300 x=200 y=300 gcd=100 6536 7144 x=6536 y=7144 gcd=152
といった感じである。
②型モデル
宣言はいつでもリストで似たような図をかける。
上の例で言えば
int(*func[10])(int a);
という宣言があったら、これを
fanc is array[10] of pointer to function(a is int) returning int.
fancはint型を返す関数(aはint)へのポインタの配列[10]
とよめた。ではリストで図示してみると、
___ 返す____ への ________ の________ int| →|関数| → |ポインタ| →|配列 |  ̄ ̄ |int |  ̄ ̄ ̄ ̄ |要素10 |  ̄ ̄  ̄ ̄ ̄ ̄
こんな具合である。
K&Rではオブジェクトの生成法は一般的に再帰的に適用可能である。
とあり、つまり大概の宣言はどんどん繰り返してくっつけていけますといっている。
この先頭を基本型と呼び、常にintやcharなどの型が来る。
そして2つ目以降を派生型とよぶ。
派生型は考えれば分かるが関数、ポインタ、配列、構造体、共用体がある。
また、最後の型(上の場合では配列[10])は型全体がどんなものか決めるもので、他に対し特に重要な意味を持っているので型分類と呼ぶ。
[型]不完全型
Cの型分類は
- オブジェクト型
- 関数型
- 不完全型
不完全型とは方のサイズが決まらない型の中で、関数型以外のものを指す。
逆にサイズが特定できるものを「オブジェクト型」と呼ぶ。
典型例として構造体のタグ宣言が挙げられる。
例えばこんな感じである。
struct a{ struct b *bb; }; struct b{ struct a *aa; };
こうなった時、どちらを先に宣言しても宣言がないと言われるだろう。
対処法はもちろんある。
#include<stdio.h> main(){ struct b; //*タグだけ先に宣言*// struct a{ struct b *bb; }; struct b{ struct a *aa; }; }
とタグだけ先に宣言してやると良い。
タグだけ宣言された時点ではその内容が分からない。
もちろんサイズも決められない。このような型を不完全型という。
サイズが決められないことにより、不完全型は変数や配列を取ることが出来ない。
ただしポインタだけは取ることが出来る。
又、関数型はサイズが特定できない。ということは上の「不完全型は変数や配列を取ることが出来ない。ただしポインタだけは取ることが出来る。」という言葉を当てはめると
関数型はポインタ型以外に派生できない。
という結論に達する。
不完全型とは方のサイズが決まらない型の中で、関数型以外のものと最初に述べたが、少し他と仕様が違うところがあるからである。
つまり、関数は引数の型を持つので関数は関数型と特別のものになる。
fanc(int a)←aが引数。
②Cの宣言解読
前橋和弥氏の書いた「C言語ポインタ完全制覇」では非常に面白い宣言の解読法がある。
ややこしい宣言は英語で読め。
というものである。
- int *f(); /*f:intへのポインタを返す関数
- int (*pf)(); /*pf:intを返す関数へのポインタ
と書かれても一行目は何とか読めても2行目がよく分からない。
2行目のpfの宣言を英語で読むと
pf is pointer to function returning int
(pfはintを返す関数へのポインタ)
と読める。
機械的に読む方法を載せる。
- まず、識別子に着目する(変数名や関数名)
- 続いて識別子に近いほうから優先順位に従って派生型(ポインタ、配列、関数)を解釈する。優先順位について少しだけ述べると(これだけ抑えれば読める。)
- 宣言をまとめるための括弧
- 配列を意味する[],関数を意味する()/*関数なら引数解釈に入る*/
- ポインタを意味する*
- 派生型を解釈したら、それを「of」または「to」または「returning」で連結する。
- 最後に、型指定子(左にあるintやdouble)を追加する。
- 日本語で解釈する。(逆から読む!)
と言うものであった。
非常に有用なので是非活用すると共に前橋氏に感謝する。
int hoge[10][3];
hoge is array[10] of array[3] returning int.
int *hoge[10];
hoge is array[10] of pointer returning int.
ホゲはint型を返すポインタの配列[10]。
int (*hoge)[3];
hoge is pointer of array returning int.
ホゲはint型を返す配列[3]のポインタ
int(*func_p)(double)
まずfunc_pに着目。
宣言をまとめる括弧の中を見る。[is]
続いて*をみる。[to]
次に関数を意味する()をつける。[()の中を解釈]
関数の引数の中(double)を見る。[returning]
最後に左端の型指定子を追加する。
func_p is a pointer to function(double) returning int
逆から読むと
func_pはint型を返す(引数がダブル型)関数のポインタ
atexit()のプロトタイプ宣言 int atexit(void(*func)(void));
同様にして
atexit is a function(func is a pointer to function(void) returning void)returning int.
atexitはint型を返す関数(fancはvoid型を返す関数(void)のポインタ)
因みにatexitはプログラムが正常終了したときに登録した関数を呼び出してもらう関数。
signal()のプロトタイプ宣言 void (*signal(int sig,void (*func)(int)))(int);
signal is function(sig is int,func is pointer to function(int)returning void) **returning** pointer to function(int) returning void
こうなるようなのですが私には何故signal is function() *returning*←となるのか理解できなかった。スミマセン
①プリプロセッサ
ソースファイルから実行ファイルが出来上がるまでにはプリプロセッサ、コンパイル、リンク、という段階を踏む。(下図)
プリプロセッサ コンパイラ {ソースファイル}→ {プリプロセス} →{コンパイル} #ifdef等の処理 オブジェクト ファイルの生成 リンカ → {リンク} → {実行ファイル} オブジェクトファ イル同士の結合
これから分かるようにまずプリプロセッサが起動される。
つまりプリプロセッサがコンパイラすら行わせないような処理が出来るということだ。
このメリットはバグがあろうが無かろうがそもそもコンパイルをしないで飛ばせる。
プリプロセッサで行える主な処理は次のものである。
ディレクティブ | 機能 |
#define | define名を定義する |
#undef | define名を解除する |
#include | インクルードする |
#if〜#elif〜#else〜#endif | 条件式の結果で分岐する |
#ifdef〜#else〜#endif | define名の定義状態で条件分岐する |
#ifndef〜#else〜#endif | define名の定義状態で条件分岐する |
#error | エラーメッセージを表示する |
#ifも感覚で使えるだろうが式の評価結果に応じてソースファイルをスキップさせる。
#include<stdio.h> main(){ int n=1; printf("test-->"); #if 0 printf("n=%d\n",n); #endif } 結果 test-->
1にしたら
#include<stdio.h> main(){ int n=1; printf("test-->"); #if 1 printf("n=%d\n",n); #endif } 結果 test-->n=1
となり#if〜#endifの間が出てくる。
もちろんコンパイル前の処理なので定数以外使えない。
#ifdefはifとdefineをつなぎ合わせたもの。
#ifndefは#ifdefの否定版。if !defineをつなぎ合わせたもの。
#undefはdefineを無くす
#errorは「コンパイラ時」にエラーメッセージを表示
#include<stdio.h> #define FALSE 0 #define TRUE 1 #if defined(TRUE)||defined(FALSE) #undef TRUE #undef FALSE typedef enum{FALSE,TRUE}BOOL; #else #error "not defined" #endif main() { BOOL flag=FALSE; printf("%s\n",flag==TRUE?"TRUE":"FALSE"); } 結果 FALSE
こんな感じだがたとえば#if defined(TRUE)||defined(FALSE)を
#if defined(2RUE)||defined(4ALSE)
とかに変えて見るとコンパイラ時に
致命的エラー F1003 priprosessa.c 11: error 指令: "not defined"
と出てくる。
また定義済みdefineといって勝手に最初っから定義されて使えるものがいくつかある。
define名 | 中身 |
__LINE__ | 参照したソースファイルの行番号 |
__FILE__ | 参照したファイルの名前 |
__DATA__ | コンパイルしたときの日付(文字列) |
__TIME__ | コンパイルしたときの時刻(文字列) |
__STDC__ | ANSI Cに準拠したコンパイラである。 |
使い道はあまりないが
#include<stdio.h> main() { printf("このファイルは%s\n",__FILE__); printf("ただいま%d行目\n",__LINE__); printf("只今の時間は%s\t%s\n",__DATE__,__TIME__); #if defined(__STDC__) puts("準拠コンパイラ"); #endif } 結果 このファイルはdefine__.c ただいま5行目 只今の時間はDec 15 2005 15:17:44
こんなことも出来る。
NULLと0と'\0'
文字列の終端にNULLを入れる間違いが多くある。
array[len]=NULL;
これは環境によって動くが間違いである。
文字列は「ナル文字」で終わるのであって「ヌルポインタ」で終わるのではない。
ナル文字とは「全てのビットが0である文字」と規格され、'\0'で表す値がゼロのchar型のことである。
確かにstdio.hで#define NULL 0と書かれているので'\0'と書いても0と定数で書いても間違いではないことが多い。
だが0と言うものが定数であるのかヌルポインタであるのか分からないときがある。
main() { int *p=6; }
と記述すると”警告 W8069 null.c 3: 移植性のないポインタ変換(関数 main )”と警告が出る。(bolandC++compiler)
これは当然、定数であるint型がポインタに変換されているからである。
だが
main() { int *p=0; }
とすると警告文が消える。これは
「コンパイラがNULLポインタであると勝手に判断したから」
おこるわけである。
コンパイラは
- プロトタイプ宣言していない関数の引数
- 可変長引数の関数の、可変部の引数
と言う局面ではポインタとして扱うべき文脈が分からない。
プロトタイプ宣言がしてあれば分かるのでプロトタイプ宣言は絶対行うようにする。
最終的な結論としては
文字列の終端には'\0'を使っておけば良し。
と言うことである。