如何确定循环中的语句将使用条件语句执行多少次

Question

有一个由12个问题组成的测试.每个问题的值必须大于4分.所有问题必须加到100.所有问题都必须有一个整数值.所以可能的组合可能是5,5,5,5,5,5,5,5,5,5,5,45

有一种理论上会给出这个结果的方法:

// 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;
}

请注意,我为小于46的值创建了每个循环,因为如果所有问题的值必须大于4,那么问题就不可能达到50分.

编辑

对不起的人我觉得我不是在清楚地解释自己.我随机猜测了12个问题.这个例子可能已经有100个问题的测试.我需要的东西就像dlev在评论中提到的那样.我也知道我可以在循环中放置中断以使该方法更有效.如果总和大于100,那么为什么继续循环只是从相应的循环中退出

Answer 1

此代码将评估if语句22,563,490,300,366,186,081时间。所以不用说，这是行不通的......

但通过一些改变，它会的。我并不是说暴力是解决这个问题的方法，但它确实有效。

首先，为了使表达式更简单一点，观察一下，如果每个问题都必须有非负的分数，并且分数必须加起来为 ，那么他也会遇到同样的问题40。

现在，第一个循环变成了for (q12 = 0; q12 <= 40; q12++)。

在第二个循环中，我们不必测试 和 之间的所有内容，q11因为不能大于。040q11 + q1240

所以，第二个循环就变成了for (q11 = 0; q11 + q12 <= 40; q11++)。

等等...

最后，最后一个for循环是完全不必要的，因为 仅有一个可能的值q1。

所以，改变

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++;

不快。不优雅。但它有效。

虽然这比最初的实现要快得多，但即使1,000,000每秒找到“好的”组合，仍然需要大约 13 个小时......

让我们将问题改为“每个问题必须至少值 1 分，并且所有分数的总和必须为 52”。这相当于最初的问题。

我们有52积分可以分配。每个星号代表一个点：

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

为此，我们可以使用分隔符分隔这些点。十一个分隔符将为我们提供12星号组。

例子：****|*****|****|********|*|***|**|****|****|*********|***|*****

每个分隔符必须位于两个相邻的星号之间。有51那些空间。

11由于分隔符不存在差异，因此该解决方案也是“可以以多少种不同的、与顺序无关的方式将项目分配在点上”这一问题的解决方案51。

给定元素11集中的 组合数量为我们提供。5151! / ( 40! * 11! )47,626,016,970

这一切都假设“顺序很重要”，即问题 1 值得 10 分，问题 2 值得 20 分，反之亦然，这是不同的。

对于q每个问题的得分超过考试p分数和总分的问题，公式为：t

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