C++でforや再帰関数を使わずに、総当りする方法はありますか？

質問

C++等で、forを使わず、再帰関数を使わずに多量のループで総当りする方法はありますでしょうか？
自己末尾再帰関数というのがネットで出てきますが、C言語系では使えないみたいです。
再帰関数で変数を全てスタティックにしても、関数の多重呼び出しで容量を食ってプログラムが動かないほどの計算をこなす必要があるのですが、こういった多数の桁のやり方になれておらず、先が見えません…
また、全部をforにするのも、桁が大きすぎて問題があります。
どなたかご教授くださいますと幸いです。

回答No.3

Werner · ベストアンサー

コンパイラに期待できないなら自分で末尾最適化してみるとか。

多重のループはこんな感じに書き直せると思う。
//---------------------------------------------------------
#include<stdio.h>
int main(){
　int i[8]; //ループカウンタ
　int cnt[8] = { //ループ回数
　　4,3,2,1,2,4,1,3,
　};
　int depth = 0; //現在のループの深さ
　int depth_max = 7; //ループの深さ最大

　int j;

　i[0] = 0;
　while(i[0] < cnt[0]){
　　while(depth < depth_max){ //一番内側のループでない場合
　　　depth++; //1つ内側のループへ
　　　i[depth] = 0; //ループカウンタ初期値設定
　　}

　　//一番内側でやりたいこと
　　for(j=0;j<=depth_max;j++) printf("%d,",i[j]);
　　printf("\n");

　　//一番内側のループカウンタ+1
　　i[depth]++;

　　while(!(i[depth] < cnt[depth])){ //深さdepthのループ継続条件を満たさない場合
　　　depth--; //1つ外側のループへ
　　　i[depth]++; //外側のループカウンタ+1
　　}
　}

　return 0;
}

お礼

ご解答ありがとうございます。
書き直しの方法を詳しくお教えくださってありがとうございます。
C++でもできるのですね。自分ではどうしても解法がわからずしまいでしたので助かりました。
参考にさせていただきたく思います。

回答No.5

titokani

う～ん、別に２０重でも３０重でも多重にループを回せばいいんじゃないかと思いますけど。いったいなにが問題なのかわからないです。

回答No.4

Interest

普通に総当たりを考えると、素直に考えれば
N個のデータが配列 data[N]に入っているとして、

for(i=0; i<N; i++){
　for(j=i+1; j<N; j++){
　　　やりたい処理( data[i], data[j] );
　}
}

となると思います。
これでスタックが積み上がるとは思えないのですが、これでは何が問題なのですか？
また、
(a) 具体的にどのようなデータを相手にしているのか
(b) 多数の桁とは具体的に何桁なのか
も補足してください。

お礼

ご解答ありがとうございます。
あまり詳しく説明できず申し訳ございません…。
forで1～9までの数値を、20以上の多重ループで回します。
再帰で渡す値は、現在の潜り位置で、ポインターです。
スタックが積みあがってしまうのは、多重に関数を呼び出しているため、関数の分のメモリを食っているのだと思います。（内部のデータは全てstaticですので、純粋に己の関数の容量が摘みあがっているのだと考えます）

回答No.2

salsberry

> 自己末尾再帰関数というのがネットで出てきますが、C言語系では使えないみたいです。

決して使えないわけではなく、賢いコンパイラなら末尾再帰をコンパイル時にループに変換できる場合があります。もちろん、そのような最適化が本質的にできない再帰呼び出しもあります。

> こういった多数の桁のやり方になれておらず、先が見えません…
> また、全部をforにするのも、桁が大きすぎて問題があります。

その「多数の桁」というのがどんなものなのか、forループだとどんな問題があるのかを示したほうがアドバイスを得やすいと思います。

お礼

ご解答ありがとうございます。
あまり詳しく書くことができず申し訳ございません…。
1～9までの数値でループするものを、20以上の桁数の総当りとなります。
forループだと、20以上の多重ループになってしまうため、プログラムが煩雑になってしまいます。
そういった問題で、なるべくループを抑えたコーディングをしたいということになります。

回答No.1

chie65536（@chie65535）

＞また、全部をforにするのも、桁が大きすぎて問題があります。

「３２桁分の０～９の数字をforループ」を素直に書くと以下のような、入れ子が３２重になったforループになります。
int i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15;
int i16,i17,i18,i19,i20,i21,i22,i23,i24,i25,i26,i27,i28,i29,i30,i31;
for(i31 = 0;i31 < 10;i31++) {
　for(i30 = 0;i30 < 10;i30++) {
　　for(i29 = 0;i29 < 10;i29++) {
　　　for(i28 = 0;i28 < 10;i28++) {
　　　　for(i27 = 0;i27 < 10;i27++) {
　　　　　for(i26 = 0;i26 < 10;i26++) {
　　　　　　（以下略）

しかし、以下のようにすれば「４重」で済みます。

int ii0,ii1,ii2,ii3;
int i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15;
int i16,i17,i18,i19,i20,i21,i22,i23,i24,i25,i26,i27,i28,i29,i30,i31;

for(ii0 = 0;ii0 < 100000000;ii0++) {
　i31 = ii0 / 10000000;
　i30 = (ii0 / 1000000) % 10;
　i29 = (ii0 / 100000) % 10;
　i28 = (ii0 / 10000) % 10;
　i27 = (ii0 / 1000) % 10;
　i26 = (ii0 / 100) % 10;
　i25 = (ii0 / 10) % 10;
　i24 = ii0 % 10;
　for(ii1 = 0;ii1 < 100000000;ii1++) {
　　i23 = ii1 / 10000000;
　　i22 = (ii1 / 1000000) % 10;
　　i21 = (ii1 / 100000) % 10;
　　i20 = (ii1 / 10000) % 10;
　　i19 = (ii1 / 1000) % 10;
　　i18 = (ii1 / 100) % 10;
　　i17 = (ii1 / 10) % 10;
　　i16 = ii1 % 10;
　　for(ii2 = 0;ii2 < 100000000;ii2++) {
　　　i15 = ii2 / 10000000;
　　　i14 = (ii2 / 1000000) % 10;
　　　i13 = (ii2 / 100000) % 10;
　　　i12 = (ii2 / 10000) % 10;
　　　i11 = (ii2 / 1000) % 10;
　　　i10 = (ii2 / 100) % 10;
　　　i9 = (ii2 / 10) % 10;
　　　i8 = ii2 % 10;
　　　for(ii3 = 0;ii3 < 100000000;ii3++) {
　　　　i7 = ii3 / 10000000;
　　　　i6 = (ii3 / 1000000) % 10;
　　　　i5 = (ii3 / 100000) % 10;
　　　　i4 = (ii3 / 10000) % 10;
　　　　i3 = (ii3 / 1000) % 10;
　　　　i2 = (ii3 / 100) % 10;
　　　　i1 = (ii3 / 10) % 10;
　　　　i0 = ii3 % 10;
　　　　//ループの中身
　　　}
　　}
　}
}

お礼

ご解答ありがとうございます。
とても複雑な組み方なのですね…！
しかし判定式を工夫するだけで、ループは単純に減らせるのですね。
じっくり考えて試したいと思います。