1. 総当りプログラムの概要
N桁のM進数が取りうるすべての整数を出力します。
たとえば3桁の2進数なら、
{000, 001, 010, 011, 100, 101, 110, 111}
を出力します。
forループ1回で、1桁のM進数が取りうるすべての整数を出力できるので、
総当りプログラムをforループで書くと、実にN重ループのコードになってしまいます。
今回はそんな問題を、再帰構造にすることで綺麗にまとめてしまいましょう。
2. ソースコード
はじめにソースコードを提示します。
マクロの値を変えることで、パラメータを変更できます。
- MAX_IDX : N桁
- MAX_VAL : M進数
- INIT : M進数の初期値(基本は0)
recursive_brute_force.c
#include <stdio.h>
#define MAX_IDX 2
#define MAX_VAL 1
#define INIT 0
void print_a(int* a){
int i = 0;
for (i = 0; i < MAX_IDX+1; i++){
printf("%d ", a[i]);
}
printf("\n");
}
int check_init(int* a){
int i;
for (i = 0; i <= MAX_IDX; i++){
if (a[i] != INIT) return 0;
}
return 1;
}
int recursive_increment(int idx, int* a){
if (idx < MAX_IDX) {
while (1){
a[idx] += recursive_increment(idx + 1, a);
if (a[idx] > MAX_VAL){
a[idx] = INIT;
return 1;
}
if (check_init(a)) break;
}
return 0;
}
else {
print_a(a);
if (a[idx] == MAX_VAL){
a[idx] = INIT;
return 1;
}
else{
a[idx]++;
return 0;
}
}
return -1;
}
int main(void){
int a[MAX_IDX + 1];
int buf, i;
for (i = 0; i < MAX_IDX + 1; i++){
a[i] = INIT;
}
buf = recursive_increment(0, a);
return 0;
}
3. 解説
上記のソース（recursive_brute_force.c）の詳細を説明します。
3.1. アプローチ
まずは簡単な例として、3桁の2進数を考えましょう。
冒頭に示したとおり、この場合に取りうる値は
{000, 001, 010, 011, 100, 101, 110, 111}
となります。
この集合を総当りで表示するには、次のアルゴリズムが考えられます。
- 取りうる最も低い値（000）で初期化する。2に進む。
- 1桁目をインクリメントする。3に進む。
- 1桁目が最大値(1)を超えたら、4に進む。そうでない場合、2に進む。
- 1桁目を初期値(0)にし、2桁目をインクリメントする。2桁目が最大値を超えたら、5に進む。そうでない場合、2に進む。
- 1桁目と2桁目を初期値にし、3桁目をインクリメントする。3桁目が最大値を超えたら、終了する。そうでない場合、2に進む。
当たり前と言えば当たり前ですが、このアルゴリズムが基本になります。
上の例では3桁の2進数と状況を限定しているので、手計算でも、forループでも簡単に計算できますが、
一般化するとなると少々難しくなります。
3.2. 再帰的に一般化
3.1.で示したアルゴリズムを再帰的に一般化すると、下記のようになります。
- 取りうる最も低い値で初期化する。桁を表わす変数idxを0で初期化する(idx=0は最上位桁)。2に進む。
- idxが最下位桁を指していなければ、再帰する。idxをインクリメントし、再び2に進む。最下位桁なら、3に進む。
- 最下位桁の値が最大値なら、最下位桁を初期値にし、1を返す。それ以外なら、最下位桁をインクリメントし、0を返す。4に進む。
- 返り値をidx桁に足す。最大値を超えたら、idx桁を初期値にし、1を返して、再び4に進む。それ以外なら、5に進む。
- すべての桁が初期値なら、0を返して、4に進む。
スタック上の関数がmain関数のみとなったとき、このアルゴリズムは終了します。
再帰をするたびにidxがインクリメントしてより低い桁を指すようになり、
再帰から返るたびに桁がひとつずつ上がっていく、というイメージが理解できれば、掴みやすいです。