1

What is the approach to solve "nested for" loops?

Ex -

for(i=0;i<10;i++)
for(j=i;j<10;j++)
for(k=j;k<10;k++)
for(l=k;l<10;l++)
for(m=l;m<10;m++)
   count++;

gives count = 2002..?? (14C5)

I thought of 10 * (10 + 9) * (10 + 9 + 8) ........ *(10+9+8+7+6) which is giving way wrong. Also, I thought of 15C5. But it is also incorrect.

The answer is coming as.. For first loop, it is 10/1
For second loop, it is 10*11/(2*1)
For third loop, its is 10*11*12 / (3*2*1) and so on..

Kindly correct me and provide me with the correct approach to solve such questions as the interviewers always modify such questions..

4

2 回答 2

1

这是一个关于为什么封闭形式的计数论点：

(10 + (number of loops - 1)) choose (number of loops)

考虑循环数为 3 的情况，因此我们有 3 个迭代器。现在在算法执行期间可视化迭代器的值。很难用严格的语言表达，但希望这会有所帮助：

0 | | | 1 2 3 4 5 6 7 8 9
0 | | 1 | 2 3 4 5 6 7 8 9
0 | | 1 2 | 3 4 5 6 7 8 9
...
0 | 1 | | 2 3 4 5 6 7 8 9
0 | 1 | 2 | 3 4 5 6 7 8 9
0 | 1 | 2 3 | 4 5 6 7 8 9
...
0 1 | | | 2 3 4 5 6 7 8 9
0 1 | | 2 | 3 4 5 6 7 8 9
...
0 1 2 3 4 5 6 7 8 9 | | |

它实际上与拥有 12 个插槽（最左边的插槽始终为 0）相同，我们为迭代器选择三个插槽，然后依次用[1-9]. 例如，{0, 5, 7}在这种情况下，一种可能的选择是在每个插槽中放置一个迭代器，然后依次放置数字 1-9：

Slots: 0 1 2 3 4 5 6 7 8 9 10 11
     0 | 1 2 3 4 | 5 6 | 7 8  9

不是我最大的计数论点，但我认为它可以传达这个想法。

现在你的实际问题是如何当场提出这个问题。在短时间内找到封闭形式似乎相当困难。也许他们只是想让你手动弄清楚count == 2002使用你在路上看到的任何小的算术快捷方式？使手动计算快速的最明显方法是利用代码的递归特性。您可以迭代计算count一个循环、两个循环、三个循环等，并使用部分和来执行下一步。我的意思是：

1 Loop:
    10
    Sum: 10
2 Loop:
    10 9 8 7 6 5 4 3 2 1
    Partial Sums: 1
    => 1 + 2 = 3
    => 1 + 2 + 3 = 6
    => 1 + 2 + 3 + 4 = 10
    ...
    => Sum: 55 
3 Loop:
    10 9 8 7 6 5 4 3 2 1
    9 8 7 6 5 4 3 2 1
    8 7 6 5 4 3 2 1
    7 6 5 4 3 2 1
    6 5 4 3 2 1
    5 4 3 2 1
    4 3 2 1
    3 2 1
    2 1
    1
    Partial Sums: 1
    => 1 + 3 = 4
    => 1 + 3 + 6 = 10
    => 1 + 3 + 6 + 10 = 20
    ...

所以请注意，在三个循环的情况下，我们可以使用两个循环的部分和来更快地计算总和（总是有十个部分和）。我可以想象在大约 15 分钟内把它写出来，虽然这会很痛苦。也许其他人会以聪明的洞察力插话……

于 2013-08-11T10:43:53.463 回答
0

当使用超出您可以在脑海中正确跟踪的编程逻辑提出时，请使用编译器。

以下是基于您的代码片段的最小 C 程序，它运行所有for循环并在每次迭代期间打印所有变量的值。

/* testloop.c */

#include <stdio.h>

int main()
{
        static int count, i, j, k, l, m;

        for(i=0;i<10;i++)
            for(j=i;j<10;j++)
                for(k=j;k<10;k++)
                    for(l=k;l<10;l++)
                        for(m=l;m<10;m++) {
                            printf("i= %d\tj= %d\tk= %d\tl= %d\tm= %d\tcount= %d\n", i, j, k, l, m, count);
                            count++;
                        }   

        printf("After all loops count = %d\n", count);

}

编译如下

$ gcc testloop.c -o testloop

并将其运行为

$ ./testloop

并观察输出以了解代码流。

0   0   0   0   0   count = 0
0   0   0   0   1   count = 1
0   0   0   0   2   count = 2
0   0   0   0   3   count = 3
0   0   0   0   4   count = 4
...
... (1985 more lines)
...
7   7   9   9   9   count = 1990
7   8   8   8   8   count = 1991
7   8   8   8   9   count = 1992
7   8   8   9   9   count = 1993
7   8   9   9   9   count = 1994
7   9   9   9   9   count = 1995
8   8   8   8   8   count = 1996
8   8   8   8   9   count = 1997
8   8   8   9   9   count = 1998
8   8   9   9   9   count = 1999
8   9   9   9   9   count = 2000
9   9   9   9   9   count = 2001
After all loops count = 2002
于 2013-08-11T10:44:14.917 回答