組込み関数 rand() は 0 以上 RAND_MAX 未満の乱数を返す関数である。 RAND_MAX はシステムに依存する。 乱数は初期化しないと常に同じ値の列になってしまうので、 何らかの方法で初期化する。よく用いられるのは時刻を用いて
srand((unsigned)time(NULL));などとすることである。 ただし数値シミュレーション等で用いる場合に、この方法で乱数を初期化した場合、 乱数の種を保存しておかないと、 同じ現象を再現できない。
unsigned seed; seed = (unsigned)time(NULL); srand(seed);などとして seed を同時に出力しておくと良いであろう。
例えば 0 以上 1 未満の乱数を得たい場合には
float a; a = 1. 0 / (RAND_MAX + 1.0) * rand();などとすれば良い。
課題 09.01
モンテカルロ法によって 2 の平方根の近似値を求めよ。
(0 以上 2 未満の乱数 x を繰り返し発生させ x2 < 2 となる確率を 2 倍すればよい。
繰り返しの回数が大きいほど精度は高くなる。)
課題 09.02
モンテカルロ法によって円周率の近似値を求めよ。
課題 09.03
区分求積法で二変数関数の重積分を求めるプログラムを書け。
多項式を C 言語で扱うことを考えよう。 ここでは簡単のため一変数のもののみを考える。 一変数多項式 a0+a1x+...+anxn を配列 {a0,...an} と考え、次数も併せて構造体を定義する。
typedef struct {
int deg;
float *coef;
} polynomial;
課題 09.04
多項式を上の形で定義し、その加法と乗法を行う関数を書け。
(ただしメモリの管理が大変ならば、適当な次数 N 以上の項を無視して
float coef[N] などとしても構わない。)
課題 09.05
長さ n の二つの自然数の列に対して、
辞書式順序でその大小を判定する関数を書け。
課題 09.06
n 次の置換 σ を数列 {σ(1),σ(2),...,σ(n)} で表す。
二つの置換の積を求める関数を書け。
課題 09.07
n 次の置換をすべて出力するプログラムを書け。
課題 09.08
集合 {1,2,3,...,n} の二つの部分集合 A, B に対して
A が B の部分集合であるかどうかを判定する関数を書け。
(まず、データをプログラム内でどのように表現するかを考えよ。)
課題 09.09
集合 {1,2,3,...,n} の二つの部分集合 A, B に対して
A と B の共通部分と和集合を求めるプログラムを書け。
課題 09.10
与えられた自然数を 2 進数として表示するプログラムを書け。
逆に 2 進数を 10 進数として表示するプログラムを書け。
同様に 2 以上 16 以下の n に対して
n 進数と 10 進数との変換を行うプログラムを書け。
(n が 10 を越えるときには a=10, b=11 などとして
アルファベットを数として扱う。)
課題 09.11
ハノイの塔について調べ、
それを解くプログラムを書け。
課題 09.12
ニュートン法について調べ、
それを実行するプログラムを書け。
課題 09.13
2 次、3 次の正方行列の行列式を求める関数を書け。
課題 09.14
2 次、3 次の正方行列が正則であるかどうかを判定し、
正則であるならば、その逆行列を求めるプログラムを書け。
課題 09.15
自然数 a, b の最大公約数を d とする。
このとき ax + by = d となる整数 x, y が存在する。
この x, y を求めるプログラムを書け。
課題 09.16
有理数を表す構造体を定義し、その四則演算を行う関数を書け。
ただし出力は常に既約分数となるようにせよ。
計算機内部ではすべての数は 2 進数で表されている。 このため、2 をかける、2 で割る、という操作は単に桁をシフトするだけでよく、 非常に効率よく計算できる。 またこのための単項演算子も用意されている。 a << b は a を左に b だけシフトした値を示す。 すなわち 2b をかけることになる。 a >> b は a を右に b だけシフトした値を示す。 すなわち 2b で割ることになる。 ただし小数点以下は切り捨てられる。 これらをシフト演算子と呼ばれ、 整数値に対してのみ用いることが出来る。 (通常はコンパイラの最適化機能によって a * 2 などは自動的に シフト演算子に置き換えられ、プログラムにどのように書いても 速さなどは変わらないようである。)
課題 09.17
シフト演算子を利用して、10 進数と 2 進数を変換するプログラムを書け。