Yet Another C++ Problems は M.Hiroi がＣ++の勉強で作成した簡単なプログラムをまとめたものです。拙作のページ Yet Another Clang 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
下記に示すデータの度数分布表と累積度数表を求めるプログラムを作ってください。階級はデータの範囲を表します。この表では x cm 以上 y cm 未満を x - y で表しています。度数はその階級に出現したデータの個数です。度数を示してある表のことを「度数分布表」といいます。累積度数はその階級までの度数を全部加えたものです。累積度数を示してある表を「累積度数分布表」といいます。
リスト : 身長のデータ
const int N = 100;
double height[N] = {
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3
};
階級 度数 累積度数 ------------------------ 130 - 135 1 1 135 - 140 6 7 140 - 145 12 19 145 - 150 25 44 150 - 155 32 76 155 - 160 17 93 160 - 165 6 99 165 - 170 1 100
問題２のデータで、平均値と標準偏差を求めるプログラムを作ってください。データを \(x_1, x_2, \ldots , x_N\) とすると、総計量 \(T\) と平均値 \(M\) は次式で求めることができます。
平均値が同じ場合でも、データの特徴が異なる場合があります。たとえば、A = {4, 4, 5, 5, 5, 6, 6, 6, 7, 7} と B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} の平均値は 5.5 になります。A のデータは平均値の近くに集まっていてますが、B のデータはバラバラになっていますね。統計学では、ばらつきの大きさを表すために「分散 (variance)」という値を使います。分散の定義を次に示します。
分散の定義からわかるように、平均値から離れたデータが多いほど、分散の値は大きくなります。逆に、平均値に近いデータが多くなると分散は小さな値になります。そして、分散の平方根が「標準偏差 (SD : standard deviation)」になります。
x の y 乗を求める関数 power を再帰定義を使ってプログラムしてください。ここでは、x を double, y を int とします。
double power(double x, int y);
下図に示すフィボナッチ関数 fibo を定義してください。
int fibo(int n);
n 個の中から r 個を選ぶ組み合わせの数 nＣ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);
リスト : 九九表
void ninety_nine()
{
cout << " | 1 2 3 4 5 6 7 8 9\n";
cout << "---+---------------------------\n";
for (int i = 1; i <= 9; i++) {
cout << setw(2) << i << " | ";
for (int j = 1; j <= 9; j++)
cout << setw(2) << i * j << " ";
cout << endl;
}
}
九九表は二重の for ループで簡単に作ることができます。setw(2) は出力するデータのフィールド幅を指定するマニピュレータです。ヘッダ <iomanip> をインクルードしてください。setw(n) は表示するデータが n 桁未満の場合、上位の桁には空白文字が埋められます。
リスト : 度数分布表と累積度数表
const int N = 100;
const int M = 8;
// 身長
double height[N] = {
・・・省略・・・
};
// 表の作成
void make_freq()
{
int freq[M] = {0}; // 度数分布表
int cum[M]; // 累積度数表
double low = 130.0;
double z = 5.0;
// 度数分布表の作成
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (height[i] < low + z * (j + 1)) {
freq[j]++;
break;
}
}
}
// 累積度数表の作成
cum[0] = freq[0];
for (int i = 1; i < M; i++)
cum[i] = cum[i - 1] + freq[i];
// 表示
for (int i = 0; i < M; i++) {
cout << low + z * i << " - " << low + z * (i + 1) << " | ";
cout << setw(3) << freq[i] << " ";
cout << setw(3) << cum[i] << endl;
}
}
関数 make_freq の配列 freq が度数分布表、cum が累積度数表、変数 low が階級の下限値、z が階級の幅を表します。freq は 0 で初期化します。
度数分布表の作成は簡単です。最初の for ループで height の要素を取り出します。次の for ループで階級を求めます。変数 j が階級を表し、その上限値は low + z * (j + 1) で求めることができます。height[i] がこの値よりも小さい場合、その要素は階級 j であることがわかります。freq[j] の値をインクリメントして、for ループを脱出します。
累積度数表の作成も簡単です。cum[0] を freq[0] で初期化します。あとは、度数分布表の値 freq[i] と累積度数表の値 cum[i - 1] を足し算していくだけです。最後に、for ループで 2 つの表を出力します。
実行結果は次のようになります。
130.0 - 135.0 | 1 1 135.0 - 140.0 | 6 7 140.0 - 145.0 | 12 19 145.0 - 150.0 | 25 44 150.0 - 155.0 | 32 76 155.0 - 160.0 | 17 93 160.0 - 165.0 | 6 99 165.0 - 170.0 | 1 100
平均値と標準偏差を求めるプログラムは簡単です。次のリストを見てください。
リスト : 平均値と標準偏差
// 合計値を求める
double sum(double buff[], int size)
{
double a = 0.0;
for (int i = 0; i < size; i++) a += buff[i];
return a;
}
// 平均値と標準偏差
void meansd(double buff[], int size)
{
double m = sum(buff, size) / size;
double s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i];
s += (x - m) * (x - m);
}
cout << "mean = " << m << ", sd = " << sqrt(s / size) << endl;
}
void meansd2(double buff[], int size)
{
double m = 0.0, s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i] - m;
m += x / (i + 1);
s += (i * x * x) / (i + 1);
}
cout << "mean = " << m << ", sd = " << sqrt(s / size) << endl;
}
プログラムは簡単なので、説明は不要でしょう。参考文献『Ｃ言語による最新アルゴリズム事典』によると、データを 1 回通読するだけで平均値と標準偏差 (分散) を求めることができるそうです。これを参考にプログラムしたものが関数 meansd2 です。
meansd(height, N) => mean = 150.627, sd = 6.43347 meansd2(height, N) => mean = 150.627, sd = 6.43347
平均値は 150.627 cm で、標準偏差は 6.43347 になりました。
累乗は 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; 図 : 累乗の計算
式を変形するともっと少ない回数で求めることができます。
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) を計算する部分は、再帰を使えば簡単です。
リスト : 累乗
double power(double x, int y)
{
if (y == 0) return 1;
double z = power(x, y / 2);
if (y % 2 == 0)
return z * z;
else
return x * z * z;
}
局所変数 z を定義します。z の値は x ** (y / 2) です。これは power_rec を再帰呼び出しすれば簡単に求めることができます。あとは、y が偶数であれば z * z を返し、奇数であれば x * z * z を返します。このように、再帰呼び出しを使って累乗を効率的に計算することができます。
リスト : フィボナッチ関数
// 二重再帰
int fibo(int n)
{
if (n == 0 || n == 1)
return n;
else
return fibo(n - 1) + fibo(n - 2);
}
// 末尾再帰
int fibo_rec(int n, int a = 0, int b = 1)
{
return n == 0 ? a : fibo_rec(n - 1, b, a + b);
}
// 繰り返し
int fiboi(int n)
{
int a = 0, b = 1;
while (n-- > 0) {
int c = a;
a += b;
b = c;
}
return a;
}
フィボナッチ関数は再帰呼び出しを使えば簡単にプログラムできます。関数 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_rec の累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 a に、ひとつ先の値を変数 b に格納しておきます。あとは a と b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo_rec の呼び出しを下図に示します。
fibo_rec(5, 0, 1)
fibo_rec(4, 1, 1)
fibo_rec(3, 1, 2)
fibo_rec(2, 2, 3)
fibo_rec(1, 3, 5)
fibo_rec(0, 5, 8)
=> a の値 5 を返す
=> 5
=> 5
=> 5
=> 5
=> 5
図 : 関数 fibo_rec の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。
Ｃ/Ｃ++の場合、規格では末尾再帰最適化をサポートしてませんが、末尾再帰を繰り返しに変換することは簡単です。関数 fibo を繰り返しに変換すると関数 fiboi のようになります。このように、末尾再帰は簡単に繰り返しに変換することができます。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Ｃ/Ｃ++の整数 (int や long log int など) は多倍長整数ではないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗やフィボナッチ関数と同じように、再帰定義を使って簡単にプログラムできます。
リスト : 組み合わせの数を求める
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 は 32 bit なので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
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 を使って計算するバージョンです。
リスト : 順列
const int N1 = 16;
int buffer[N1];
bool used[N1 + 1];
// buffer の表示
void print_buffer(int n)
{
for (int i = 0; i < n; i++)
cout << buffer[i] << " ";
cout << endl;
}
void perm_sub(int n, int m)
{
if (n == m)
print_buffer(n);
else {
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
buffer[m] = i;
used[i] = true;
perm_sub(n, m + 1);
used[i] = false;
}
}
}
void permutations(int n)
{
if (n > 0 && n < N1) perm_sub(n, 0);
}
実際の処理は関数 perm_sub で行います。第 2 引数 m が選んだ数字の個数を表します。n と m が等しいときが再帰呼び出しの停止条件になります。print_buffer で順列を表示します。選んだ数字 i を配列 buffer[m] に格納し、配列 used[i] に印をつけてから perm_sub を再帰呼び出しします。再帰呼び出しから戻ってきたら used を元に戻します。これで順列を表示することができます。
実際に実行すると次のように表示されます。
permutations(4) => 画面に表示 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 permutations(5) => 画面に表示 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 ・・・省略・・・ 5 4 2 3 1 5 4 3 1 2 5 4 3 2 1
リスト : 重複順列
void repeat_perm_sub(int n, int m)
{
if (n == m)
print_buffer(n);
else {
for (int i = 1; i <= n; i++) {
buffer[m] = i;
repeat_perm_sub(n, m + 1);
}
}
}
void repeat_perm(int n)
{
if (n > 0 && n < N1) repeat_perm_sub(n, 0);
}
重複順列は簡単です。数字は重複してもよいので、配列 used で数字をチェックする必要はありません。実行結果は次のようになります。
repeat_perm(3) => 画面に表示 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 repeat_perm(4) => 画面に表示 1 1 1 1 1 1 1 2 1 1 1 3 ・・・省略・・・ 4 4 4 2 4 4 4 3 4 4 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 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は組み合わせの公式と同じです。
プログラムは次のようになります。
リスト : 組み合わせ
void comb_sub(int n, int r, int m)
{
if (r == 0)
print_buffer(m);
else if (n == r) {
for (int i = r; i > 0; i--)
buffer[m++] = i;
print_buffer(m);
} else {
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 <= N1) comb_sub(n, r, 0);
}
実際の処理は関数 comb_sub で行います。comb_sub は、1 から n までの数字の中から r 個を選ぶ組み合わせを生成します。引数 m は選んだ数字の個数を表します。選んだ要素は配列 buffer に格納します。r が 0 になったら組み合わせを一つ生成できたので、print_buffer で組み合わせを表示します。n が r と等しくなったならば、残りの数字 (1 から r まで) を全て選択します。for ループで 1 から r までの数字を buffer に追加してから print_buffer を呼び出します。
この 2 つの条件が再帰呼び出しの停止条件になります。あとは comb_sub を再帰呼び出しするだけです。最初の呼び出しは数字 n を選ばない場合です。残りの数字の中から r 個の数字を選びます。最後の呼び出しが数字 n を選択する場合です。数字 n を buffer に追加して、残りの数字の中から r - 1 個を選びます。
実際に実行すると次のように表示されます。
combinations(5, 3) => 画面に表示 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 combinations(6, 4) => 画面に表示 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
要素の順番が逆になっていますが、正常に動作しています。
リスト : 重複組み合わせ
void repeat_comb_sub(int n, int r, int m)
{
if (r == 0)
print_buffer(m);
else if (n == 1) {
for (int i = r; i > 0; i--)
buffer[m++] = 1;
print_buffer(m);
} else {
repeat_comb_sub(n - 1, r, m);
buffer[m] = n;
repeat_comb_sub(n, r - 1, m + 1);
}
}
void repeat_comb(int n, int r)
{
if (r > 0 && r <= N1) repeat_comb_sub(n, r, 0);
}
重複組み合わせを求める repeat_comb も簡単です。実際の処理は関数 repeat_comb_sub で行います。2 番目の else if 節で、n が 1 の場合は 1 を r 個選びます。最後の else 節では、n を選んだあとそれを取り除かないで r - 1 個の要素を選びます。実行結果は次のようになります。
repeat_comb(3, 2) => 画面に表示 1 1 2 1 2 2 3 1 3 2 3 3 repeat_comb(4, 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
//
// yacp1.cpp : Yet Another C++ Problems (1)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
// Q01
void ninety_nine()
{
cout << " | 1 2 3 4 5 6 7 8 9\n";
cout << "---+---------------------------\n";
for (int i = 1; i <= 9; i++) {
cout << setw(2) << i << " | ";
for (int j = 1; j <= 9; j++)
cout << setw(2) << i * j << " ";
cout << endl;
}
}
// Q02
const int N = 100;
const int M = 8;
// 身長
double height[N] = {
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3
};
void make_freq()
{
int freq[M] = {0}; // 度数分布表
int cum[M]; // 累積度数表
double low = 130.0;
double z = 5.0;
// 度数分布表の作成
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (height[i] < low + z * (j + 1)) {
freq[j]++;
break;
}
}
}
// 累積度数表の作成
cum[0] = freq[0];
for (int i = 1; i < M; i++)
cum[i] = cum[i - 1] + freq[i];
// 表示
for (int i = 0; i < M; i++) {
cout << low + z * i << " - " << low + z * (i + 1) << " | ";
cout << setw(3) << freq[i] << " ";
cout << setw(3) << cum[i] << endl;
}
}
// Q03
// 合計値を求める
double sum(double buff[], int size)
{
double a = 0.0;
for (int i = 0; i < size; i++) a += buff[i];
return a;
}
// 平均値と標準偏差
void meansd(double buff[], int size)
{
double m = sum(buff, size) / size;
double s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i];
s += (x - m) * (x - m);
}
cout << "mean = " << m << ", sd = " << sqrt(s / size) << endl;
}
void meansd2(double buff[], int size)
{
double m = 0.0, s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i] - m;
m += x / (i + 1);
s += (i * x * x) / (i + 1);
}
cout << "mean = " << m << ", sd = " << sqrt(s / size) << endl;
}
// Q04
double power(double x, int y)
{
if (y == 0) return 1;
double z = power(x, y / 2);
if (y % 2 == 0)
return z * z;
else
return x * z * z;
}
// Q05
// 二重再帰
int fibo(int n)
{
if (n == 0 || n == 1)
return n;
else
return fibo(n - 1) + fibo(n - 2);
}
// 末尾再帰
int fibo_rec(int n, int a = 0, int b = 1)
{
return n == 0 ? a : fibo_rec(n - 1, b, a + b);
}
// 繰り返し
int fiboi(int n)
{
int a = 0, b = 1;
while (n-- > 0) {
int c = a;
a += b;
b = c;
}
return a;
}
// Q06
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;
}
// Q07
const int N1 = 16;
int buffer[N1];
bool used[N1 + 1];
// 順列の表示
void print_buffer(int n)
{
for (int i = 0; i < n; i++)
cout << buffer[i] << " ";
cout << endl;
}
void perm_sub(int n, int m)
{
if (n == m)
print_buffer(n);
else {
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
buffer[m] = i;
used[i] = true;
perm_sub(n, m + 1);
used[i] = false;
}
}
}
void permutations(int n)
{
if (n > 0 && n < N1) perm_sub(n, 0);
}
// Q08
void repeat_perm_sub(int n, int m)
{
if (n == m)
print_buffer(n);
else {
for (int i = 1; i <= n; i++) {
buffer[m] = i;
repeat_perm_sub(n, m + 1);
}
}
}
void repeat_perm(int n)
{
if (n > 0 && n < N1) repeat_perm_sub(n, 0);
}
// Q09
void comb_sub(int n, int r, int m)
{
if (r == 0)
print_buffer(m);
else if (n == r) {
for (int i = r; i > 0; i--)
buffer[m++] = i;
print_buffer(m);
} else {
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 <= N1) comb_sub(n, r, 0);
}
// Q10
void repeat_comb_sub(int n, int r, int m)
{
if (r == 0)
print_buffer(m);
else if (n == 1) {
for (int i = r; i > 0; i--)
buffer[m++] = 1;
print_buffer(m);
} else {
repeat_comb_sub(n - 1, r, m);
buffer[m] = n;
repeat_comb_sub(n, r - 1, m + 1);
}
}
void repeat_comb(int n, int r)
{
if (r > 0 && r <= N1) repeat_comb_sub(n, r, 0);
}
// 簡単なテスト
int main()
{
ninety_nine();
make_freq();
meansd(height, N);
meansd2(height, N);
cout << power(2, 16) << endl;
cout << power(2, 32) << endl;
cout << power(2, 64) << endl;
for (int i = 0; i <= 20; i++) {
cout << fibo(i) << endl;
cout << fibo_rec(i) << endl;
cout << fiboi(i) << endl;
}
for (int i = 16; i <= 30; i += 2)
cout << i << ", " << i / 2 << " = " << combination(i, i / 2) << endl;
for (int i = 32; i <= 62; i += 2)
cout << i << ", " << i / 2 << " = " << combinationl(i, i / 2) << endl;
permutations(3);
permutations(4);
repeat_perm(3);
repeat_perm(4);
combinations(5, 3);
combinations(6, 4);
repeat_comb(3, 2);
repeat_comb(4, 3);
}