Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
420 views
in Technique[技术] by (71.8m points)

c++ - variable nested for loops

I'm trying to figure out how I can use recursion to do n-level nested for loops. For example, if n=3, there would be 3 'levels'

for(z=0;z<6;z++){
   for(y=0;y<6;y++){
      for(x=0;x<6;x++){
         if (z+y+x==f){
            //do something
         } 
      }
   }
}

and so on.

I can't seem to figure out how I would be able to place the if loop in the last for loop and how I can access the variables of previous for loops from the if statement. I know that the question of variable nested loops has been asked alot of times, and I have looked through all of them. But none seem to help me.

Could someone present an easy way of using recursion to achieve this, keeping in mind that I'm still a beginner in c++, to point me in the right direction?

The use case is as follows:

Write a program to input the number of dice m. The program will output the total number of possible cases, the number of possible cases for each possible n and the n with the highest probability. Note: only one input m is read in. n is computed by the program

Example if user enters m=2 then program should output

The total number of possible cases is 36.
The possibilities are
2 1
3 2
4 3
.
.
.
12 1

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I came across this earlier today and thought I might share the solution that I eventually came up with. I'm not sure what the policy is here regarding replying to old posts. I'm just going by the fact that I came across this question this morning, and this kind of thing would have been useful to me.

For efficiency, I've avoided recursion. Also, it doesn't use any specific c++ stuff - it will work fine on C as well.

We're trying to create N nested "for" loops. Instead of using

for(int i = 0; i<max; i++)
  for (int j = 0; j<max; j++)
    ...

I'll be replacing i, j, ... with an array: i[0], i[1], ..., i[n-1].

Here's my solution:

const int n = /*Insert N here: how many loops do you need?*/;
int i[n+1]; // if "n" is not known before hand, then this array will need to be created dynamically.
//Note: there is an extra element at the end of the array, in order to keep track of whether to exit the array.

for (int a=0; a<n+1; a++) {
  i[a]=0;
}

int MAX = 79; //That's just an example, if all of the loops are identical: e.g. "for(int i=0; i<79; i++)". If the value of MAX changes for each loop, then make MAX an array instead: (new) int MAX [n]; MAX[0]=10; MAX[1]=20;...;MAX[n-1]=whatever.

int p = 0; //Used to increment all of the indicies correctly, at the end of each loop.
while (i[n]==0) {//Remember, you're only using indicies i[0], ..., i[n-1]. The (n+1)th index, i[n], is just to check whether to the nested loop stuff has finished.

  //DO STUFF HERE. Pretend you're inside your nested for loops. The more usual i,j,k,... have been replaced here with i[0], i[1], ..., i[n-1].


  //Now, after you've done your stuff, we need to increment all of the indicies correctly.
  i[0]++;
  // p = 0;//Commented out, because it's replaced by a more efficient alternative below.
  while(i[p]==MAX) {//(or "MAX[p]" if each "for" loop is different. Note that from an English point of view, this is more like "if(i[p]==MAX". (Initially i[0]) If this is true, then i[p] is reset to 0, and i[p+1] is incremented.
    i[p]=0;
    i[++p]++; //increase p by 1, and increase the next (p+1)th index
    if(i[p]!=MAX)
      p=0;//Alternatively, "p=0" can be inserted above (currently commented-out). This one's more efficient though, since it only resets p when it actually needs to be reset!
  }
}

There, that's all. Hopefully the comments make it clear what it's meant to be doing. I think it should be pretty efficient - almost as much as real nested for-loops. Most of the overhead is a one-off at the beginning, so this should be more efficient that using recursive functions etc (please correct me if I'm wrong on this point).

Hope it's useful to somebody one day.

Peace and love.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...