小町算のプログラム

1 2 3 4 5 6 7 8 9の配列の空白の部分に四則演算子を入れて500を作るプログラムを書きたいのですが私は空白の部分に四則演算子を入れた全てのパターンを作り500になるかどうか比較しようと考えますがどうすれば全てのパターンを作れるかわかりません。
再起関数が使えるのは分かるのですが.....。出力と計算は他の関数で行おうと考えています。
出来ればc++でのご回答お願いします。

No.1 回答者： Ogre7077 回答日時： 2017/01/10 14:27

"1 2 3 4 5 6 7 8 9" の空白部分とは、

四則演算子と空白で 5 種類の記号が、
連続して 8 個並ぶ配列なので、
これは 5 進数 8 桁の整数と見做せます。

ならば目的の全てのパターンを作るならば、
再帰を使わずとも以下の手順で求まります。

5 進数 8 桁の数を、
最小値 (00000000){5進数} から
最大値 (44444444){5進数} まで、
1 づつ加算しながら繰り返し出力。

以下 C++ のサンプルです。

string ops[] = { "+", "-", "*", "/", "" };
int num5x8[] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // 5 進数 8 桁の数の最小値 (00000000){5進数}
int flag = true;
while (flag) { // 最大値 (44444444){5進数} 以下なら繰り返し
_ 5進数8桁の数から小町算を出力する処理(num5x8, ops);
_ flag = 5進数8桁の数に1を加算し最大値以下ならtrueを返す処理(num5x8);
}

5 進数 8 桁の数に 1 を加算する実装については、加算器とかカンターなどのキーワードが参考になるでしょう。

No.2 回答者： Tacosan 回答日時： 2017/01/10 15:47

単純に 8重ループを組めばいいだけ, なんだけどね.