1

「ネストされた」ループを解決するアプローチは何ですか?

元 -

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

count = 2002..?? を与える (14C5)

私は 10 * (10 + 9) * (10 + 9 + 8) ........ *(10+9+8+7+6) を考えましたが、これは間違っています。あと、15C5も考えました。しかし、それは正しくもありません。

答えは.. 最初のループでは 10/1 です
2 番目のループでは 10*11/(2*1)
3 番目のループでは 10*11*12 / (3*2*1) です等々..

インタビュアーは常にそのような質問を修正するので、親切に私を修正し、そのような質問を解決するための正しいアプローチを提供してください..

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) を持つのと同じで、イテレータ用に 3 つのスロットを選択[1-9]し、残りを. たとえば、可能な選択肢の 1 つは{0, 5, 7}、これらのスロットのそれぞれに 1 つのイテレータを配置し、次に 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おそらく、彼らは、途中で見た小さな算術ショートカットを使用して、手動でそれを理解することを望んでいたのでしょうか? 手動計算を高速化する最も明白な方法は、コードの再帰的な性質を利用することです。count1 つのループ、2 つのループ、3 つのループなどを繰り返し計算し、部分和を使用して次のステップを実行できます。つまり、次のことを意味します。

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
    ...

したがって、3 つのループのケースでは、2 つのループのケースの部分和を使用して合計をより速く計算できることに注意してください (常に 10 個の部分和があります)。それを 15 分以内に書き出すことは想像できますが、かなり大変です。おそらく、他の誰かが賢い洞察力で声を上げてくれるでしょう...

于 2013-08-11T10:43:53.463 に答える
0

頭の中で適切にトレースできる範囲を超えたプログラミング ロジックが提示された場合は、コンパイラを使用します。

for以下は、すべてのループを実行し、各反復中にすべての変数の値を出力する、コード スニペットに基づく最小限の C プログラムです。

/* 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 に答える