How to determine how many times will a statement inside a loop will be executed with conditional statements_问答_开发者

There is a test that consists of 12 questions. each question must have a value greater than 4 points. all the question must add to 100. also all the questions must have an integer value. so a possible combination may be 5,5,5,5,5,5,5,5,5,5,5,45

there is a method that theoretically will give this result:

// this method will return the possible number of tests
public static double PosibleNumberOfTests()
{
    int q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12; // each question value

    double counter=0; // if there is a valid combination then counter will be increased by 1

    for (q12 = 5; q12 < 46; q12++)
    {
        for (q11 = 5; q11 < 46; q11++)
        {
            for (q10 = 5; q10 < 46; q10++)
            {
                for (q9 = 5; q9 < 46; q9++)
                {
                    for (q8 = 5; q8 < 46; q8++)
                    {
                        for (q7 = 5; q7 < 46; q7++)
                        {
                            for (q6 = 5; q6 < 46; q6++)
                            {
                                for (q5 = 5; q5 < 46; q5++)
                                {
                                    for (q4 = 5; q4 < 46; q4++)
                                    {
                                        for (q3 = 5; q3 < 46; q3++)
                                        {
                                            for (q2 = 5; q2 < 46; q2++)
                                            {
                                                for (q1 = 5; q1 < 46; q1++)
                                                {
                                                    if (q1 + q2 + q3 + q4 + q5 + q6 + q7 + q8 + q9 + q10 + q11 + q12 == 100)
                                                        counter++;  // here is what we need. How many times will this line be executed!
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

    }
    return counter;
}

note that I created each loop for values less than 46 because if all questions must have a value greater than 4 it will be impossible for a question to be worth 50 points for example.

Edit

Sorry people I think I am not explaining my self clearly. I piked 12 questions as a random guess. This example may have been with a test 开发者_JS百科with 100 questions. I need something like what dlev mentioned in his comment. I also know I can place breaks in the loops to make the method more efficient. if the sum is greater than 100 then why continue looping just brak out of the corresponding loop

This code will evaluate the if statement 22,563,490,300,366,186,081 times. So needless to say, that ain't gonna work...

But with a few changes, it will. I'm not suggesting that brute force would be the way to go to solve this problem, but it does work.

First, to make the expressions a little simpler, observe that he have the same problem if every question must have a non-negative amount of points and the points have to add up to 40.

Now, the first loop becomes for (q12 = 0; q12 <= 40; q12++).

In the second loop, we don't have to test all q11 between 0 and 40, since q11 + q12 can't be greater than 40.

So, the second loop becomes for (q11 = 0; q11 + q12 <= 40; q11++).

And so on...

Finally, the last for loop is completely unnecessary since there's only one possible value for q1.

So, change

for (q1 = 5; q1 < 46; q1++)
    if (q1 + q2 + q3 + q4 + q5 + q6 + q7 + q8 + q9 + q10 + q11 + q12 == 100)
        counter++;

if (q2 + q3 + q4 + q5 + q6 + q7 + q8 + q9 + q10 + q11 + q12 <= 40)
    counter++;

Not quick. Not elegant. But it works.

While this is much faster than the initial implementation, even if finding 1,000,000 "good" combinations per second, it will still take about 13 hours...

Let's change to problem to "each question must be worth at least 1 point and the sum of all points has to be 52". This is equivalent to the initial question.

We have 52 points to distribute. Each asterisk represents a point:

****************************************************

To do this, we may separate those points using delimiters. Eleven delimiters will give us 12 groups of asterisks.

Example: ****|*****|****|********|*|***|**|****|****|*********|***|*****

Each delimiter must be between two adjacent asterisks. There are 51 of those spaces.

Since the delimiters present no differences, the solution is also the solution of the question "in how many different, order-independent ways can 11 items be allocated in 51 spots.

The number of 11-combinations from a given set of 51 elements is 51! / ( 40! * 11! ) which gives us 47,626,016,970.

This all is assuming that "order matters", i. e., it's different if question 1 is worth 10 points and question 2 is worth 20 points or viceversa.

For q questions, each worth more than p points and a total of t points on the test, the formula would be:

(t - p * q - 1)! / ( (t - (p + 1) * q)! * (q - 1)! )

Whenever you encounter a counting question, it's always a good idea to subtract constants first. In this case, the minimum value for each question is 5, so subtract that from each value and from the total. This gives you a maximum total of 40 with a minimum of 0 for each question. Then at the end, when you present the actual solution, you can add the constants again.

Now look at this question: Distribution of balls into 'bins with given capacities' using Dynamic Programming.

Your problem is the same, except that it's a little bit simpler. It's the same because your questions correspond to the bins and the values correspond to the balls.

Yours is simpler because in your case, the capacity of the questions is not limiting. In the accepted answer to the above question, min(n, c[k]) is always equal to n.