C言語の基本 - 計算機班wiki

上へ

課題１～９は自力で解けるようになりましょう。１０～１２は暇がある人はやってみましょう。

課題1　if文と数学関数

二次方程式

の実数解を求めよ。
a, b, cを入力として、実数解をすべて出力せよ。実解がないときはその旨を出力せよ。
必要知識：入出力、if文、数学関数
解答例：t1-1.c

課題2　for文

ライプニッツの公式を用いて円周率を計算せよ。
6桁の精度で合わせるにはどれだけ反復する必要があるか。
必要知識：for文
解答例：t1-2.c

課題3　乱数

モンテカルロ法で円周率を計算せよ。
乱数の使い方については解答例を参照のこと。
ライプニッツの式よりも収束が遅いのが分かるだろうか。
必要知識：if文、for文、乱数
解答例：t1-3.c

課題4　配列

10個の整数を入力し、それを小さい順に並べて出力せよ。
これができたら、n個の整数を乱数で生成し、それを小さい順に並べるプログラムに改良せよ。(O(n^2)の方法：計算速度がnの二乗に比例するアルゴリズムで良い)。
nが増えるに従って、計算時間がどのように増えるか調べよ。
aという名前のプログラムの計算時間を測るにはtimeコマンド

time ./a

を使う。
また、大量の出力を画面に表示させるには時間がかかるので、

time ./a > 1-4.out

というように書くと、結果をファイル「1-4.out」に書いてくれるので便利。
必要知識：入出力、if文、for文、配列
解答例：t1-4.c

課題5　多次元配列

２つのn*n行列を乱数で生成し、その行列積を計算するプログラムを作成せよ。
nを増やすと計算時間がどのように増えるか調べよ。
必要知識：for文、乱数、多次元配列
解答例：t1-5.c

課題6　関数定義

を計算する関数を作れ。
いくつかのxに対してこの関数を呼びだして、結果をファイルに出力し、Excelか何かでグラフにしてみよ。tanh(x)のグラフと同じになるはずである。
プロトタイプ：double mytanh(double x);
必要知識：数学関数、関数定義
参考：ここの9, 10章
解答例：t1-6.c

課題7　ポインタ

二つのint型ポインタを引数として、二つの中身を入れ替える関数を作れ。
すなわち、

int a=3, b=5;
swap(&a, &b);

と実行すると、aが5、bが3になる。
なぜポインタを使う必要があるのか考えてみよ（swap(a, b)ではなぜいけないのか）。
プロトタイプ：void swap(int* a, int* b);
必要知識：関数定義、ポインタ
参考：ここの31, 32, 33章
解答例：t1-7.c

課題8　配列の渡し方

整数nと、n個の要素からなる配列x, yへのポインタ、double型のポインタcx, cyを引数として、cx、cyにn個の要素からなる座標列(x[i], y[i])の重心が入るような関数を作れ。
たとえばx[] = {3, 1, 5}, y[] = {1, 5, 9}のとき、関数を呼び出すと、cx = 3, cy = 5となる。
プロトタイプ：void center(int n, double x[], double y[], double* cx, double* cy);
参考：ここの31, 32, 33章
解答例：t1-8.c

課題9　再帰

二分探索法を実装せよ。
n個の昇順に並んだ数列a[]の中に、数sが存在するかどうかを調べる。
具体的には次の関数を作る。
int mybsearch(int a[], int left, int right, int s);
a：小さい順に並んだn要素の配列
left：探索範囲の左端
right:探索範囲の右端＋１
s：探したい整数
戻り値：a[left]～a[right-1]の中にsと等しいものがあれば1を、なければ0を返す。

方針１：a[left]～a[right-1]まで全てを愚直にsと比較し、等しい物があるか探す。
方針２：a[(left+right)/2]を見て、sより大きければmybsearch(a, left, (left+right)/2, s)を呼び出す。小さければmybsearch(a, (left+right)/2, right, s)を呼び出す。ただし、探索範囲が１つだけの時は、その一つとsとを比較して0, 1を返す。
このように関数mybsearchの中で同じ関数mybsearchを呼び出すのを、「再帰呼び出し」という。

方針１の計算時間はO(n)、方針２はO(log(n))である。実際に大きなnに対して双方を走らせてみて、速度を比較せよ。このとき配列を乱数で生成するとどっちもO(n)かかってしまうので、入力をあらかじめファイルに用意しておくと良い。
ファイルから入力を読み込むには、

./t9.in > ./t9

のように「>」記号を使う。
参考：再帰
解答例：t1-9.c

課題10　腕試し：特殊関数の計算

ルジャンドル多項式を計算せよ。（引数n, x）
この漸化式を使うとよい。
解答例：legendre.c

課題11　腕試し：クイックソート

クイックソートを実装せよ。
課題4と速度を比較せよ。
解答例：quicksort.c

課題12　腕試し：ローレンツアトラクタ

オイラー法でローレンツアトラクタを計算せよ。
結果をExcel、gnuplot、Mathematicaなど好きなもので可視化せよ。
解答例：lorentz.c

コメント欄

• 解けたらコメントを書こう！ -- mattya (2011-10-23 01:12:58)

---