Yet Another Clang Problems は M.Hiroi がＣ言語の勉強で作成した簡単なプログラムをまとめたものです。拙作のページ Yet Another Prolog Problems や Yet Another Scheme Problems などのＣ言語バージョンになります。同じような問題が多くなると思いますが、あしからずご了承くださいませ。
次のような九九表を表示する関数 ninety_nine を定義してください。
void ninety_nine(void);
| 1 2 3 4 5 6 7 8 9 ---+--------------------------- 1 | 1 2 3 4 5 6 7 8 9 2 | 2 4 6 8 10 12 14 16 18 3 | 3 6 9 12 15 18 21 24 27 4 | 4 8 12 16 20 24 28 32 36 5 | 5 10 15 20 25 30 35 40 45 6 | 6 12 18 24 30 36 42 48 54 7 | 7 14 21 28 35 42 49 56 63 8 | 8 16 24 32 40 48 56 64 72 9 | 9 18 27 36 45 54 63 72 81
整数 n から m までの和、二乗の和、三乗の和を求める関数 sum_of_int, sum_of_square, sum_of_cube を次に示す公式を使って定義してください。なお、int ではすぐにオーバーフローするので double を使って計算してください。
double sum_of_int(int n, int m); double sum_of_square(int n, int m); double sum_of_cube(int n, int m);
x の y 乗を求める関数 power を定義してください。ここでは、x を double, y を int とします。
double power(double x, int y);
下図に示すフィボナッチ数を求める関数を定義してください。
int fibo(int n);
フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, .... という直前の 2 項を足していく数列になります。
整数 n を b 進数 (2 <= b <= 16) で画面 (標準出力) に表示する関数 print_int を定義してください。
void print_int(int n, int b);
n 個の中から r 個を選ぶ組み合わせの数 \({}_n \mathrm{C}_r\) を求める関数 combination を定義してください。
int combination(int n, int r);
1 から n までの数字から m 個を選ぶ順列を画面に表示する関数 permutations を定義してください。
void permutations(int n, int m);
1 から n までの数字から重複を許して m 個を選ぶ順列を画面に表示する関数 repeat_perm を定義してください。
void repeat_perm(int n, int m);
1 から n までの数字から r 個を選ぶ組み合わせを画面に表示する関数 combinations を定義してください。
void combinations(int n, int r);
1 から n までの数字から重複を許して r 個を選ぶ組み合わせを画面に表示する関数 repeat_comb を定義してください。
void repeat_comb(int n, int r);
リスト : 九九表 (yacp01.c)
#include <stdio.h>
void ninety_nine(void)
{
printf(" | 1 2 3 4 5 6 7 8 9\n");
printf("---+---------------------------\n");
for (int i = 1; i <= 9; i++) {
printf("%2d | ", i);
for (int j = 1; j <= 9; j++)
printf("%2d ", i * j);
printf("\n");
}
}
int main(void)
{
ninety_nine();
return 0;
}
九九表は二重の for ループで簡単に作ることができます。printf の書式 %2d の 2 はフィールド幅を指定します。%nd は表示する整数が n 桁未満の場合、上位の桁には空白文字が埋められます。
リスト : 整数の和、二乗の和、三乗の和 (yacp02.c)
#include <stdio.h>
// 1 から n までの合計値を求める
double sum_of_int_1(double n)
{
return n * (n + 1) / 2;
}
double sum_of_square_1(double n)
{
return n * (n + 1) * (2 * n + 1) / 6;
}
double sum_of_cube_1(double n)
{
return n * n * (n + 1) * (n + 1) / 4;
}
// n から m までの合計値を求める
double sum_of_int(int n, int m)
{
return sum_of_int_1(m) - sum_of_int_1(n - 1);
}
double sum_of_square(int n, int m)
{
return sum_of_square_1(m) - sum_of_square_1(n - 1);
}
double sum_of_cube(int n, int m)
{
return sum_of_cube_1(m) - sum_of_cube_1(n - 1);
}
int main(void)
{
printf("%.0f\n", sum_of_int(1, 10000));
printf("%.0f\n", sum_of_int(100, 10000));
printf("%.0f\n", sum_of_square(1, 10000));
printf("%.0f\n", sum_of_square(100, 10000));
printf("%.0f\n", sum_of_cube(1, 10000));
printf("%.0f\n", sum_of_cube(100, 10000));
return 0;
}
$ clang yacp02.c $ ./a.out 50005000 50000050 333383335000 333383006650 2500500025000000 2500500000497500
1 から n までの合計値を関数 sum_of_xxx_1 で求めます。あとは sum_of_xxx_1(m) - sum_of_xxx_1(n - 1) を計算するだけです。sum_of_xxx の引数 n, m は int で、sum_of_xxx_1 の引数 n は double です。この場合、Ｃ言語は int を double に変換して、sum_of_xxx_1 に渡します。printf の書式 %.0f の .0 は精度の指定です。f 指定子の場合、精度は小数点以下の桁数を表します。.0 と指定することで、小数点以下を非表示にすることができます。
リスト : 累乗 (yacp03.c)
#include <stdio.h>
// 単純な繰り返し
double power(double x, int y)
{
double a = 1.0;
while (y-- > 0) a *= x;
return a;
}
// 再帰定義
double power_rec(double x, int y)
{
if (y == 0) return 1;
double z = power_rec(x, y / 2);
if (y % 2 == 0)
return z * z;
else
return x * z * z;
}
int main(void)
{
printf("%f\n", power(2, 16));
printf("%f\n", power(2, 32));
printf("%f\n", power(2, 64));
printf("%f\n", power_rec(2, 16));
printf("%f\n", power_rec(2, 32));
printf("%f\n", power_rec(2, 64));
return 0;
}
$ clang yacp03.c $ ./a.out 65536.000000 4294967296.000000 18446744073709551616.000000 65536.000000 4294967296.000000 18446744073709551616.000000
累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。
pow (x, y) = x ** y x ** 3 = x * x * x; x ** 4 = x * x * x * x; x ** 5 = x * x * x * x * x; 図 : 累乗の計算
これをそのままプログラムしたものが関数 power です。プログラムは簡単なので説明は割愛します。この場合、n 回の乗算が必要になります。ところが、式を変形するともっと少ない回数で求めることができます。
x ** 4 = (x ** 2) ** 2 -> 2 回
x ** 8 = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回
一般化すると
x ** y = (x ** (y / 2)) ** 2 （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）
図 : 累乗の高速化
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。x ** (y / 2) を計算する部分は、再帰を使えば簡単です。
この考え方でプログラムしたものが関数 power_rec です。局所変数 z を定義します。z の値は x ** (y / 2) です。これは power_rec を再帰呼び出しすれば簡単に求めることができます。あとは、y が偶数であれば z * z を返し、奇数であれば x * z * z を返します。このように、再帰呼び出しを使って累乗を効率的に計算することができます。
リスト : フィボナッチ関数 (yacp04.c)
#include <stdio.h>
// 二重再帰
int fibo(int n)
{
if (n == 0 || n == 1)
return n;
else
return fibo(n - 1) + fibo(n - 2);
}
// 末尾再帰
int fibo_sub(int n, int a, int b)
{
if (n == 0)
return a;
else
return fibo_sub(n - 1, a + b, a);
}
int fibo_rec(int n)
{
return fibo_sub(n, 0, 1);
}
// 繰り返し
int fiboi(int n)
{
int a = 0, b = 1;
while (n-- > 0) {
int c = a;
a += b;
b = c;
}
return a;
}
int main(void)
{
printf("%d\n", fibo(30));
printf("%d\n", fibo_rec(30));
printf("%d\n", fiboi(30));
return 0;
}
$ clang yacp04.c $ ./a.out 832040 832040 832040
フィボナッチ関数は再帰呼び出しを使えば簡単にプログラムできます。関数 fibo は自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。
fibo(5) ┬ fibo(4) ┬ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │ │ │
│ │ │ └ fibo(0)
│ │ └ fibo(1)
│ └ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
│
└ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
└ fibo(1)
図 : 関数 fibo のトレース
同じ値を何回も求めているため、関数 fibo の効率はとても悪いのです。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。累算変数を使って二重再帰を末尾再帰へ変換したものが関数 fibo_rec と fibo_sub です。
関数 fibo_sub の累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 a に、ひとつ先の値を変数 b に格納しておきます。あとは a と b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo_sub の呼び出しを下図に示します。
fibo_sub(5, 0, 1)
fibo_sub(4, 1, 1)
fibo_sub(3, 1, 2)
fibo_sub(2, 2, 3)
fibo_sub(1, 3, 5)
fibo_sub(0, 5, 8)
=> a の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : 関数 fibo_sub の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。
Ｃ言語の場合、規格では末尾再帰最適化をサポートしてませんが、末尾再帰を繰り返しに変換することは簡単です。関数 fibo を繰り返しに変換すると関数 fiboi のようになります。このように、末尾再帰は簡単に繰り返しに変換することができます。
リスト ; 整数の n 進数表示 (yacp05.c)
#include <stdio.h>
char table[] = "0123456789ABCDEF";
void print_int_sub(int n, int b)
{
if (n >= b) {
print_int_sub(n / b, b);
}
printf("%c", table[n % b]);
}
void print_int(int n, int b)
{
if (b > 1 || b <= 16)
if (n < 0) {
printf("-");
print_int_sub(-n, b);
} else
print_int_sub(n, b);
else
printf("基数は 2 以上 16 以下の数を指定してください");
printf("\n");
}
int main(void)
{
print_int(123456789, 2);
print_int(-123456789, 8);
print_int(123456789, 10);
print_int(-123456789, 16);
print_int(0xabcdef, 10);
print_int(0xabcdef, 16);
print_int(0x7fffffff, 10);
print_int(0x7fffffff, 16);
return 0;
}
$ clang yacp05.c $ ./a.out 111010110111100110100010101 -726746425 123456789 -75BCD15 11259375 ABCDEF 2147483647 7FFFFFFF
実際の印字処理は関数 print_int_sub で行います。上位の桁から表示するため再帰呼び出しを使っています。n < b が再帰呼び出しの停止条件です。n が b 以上であれば、n を b で割り算して print_int_sub を再帰呼び出しします。戻ってきたら、n % b の印字コードを文字列 table から求めて、それを printf で出力します。%c は文字を出力する指定子です。print_int は引数の条件をチェックして print_int_sub を呼び出すだけです。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Ｃ言語の整数 (int や long log int など) は多倍長整数ではないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗やフィボナッチ関数と同じように、再帰定義を使って簡単にプログラムできます。
リスト : 組み合わせの数を求める (yacp06.c)
#include <stdio.h>
int combination(int n, int r)
{
if (n == r || r == 0)
return 1;
else
return combination(n, r - 1) * (n - r + 1) / r;
}
long long combinationl(int n, int r)
{
if (n == r || r == 0)
return 1;
else
return combinationl(n, r - 1) * (n - r + 1) / r;
}
int main(void)
{
for (int i = 16; i <= 30; i += 2)
printf("(%d, %d) = %d\n", i, i / 2, combination(i, i / 2));
for (int i = 32; i <= 62; i += 2)
printf("(%d, %d) = %lld\n", i, i / 2, combinationl(i, i / 2));
return 0;
}
とても簡単ですね。ところで、Ｃ言語の int は 32 bit なので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
$ clang yacp06.c $ ./a.out (16, 8) = 12870 <-- combination (18, 9) = 48620 (20, 10) = 184756 (22, 11) = 705432 (24, 12) = 2704156 (26, 13) = 10400600 (28, 14) = 40116600 (30, 15) = -131213633 (32, 16) = 601080390 <-- combinationl (34, 17) = 2333606220 (36, 18) = 9075135300 (38, 19) = 35345263800 (40, 20) = 137846528820 (42, 21) = 538257874440 (44, 22) = 2104098963720 (46, 23) = 8233430727600 (48, 24) = 32247603683100 (50, 25) = 126410606437752 (52, 26) = 495918532948104 (54, 27) = 1946939425648112 (56, 28) = 7648690600760440 (58, 29) = 30067266499541040 (60, 30) = 118264581564861424 (62, 31) = -284401161134521734
Ｃ言語の場合、桁あふれが発生してもランタイムエラーは発生しません。int のかわりに long long int を使うと、もう少し大きな値でも計算することができます。関数 combinationl は long long int を使って計算するバージョンです。printf で long long int を表示する場合、%lld のように変換修飾子 ll を付けてください。
リスト ; 順列 (yacp07.c)
#include <stdio.h>
#include <stdbool.h>
#define N 16
int buffer[N];
bool used[N + 1];
void print_perm(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void perm_sub(int n, int m, int k)
{
if (k == m)
print_perm(m);
else {
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
buffer[k] = i;
used[i] = true;
perm_sub(n, m, k + 1);
used[i] = false;
}
}
}
void permutations(int n, int m)
{
if (n > 0 && n < N && m <= n) perm_sub(n, m, 0);
}
int main(void)
{
permutations(3, 3);
permutations(4, 2);
}
実際の処理は関数 perm_sub で行います。第 3 引数 k が選んだ数字の個数を表します。k と m が等しいときが再帰呼び出しの停止条件になります。print_perm で順列を表示します。選んだ数字 i を配列 buffer[k] に格納し、配列 used[i] に印をつけてから perm_sub を再帰呼び出しします。再帰呼び出しから戻ってきたら used を元に戻します。これで順列を表示することができます。
実際に実行すると次のように表示されます。
$ clang yacp07.c $ ./a.out 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
リスト : 重複順列 (yacp08.c)
#include <stdio.h>
#define N 16
int buffer[N];
void print_perm(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void perm_sub(int n, int m, int k)
{
if (k == m)
print_perm(k);
else {
for (int i = 1; i <= n; i++) {
buffer[k] = i;
perm_sub(n, m, k + 1);
}
}
}
void repeat_perm(int n, int m)
{
if (n > 0 && n < N && m <= n) perm_sub(n, m, 0);
}
int main(void)
{
repeat_perm(3, 3);
repeat_perm(4, 2);
}
重複順列は簡単です。数字は重複してもよいので、配列 used で数字をチェックする必要はありません。実行結果は次のようになります。
$ clang yacp08.c $ ./a.out 1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4
1 から 5 までの数字の中から 3 個を選ぶ組み合わせは次のようになります。
[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5],
最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個を選ぶと [1, 4, 5] を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は組み合わせの公式と同じです。
プログラムは次のようになります。
リスト : 組み合わせ (yacp09.c)
#include <stdio.h>
#define N 16
int buffer[N];
void print_combination(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void comb_sub(int n, int r, int m)
{
if (r == 0)
print_combination(m);
else if (n > 0) {
comb_sub(n - 1, r, m);
buffer[m] = n;
comb_sub(n - 1, r - 1, m + 1);
}
}
void combinations(int n, int r)
{
if (r > 0 && r <= N && r <= n) comb_sub(n, r, 0);
}
int main(void)
{
combinations(5, 3);
combinations(6, 4);
}
実際の処理は関数 comb_sub で行います。comb_sub は、1 から n までの数字の中から r 個を選ぶ組み合わせを生成します。引数 m は選んだ数字の個数を表します。選んだ要素は配列 buffer に格納します。r が 0 になったら組み合わせを一つ生成できたので、print_combinaion で組み合わせを表示します。
あとは n が 0 より大きければ comb_sub を再帰呼び出しするだけです。最初の呼び出しは数字 n を選ばない場合です。残りの数字の中から r 個の数字を選びます。最後の呼び出しが数字 n を選択する場合です。数字 n を buffer に追加して、残りの数字の中から r - 1 個を選びます。
実際に実行すると次のように表示されます。
$ clang yacp09.c $ ./a.out 3 2 1 4 2 1 4 3 1 4 3 2 5 2 1 5 3 1 5 3 2 5 4 1 5 4 2 5 4 3 4 3 2 1 5 3 2 1 5 4 2 1 5 4 3 1 5 4 3 2 6 3 2 1 6 4 2 1 6 4 3 1 6 4 3 2 6 5 2 1 6 5 3 1 6 5 3 2 6 5 4 1 6 5 4 2 6 5 4 3
要素の順番が逆になっていますが、正常に動作しています。
リスト : 重複組み合わせ (yacp10.c)
#include <stdio.h>
#define N 16
int buffer[N];
void print_combination(int n)
{
for (int i = 0; i < n; i++)
printf("%d ", buffer[i]);
printf("\n");
}
void comb_sub(int n, int r, int m)
{
if (r == 0)
print_combination(m);
else if (n > 0) {
comb_sub(n - 1, r, m);
buffer[m] = n;
comb_sub(n, r - 1, m + 1);
}
}
void repeat_comb(int n, int r)
{
if (r > 0 && r <= N && r <= n) comb_sub(n, r, 0);
}
int main(void)
{
repeat_comb(3, 2);
repeat_comb(4, 3);
}
重複組み合わせを求める repeat_comb も簡単です。実際の処理は関数 comb_sub で行います。最後の else if 節では、n を選んだあとそれを取り除かないで r - 1 個の要素を選びます。実行結果は次のようになります。
$ clang yacp10.c $ ./a.out 1 1 2 1 2 2 3 1 3 2 3 3 1 1 1 2 1 1 2 2 1 2 2 2 3 1 1 3 2 1 3 2 2 3 3 1 3 3 2 3 3 3 4 1 1 4 2 1 4 2 2 4 3 1 4 3 2 4 3 3 4 4 1 4 4 2 4 4 3 4 4 4