ファイルの文字数 (ファイルサイズ) と行数をカウントするプログラムを作ってください。コマンドラインでファイル名が省略された場合は標準入力を使うものとします。なお、Unix 系 OS には同等の機能を持つコマンド wc があります。
prog [input_file]
ファイルから文字列を探索し、見つけたらその行を出力するプログラムを作ってください。コマンドラインでファイル名が省略された場合は標準入力を使うものとします。なお、Unix 系 OS には正規表現を使って文字列を検索するコマンド grep があります。
prog key [input_file]
ファイルを読み込んで、ある特定の文字を他の文字で置換するプログラムを作ってください。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。
コマンドラインの第 1 引数が置換対象となる文字、第 2 引数が置き換える文字とします。これらの引数は文字列で指定することができ、たとえば prog abc ABC とすると、a -> A, b -> B, c -> C と置換します。引数の長さが異なる場合はエラー終了するものとします。なお、Unix 系 OS にはもっと多くの機能を持つコマンド tr があります。
prog char_set1 char_set2 [input_file [output_file]]
ファイルを読み込んで、第 1 引数で指定した文字列を、第 2 引数で指定した文字列に置換するプログラムを作ってください。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。なお、Unix 系 OS ではコマンド sed で文字列の置換を行うことができます。もちろん、正規表現も利用することができます。
prog key_str replace_str [input_file [output_file]]
ファイルの単語をカウントするプログラムを作ってください。単語は空白文字で区切られた文字列とします。コマンドラインでファイル名が省略された場合は標準入力を使うものとします。なお、Unix 系 OS には同等の機能を持つコマンド wc があります。
prog [input_file]
タブを空白文字に展開するプログラムを作ってください。タブの値は 8 個とします。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。なお、Unix 系 OS には同等の機能を持つコマンド expand があります。
prog [input_file [output_file]]
空白文字をタブに置き換えるプログラムを作ってください。タブの値は 8 個とします。コマンドラインでファイル名が省略された場合は標準入出力を使うものとします。なお、Unix 系 OS には同等の機能を持つコマンド unexpand があります。
prog [input_file [output_file]]
自然数 n (long long int) を素因数分解する関数 factorization を定義してください。返り値は vector<Pair> で、Pair(p, q) は pq を表します。
リスト : Pair の定義 typedef tuple<long long, long long> Pair;
factorization(24) => (2, 3) (3, 1) factorization(12345678) => (2, 1) (3, 2) (47, 1) (14593, 1) factorization(123456789) => (3, 2) (3607, 1) (3803, 1) factorization(1234567890) => (2, 1) (3, 2) (5, 1) (3607, 1) (3803, 1) factorization(1111111111) => (11, 1) (41, 1) (271, 1) (9091, 1)
自然数 n の約数の個数を求める関数 divisor_num を定義してください。
divisor_num(24) => 8 divisor_num(12345678) => 24 divisor_num(123456789) => 12 divisor_num(1234567890) => 48 divisor_num(1111111111) => 16
自然数 n の約数の合計値を求める関数 divisor_sum を定義してください。
divisor_sum(24) => 60 divisor_sum(12345678) => 27319968 divisor_sum(123456789) => 178422816 divisor_sum(1234567890) => 3211610688 divisor_sum(1111111111) => 1246404096
自然数 n の約数を vector に格納して返す関数 divisor を定義してください。
divisor(24) => 1 2 3 4 6 8 12 24 divisor(12345678) => 1 2 3 6 9 18 47 94 141 282 423 846 14593 29186 43779 87558 131337 262674 685871 1371742 2057613 4115226 6172839 12345678 divisor(123456789) => 1 3 9 3607 3803 10821 11409 32463 34227 13717421 41152263 123456789 divisor(1234567890) => 1 2 3 5 6 9 10 15 18 30 45 90 3607 3803 7214 7606 10821 11409 18035 19015 21642 22818 32463 34227 36070 38030 54105 57045 64926 68454 108210 114090 162315 171135 324630 342270 13717421 27434842 41152263 68587105 82304526 123456789 137174210 205761315 246913578 411522630 617283945 1234567890 divisor(1111111111) => 1 11 41 271 451 2981 9091 11111 100001 122221 372731 2463661 4100041 27100271 101010101 1111111111
完全数 - Wikipedia によると、『完全数 (かんぜんすう，perfect number) とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。』 とのことです。自然数 n 以下の完全数を求める関数 perfect_number を定義してください。
perfect_number(10000) => (画面に出力) 6 28 496 8128
友愛数 - Wikipedia によると、『友愛数（ゆうあいすう）とは、異なる2つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。』 とのことです。自然数 n 以下の友愛数を求める関数 yuuai_number を定義してください。
yuuaiNumber(100000) => (画面に出力) 220 284 1184 1210 2620 2924 5020 5564 6232 6368 10744 10856 12285 14595 17296 18416 63020 76084 66928 66992 67095 71145 69615 87633 79750 88730
m 個の整数 1, 2, ..., m の順列を考えます。このとき、i 番目 (先頭要素が 1 番目) の要素が整数 i ではない順列を「完全順列」といいます。簡単な例を示しましょう。
1 - 3 の完全順列 2 3 1 3 1 2
1 - 4 の完全順列 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1
1 から m までの整数値で完全順列を生成するプログラムを作ってください。
完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
モンモール数を求める関数 montmort_number を定義してください。
montmort_number(1) => 0 montmort_number(2) => 1 montmort_number(3) => 2 montmort_number(4) => 9 montmort_number(5) => 44 montmort_number(6) => 265 montmort_number(7) => 1854 montmort_number(10) => 1334961 montmort_number(20) => 895014631192902121
バランスの取れた n 対のカッコ列を画面に表示する関数 kakko を定義してください。カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。
kakko(3) => (画面に表示) ((())) (()()) (())() ()(()) ()()() kakko(4) => (画面に表示) (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
バランスの取れた n 対のカッコ列の総数を求める関数 kakko_num を定義してください。
kakko_num(1) => 1 kakko_num(2) => 2 kakko_num(3) => 5 kakko_num(4) => 14 kakko_num(5) => 42 kakko_num(6) => 132 kakko_num(7) => 429 kakko_num(8) => 1430 kakko_num(9) => 4862 kakko_num(10) => 16796 kakko_num(30) => 3814986502092304
リスト : ファイルの文字数と行数
#include <iostream>
#include <fstream>
using namespace std;
void read_file(istream& fin)
{
int line = 0;
int size = 0;
int c;
while ((c = fin.get()) != EOF) {
if (c == '\n') line++;
size++;
}
cout << "line : " << line << ", size = " << size << endl;
}
int main(int argc, char* argv[])
{
if (argc < 2) {
read_file(cin);
} else {
ifstream fin(argv[1]);
if (fin) {
read_file(fin);
} else {
cerr << argv[1] << " が見つかりません" << endl;
return 1;
}
}
}
行数と文字数は関数 read_file でカウントします。行数を変数 line, 文字数を変数 size でカウントします。どちらの変数も 0 で初期化します。あとは、get で 1 バイトずつ読み込み、それが改行文字ならば line を +1 して、size を +1 します。最後に、size と line を演算子 << で表示するだけです。
リスト : 文字列の探索
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
void search_key(const char* key, istream& fin)
{
string buff;
while (getline(fin, buff)) {
if (buff.find(key, 0) != string::npos) {
cout << buff << endl;
}
}
}
int main(int argc, char* argv[])
{
if (argc < 2) {
cerr << "引数が足りません\n";
return 1;
}
if (argc == 2) {
search_key(argv[1], cin);
} else {
ifstream fin(argv[2]);
if (fin) {
search_key(argv[1], fin);
} else {
cerr << argv[2] << " が見つかりません\n" << endl;
}
}
}
文字列の検索は関数 search_key で行います。search_key は getline で fin から 1 行ずつバッファ buff に読み込み、メンバ関数 find で buff から key を探します。見つかった場合は演算子 << で buff を出力します。
リスト : 文字の置換
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int position(const char* buff, int c)
{
for (int i = 0; buff[i] != '\0'; i++)
if (buff[i] == c) return i;
return -1;
}
void replace_char(const char* src, const char* dst, istream& fin, ostream& fout)
{
int c;
while ((c = fin.get()) != EOF) {
int n = position(src, c);
if (n >= 0) {
fout.put(dst[n]);
} else {
fout.put(c);
}
}
}
int main(int argc, char* argv[])
{
if (argc < 3) {
cerr << "引数が足りません" << endl;
return 1;
}
if (strlen(argv[1]) != strlen(argv[2])) {
cerr << "引数 (文字列) の長さが異なります" << endl;
return 1;
}
if (argc == 3) {
replace_char(argv[1], argv[2], cin, cout);
} else if (argc >= 4) {
ifstream fin(argv[3]);
if (!fin) {
cerr << argv[3] << " が見つかりません" << endl;
return 1;
}
if (argc == 4) {
replace_char(argv[1], argv[2], fin, cout);
} else {
ofstream fout(argv[4]);
if (!fout) {
cerr << argv[4] << " をライトオープンできません" << endl;
return 1;
}
replace_char(argv[1], argv[2], fin, fout);
}
}
}
最初に引数をチェックして、argv[1] と argv[2] の長さが異なればエラー終了します。実際の処理は関数 replace_char で行います。fin から get で 1 バイト読み込み、それが文字列 src にあるか関数 position で検索します。position は単純な線形探索です。見つかった場合は dst[n] を put で出力し、そうでなければ文字 c を put で出力します。
リスト : 文字列の置換
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
void replace_string(const char* s, const char* d, istream& fin, ostream& fout)
{
string buff;
int k = strlen(s);
while (getline(fin, buff)) {
int n = 0;
while (true) {
n = buff.find(s, n);
if (n == string::npos) break;
buff.replace(n, k, d);
n += k;
}
fout << buff << endl;
}
}
int main(int argc, char* argv[])
{
if (argc < 3) {
cerr << "引数が足りません" << endl;
return 1;
}
if (argc == 3) {
replace_string(argv[1], argv[2], cin, cout);
} else if (argc >= 4) {
ifstream fin(argv[3]);
if (!fin) {
cerr << argv[3] << " が見つかりません" << endl;
return 1;
}
if (argc == 5) {
ofstream fout(argv[4]);
if (!fout) {
cerr << argv[4] << " をライトオープンできません" << endl;
return 1;
}
replace_string(argv[1], argv[2], fin, fout);
} else {
replace_string(argv[1], argv[2], fin, cout);
}
}
}
文字列の置換は関数 replace_string で行います。replace_string は getline で fin から 1 行ずつバッファ buff に読み込みます。変数 k は文字列 key の長さをセットします。一致する文字列をすべて置換するため、find の返り値が npos になるまで while ループで処理を繰り返します。変数 n が検索開始位置を表します。最初は buff の先頭 (0) に初期化します。
n が npos でなければ、key が見つかりました。メンバ関数 replace で、n 番目から k 個の文字を引数の文字列 d に置き換えます。そして、検索開始位置 n を n + k に更新します。key が見つからない場合は buff を fout に出力して、次の行を読み込みます。これをファイルの終端に到達するまで繰り返します。
リスト : 単語のカウント
#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;
void wc1(istream& fin)
{
bool inword = false;
int c, n = 0;
while ((c = fin.get()) != EOF) {
if (isspace(c))
inword = false;
else {
if (!inword) {
inword = true;
n++;
}
}
}
cout << n << endl;
}
void wc(istream& fin)
{
int count = 0;
string buff;
while (fin >> buff) count++;
cout << count << endl;
}
int main(int argc, char *argv[])
{
if (argc >= 2) {
ifstream fin(argv[1]);
if (!fin) {
cerr << argv[1] << " が見つかりません" << endl;
return 1;
}
wc1(fin);
} else {
wc1(cin);
}
}
単語のカウントは関数 wc で行います。入力演算子 >> は空白文字を読み飛ばすので、fin >> buff で単語を読み込むことができます。あとは、ファイルの終端に到達するまで単語を読み込んで count を +1 するだけです。
関数 wc1 は別解で、入力演算子を使わずに 1 文字ずつ入力する場合です。単語を読んでいるときは、変数 inword を true にし、空白文字が現れたら inword を false にします。そして、inword を false から true に変更するとき、単語の個数 n をインクリメントします。空白文字のチェックはライブラリ (cctype) の関数 isspace で簡単に行うことができます。
int isspace(int c);
isspace は文字 c が空白文字であれば真を返します。ASCII コードの場合、isspace が真を返す空白文字には次の種類があります。
' ' : 空白 (0x20) '\t' : 水平タブ (0x09) '\n' : 改行 (0x0a) '\v' : 垂直タブ (0x0b) '\f' : 書式送り (0x0c) '\r' : 復帰 (0x0d)
リスト : タブの展開
#include <iostream>
#include <fstream>
using namespace std;
void detab(istream& fin, ostream& fout)
{
int col = 0;
int c;
while ((c = fin.get()) != EOF) {
if (c == '\t') {
do {
fout.put(' ');
col++;
} while (col % 8 != 0);
} else {
if (c == '\n')
col = 0;
else
col++;
fout.put(c);
}
}
}
int main(int argc, char *argv[])
{
if (argc < 2) {
detab(cin, cout);
} else if (argc >= 2) {
ifstream fin(argv[1]);
if (!fin) {
cerr << argv[1] << " が見つかりません";
return 1;
}
if (argc >= 3) {
ofstream fout(argv[2]);
if (!fout) {
cerr << argv[2] << " をライトオープンできません" << endl;
return 1;
}
detab(fin, fout);
} else {
detab(fin, cout);
}
}
}
実際の処理は関数 detab で行います。変数 col が欄の位置を表します。get で読み込んだ文字 c がタブ (\t) の場合、col % 8 が 0 になるまで put で空白文字を出力します。これでタブを空白に展開することができます。c が改行文字ならば col を 0 にリセットします。そうでなければ、col をインクリメントして、文字 c を put で出力します。
リスト : 空白をタブに置換
#include <iostream>
#include <fstream>
using namespace std;
void entab(istream& fin, ostream& fout)
{
int col = 0;
int c;
while ((c = fin.get()) != EOF) {
int sc = 0;
// 空白を集める
if (c == ' ') {
do {
sc++;
col++;
if (col % 8 == 0) {
fout.put('\t');
sc = 0;
}
} while ((c = fin.get()) == ' ');
if (sc > 0) while (sc-- > 0) fout.put(' ');
}
if (c == '\n') {
col = 0;
} else {
col++;
}
fout.put(c);
}
}
int main(int argc, char *argv[])
{
if (argc < 2) {
entab(cin, cout);
} else if (argc >= 2) {
ifstream fin(argv[1]);
if (!fin) {
cerr << argv[1] << " が見つかりません";
return 1;
}
if (argc >= 3) {
ofstream fout(argv[2]);
if (!fout) {
cerr << argv[2] << " をライトオープンできません" << endl;
return 1;
}
entab(fin, fout);
} else {
entab(fin, cout);
}
}
}
実際の処理は関数 entab で行います。変数 col が欄の位置を表します。get で文字を読み込み、文字 c が空白であれば、連続している空白の個数を変数 sc に求めます。このとき、col % 8 が 0 になったならば、連続している空白をタブに置換することができます。put でタブを出力して、sc の値を 0 にリセットします。
do - while ループが終了して、sc が 0 よりも大きい場合、その空白はタブに置換することができません。put で空白を sc 個だけ出力します。文字 c が空白文字でなければ、文字 c が改行文字かチェックします。そうであれば、col を 0 にリセットします。あとは、文字 c をそのまま put で出力するだけです。
リスト : 素因数分解
typedef tuple<long long, long long> Pair;
Pair factor_sub(long long n, long long m)
{
long long i = 0;
while (n % m == 0) {
i++;
n /= m;
}
return make_tuple(i, n);
}
vector<Pair> factorization(long long n)
{
vector<Pair> a;
long long c, m;
tie(c, m) = factor_sub(n, 2);
if (c > 0) a.push_back(make_tuple(2, c));
for (long long i = 3; m >= i * i; i += 2) {
tie(c, m) = factor_sub(m, i);
if (c > 0) a.push_back(make_tuple(i, c));
}
if (m > 1) a.push_back(make_tuple(m, 1));
return a;
}
素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。関数 factor_sub は n を m で割り算します。このとき、m で割り切れる回数を求めます。factor_sub は m で割った回数と商を Pair に格納して返します。
次に、factor_sub を呼び出して n を 2 で割り算します。それから、for ループで奇数列を生成します。変数 i は 3 で初期化します。変数 a は結果を格納する vector です。√m < i になったら for ループを終了します。そうでなければ、factor_sub を呼び出して m を i で割り算します。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、n がその値で割り切れることはありません。
n の素因数分解ができると、約数の個数を求めるのは簡単です。n = pa * qb * rc とすると、約数の個数は (a + 1) * (b + 1) * (c + 1) になります。たとえば、12 は 22 * 31 になるので、約数の個数は 3 * 2 = 6 になります。実際、12 の約数は 1, 2, 3, 4, 6, 12 の 6 個です。
プログラムは次のようになります。
リスト : 約数の個数
long long divisor_num(long long n)
{
long long a = 1;
for (auto& x : factorization(n)) {
a *= get<1>(x) + 1;
}
return a;
}
divisor_num は範囲 for 文で vector の要素を順番に取り出し、get<1>(x) + 1 を a に掛け算していくだけです。
n の素因数分解ができると、約数の合計値を求めるのは簡単です。n の素因数分解が pa だった場合、その約数の合計値は次の式で求めることができます。
σ(p, a) = pa + pa-1 + ... + p2 + p + 1
たとえば、8 の素因数分解は 23 になり、素数の合計値は 8 + 4 + 2 + 1 = 15 になります。
pa の約数の合計値を σ(p, a) で表すことにします。n = pa * qb * rc の場合、n の約数の合計値は σ(p, a) * σ(q, b) * σ(r, c) になります。たとえば、12 は 22 * 3 に素因数分解できますが、その合計値は (4 + 2 + 1) * (3 + 1) = 28 となります。12 の約数は 1, 2, 3, 4, 6, 12 なので、その合計値は確かに 28 になります。
プログラムは次のようになります。
リスト : 約数の合計値
// 累乗の計算
long long pow(long long x, long long y)
{
if (y == 0)
return 1;
else if (y == 0)
return x;
else {
long long z = pow(x, y / 2);
return y % 2 == 0 ? z * z : z * z * x;
}
}
// σ(p, n) の計算
long long div_sum_sub(long long p, long long n)
{
long long a = 0;
for (; n > 0; n--) a += pow(p, n);
return a + 1;
}
// 約数の和
long long divisor_sum(long long n)
{
long long a = 1;
for (auto& x : factorization(n))
a *= div_sum_sub(get<0>(x), get<1>(x));
return a;
}
関数 div_sum_sub は σ(p, n) を計算します。あとは for ループで div_sum_sub の返り値を累積変数 a に掛け算していくだけです。
p が素数の場合、pa の約数は次のように簡単に求めることができます。
pa, pa-1, ... p2, p, 1
n の素因数分解が pa * qb だったとすると、その約数は次のようになります。
(pa, pa-1, ... p2, p, 1) * qb,
(pa, pa-1, ... p2, p, 1) * qb-1,
.....
(pa, pa-1, ... p2, p, 1) * q2,
(pa, pa-1, ... p2, p, 1) * q,
(pa, pa-1, ... p2, p, 1) * 1
たとえば、12 の約数は 24 = (1, 2, 4) と 3 = (1, 3) から、(1, 2, 4) * 1 と (1, 2, 4) * 3 のすべての要素 (1, 2, 4, 3, 6, 12) になります。
プログラムは次のようになります。
リスト : 約数をすべて求める
// p ^ q の約数を求める
vector<long long> divisor_sub(long long p, long long q)
{
vector<long long> a;
for (long long i = 0; i <= q; i++)
a.push_back(pow(p, i));
return a;
}
// 互いの要素を掛け算する
vector<long long> product(const vector<long long>& xs,
const vector<long long>& ys)
{
vector<long long> a;
for (auto x : xs) {
for (auto y : ys) {
a.push_back(x * y);
}
}
return a;
}
// n の約数を求める
vector<long long> divisor(long long n)
{
auto xs = factorization(n);
auto ys = divisor_sub(get<0>(xs[0]), get<1>(xs[0]));
for (int i = 1; i < xs.size(); i++)
ys = product(divisor_sub(get<0>(xs[i]), get<1>(xs[i])), ys);
sort(ys.begin(), ys.end());
return ys;
}
関数 divisor_sub は pn の約数を vector に格納して返します。関数 product は 2 つの vector (xs、ys) の要素を掛け合わせたものを vector に格納して返します。あとは for ループで素因数分解した結果を順番に取り出し、pq を divisor_sub で vector に変換して、それを product で累積変数 ys のスライスと掛け合わせていくだけです。
リスト : 完全数
void perfect_number(int n)
{
for (int x = 2; x <= n; x++) {
if (divisor_sum(x) - x == x)
cout << x << endl;
}
}
完全数を求める perfect_number は簡単です。x の約数の合計値を divisor_sum で求め、その値から x を引いた値が x と等しければ完全数です。出力演算子 << で x を表示します。
リスト : 友愛数
void yuuai_number(int n)
{
for (int x = 2; x <= n; x++) {
long long m = divisor_sum(x) - x;
if (x < m && x == divisor_sum(m) - m)
cout << x << " " << m << endl;
}
}
友愛数を求める yuuai_number も簡単です。divisor_sum で x の約数の合計値を求め、その値から x を引いた値を変数 m にセットします。m の約数の合計値から m を引いた値が x と等しければ、x と m は友愛数です。出力演算子 <<で x と m を表示します。同じ組を表示しないようにするため、x < m を条件に入れています。
リスト : 完全順列
void derangement_sub(vector<int>& buff, int n = 0)
{
if (n == buff.size()) {
for (int x : buff) cout << x << " ";
cout << endl;
} else {
int temp = buff[n];
for (int i = n; i < buff.size(); i++) {
if (buff[i] == n + 1) continue;
buff[n] = buff[i];
buff[i] = temp;
derangement_sub(buff, n + 1);
buff[i] = buff[n];
buff[n] = temp;
}
}
}
void derangement(int m)
{
vector<int> buff(m);
iota(buff.begin(), buff.end(), 1);
derangement_sub(buff);
}
実際の処理は関数 derangement_sub で行います。基本的には 1 から m までの数字を m 個選ぶ順列を生成する処理と同じです。n 番目の数字を選ぶとき、数字 i が n + 1 と等しい場合は i を選択しません。n が m と等しい場合は m 個の数字を選んだので buff の内容を表示します。これで完全順列を生成することができます。
リスト : 完全順列の総数
long long montmort_number(int n)
{
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}
// 別解
long long montmort_number1(int n)
{
long long a = 0, b = 1;
for (int i = 1; i < n; i++) {
long long c = (i + 1) * (a + b);
a = b;
b = c;
}
return a;
}
関数 montmort_number は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。変数 a に i 番目の値を、b に i + 1 番目の値を保存しておきます。すると、i + 2 番目の値は (i + 1) * (a + b) で計算することができます。あとは、b の値を a に、新しい値を b にセットして処理を繰り返すだけです。
リスト : カッコ列の生成
void kakko_sub(int x, int y, int m, string s)
{
if (x == y && x == m) {
cout << s << endl;
} else {
if (x < m) {
kakko_sub(x + 1, y, m, s + "(");
}
if (y < x) {
kakko_sub(x, y + 1, m, s + ")");
}
}
}
void kakko(int m)
{
kakko_sub(0, 0, m, "");
}
カッコ列の生成は簡単です。関数 kakko_sub の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 s はカッコ列を表す文字列です。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x == y && y == m の場合、カッコ列がひとつ完成しました。文字列 s を出力演算子 << で表示します。そうでなければ、kakko_sub を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
プログラムは配列を使うと簡単です。次の図を見てください。
0 : [1, 1, 1, 1, 1] 1 : [1, 1, 1, 1, 1,] 2 : [1, 1, 1+1=2, 2+1=3, 3+1=4] => [1, 1, 2, 3, 4] 3 : [1, 1, 2, 3+2=5, 5+4=9] => [1, 1, 2, 5, 9] 4 : [1, 1, 2, 5, 5+9=14] => [1, 1, 2, 5, 14]
上図は Ｃn (n = 4) を求める場合です。大きさが n + 1, 要素の値が 1 の一次元配列を用意します。n = 0, 1 の場合は n 番目の要素をそのまま返します。n が 2 よりも大きい場合、変数 i を 2 に初期化して、i - 1 番目以降の要素の累積和を求めます。
たとえば i = 2 の場合、2 番目の要素は 1 番目の要素と自分自身を加算した値 2 になります。3 番目の要素は 2 番目の要素と自分自身を足した値 3 になり、4 番目の要素は 3 + 1 = 4 になります。次に i を +1 して同じことを繰り返します。3 番目の要素は 2 + 3 = 5 になり、4 番目の要素は 5 + 4 = 9 になります。i = 4 のとき、4 番目の要素は 5 + 9 = 14 となり、Ｃ4 の値を求めることができました。
プログラムは次のようになります。
リスト : カッコ列の総数
long long kakko_num(int n)
{
vector<long long> table(n + 1, 1);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j++) {
table[j] += table[j - 1];
}
}
return table[n];
}
説明したことをそのままプログラムしただけなので、とくに難しいところはないと思います。
//
// yacp6.cpp : Yet Another C++ Problems (6)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// Q51
typedef tuple<long long, long long> Pair;
Pair factor_sub(long long n, long long m)
{
long long i = 0;
while (n % m == 0) {
i++;
n /= m;
}
return make_tuple(i, n);
}
vector<Pair> factorization(long long n)
{
vector<Pair> a;
long long c, m;
tie(c, m) = factor_sub(n, 2);
if (c > 0) a.push_back(make_tuple(2, c));
for (long long i = 3; m >= i * i; i += 2) {
tie(c, m) = factor_sub(m, i);
if (c > 0) a.push_back(make_tuple(i, c));
}
if (m > 1) a.push_back(make_tuple(m, 1));
return a;
}
void print_factor(const vector<Pair>& v)
{
for (auto& x : v) {
cout << "(" << get<0>(x) << "," << get<1>(x) << ")";
}
cout << endl;
}
// Q52
long long divisor_num(long long n)
{
long long a = 1;
for (auto& x : factorization(n)) {
a *= get<1>(x) + 1;
}
return a;
}
// Q53
long long pow(long long x, long long y)
{
if (y == 0)
return 1;
else if (y == 0)
return x;
else {
long long z = pow(x, y / 2);
return y % 2 == 0 ? z * z : z * z * x;
}
}
// σ(p, n) の計算
long long div_sum_sub(long long p, long long n)
{
long long a = 0;
for (; n > 0; n--) a += pow(p, n);
return a + 1;
}
// 約数の和
long long divisor_sum(long long n)
{
long long a = 1;
for (auto& x : factorization(n))
a *= div_sum_sub(get<0>(x), get<1>(x));
return a;
}
// Q54
// p ^ q の約数を求める
vector<long long> divisor_sub(long long p, long long q)
{
vector<long long> a;
for (long long i = 0; i <= q; i++)
a.push_back(pow(p, i));
return a;
}
// 互いの要素を掛け算する
vector<long long> product(const vector<long long>& xs,
const vector<long long>& ys)
{
vector<long long> a;
for (auto x : xs) {
for (auto y : ys) {
a.push_back(x * y);
}
}
return a;
}
//
vector<long long> divisor(long long n)
{
auto xs = factorization(n);
auto ys = divisor_sub(get<0>(xs[0]), get<1>(xs[0]));
for (int i = 1; i < xs.size(); i++)
ys = product(divisor_sub(get<0>(xs[i]), get<1>(xs[i])), ys);
sort(ys.begin(), ys.end());
return ys;
}
template<class T>
void print_vector(const vector<T>& v)
{
for (auto& x : v) cout << x << " ";
cout << endl;
}
// Q55
void perfect_number(int n)
{
for (int x = 2; x <= n; x++) {
if (divisor_sum(x) - x == x)
cout << x << endl;
}
}
// Q56
void yuuai_number(int n)
{
for (int x = 2; x <= n; x++) {
long long m = divisor_sum(x) - x;
if (x < m && x == divisor_sum(m) - m)
cout << x << " " << m << endl;
}
}
// Q57
void derangement_sub(vector<int>& buff, int n = 0)
{
if (n == buff.size()) {
for (int x : buff) cout << x << " ";
cout << endl;
} else {
int temp = buff[n];
for (int i = n; i < buff.size(); i++) {
if (buff[i] == n + 1) continue;
buff[n] = buff[i];
buff[i] = temp;
derangement_sub(buff, n + 1);
buff[i] = buff[n];
buff[n] = temp;
}
}
}
void derangement(int m)
{
vector<int> buff(m);
iota(buff.begin(), buff.end(), 1);
derangement_sub(buff);
}
// Q58
long long montmort_number(int n)
{
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}
// 別解
long long montmort_number1(int n)
{
long long a = 0, b = 1;
for (int i = 1; i < n; i++) {
long long c = (i + 1) * (a + b);
a = b;
b = c;
}
return a;
}
// Q59
void kakko_sub(int x, int y, int m, string s)
{
if (x == y && x == m) {
cout << s << endl;
} else {
if (x < m) {
kakko_sub(x + 1, y, m, s + "(");
}
if (y < x) {
kakko_sub(x, y + 1, m, s + ")");
}
}
}
void kakko(int m)
{
kakko_sub(0, 0, m, "");
}
// Q60
long long kakko_num(int n)
{
vector<long long> table(n + 1, 1);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j++) {
table[j] += table[j - 1];
}
}
return table[n];
}
// 簡単なテスト
int main()
{
// Q51
print_factor(factorization(24));
print_factor(factorization(12345678));
print_factor(factorization(123456789));
print_factor(factorization(1234567890));
print_factor(factorization(1111111111));
// Q52
cout << divisor_num(24) << endl;
cout << divisor_num(12345678) << endl;
cout << divisor_num(123456789) << endl;
cout << divisor_num(1234567890) << endl;
cout << divisor_num(1111111111) << endl;
// Q53
cout << divisor_sum(24) << endl;
cout << divisor_sum(12345678) << endl;
cout << divisor_sum(123456789) << endl;
cout << divisor_sum(1234567890) << endl;
cout << divisor_sum(1111111111) << endl;
// Q54
print_vector(divisor(24));
print_vector(divisor(12345678));
print_vector(divisor(123456789));
print_vector(divisor(1234567890));
print_vector(divisor(1111111111));
// Q55
perfect_number(10000);
// Q56
yuuai_number(100000);
// Q57
derangement(3);
derangement(4);
derangement(5);
// Q58
for (int i = 1; i <= 10; i++) {
cout << montmort_number(i) << endl;
cout << montmort_number1(i) << endl;
}
cout << montmort_number(20) << endl;
cout << montmort_number(20) << endl;
// Q59
kakko(3);
kakko(4);
// Q60
for (int i = 1; i <= 10; i++)
cout << kakko_num(i) << endl;
cout << kakko_num(30) << endl;
}