1

3桁の数字のすべての順列を再帰的に見つけることに取り組んでいます。

次の順列メソッドを構成するのにうんざりしています。

    static int a = 1;
    static int b = 2;
    static int c = 3;
    static int aCount;
    static int bCount;
    static int cCount;

    static void perm(int a, int b, int c)
    {

        Console.WriteLine("( {0}, {1}, {2} )", a, b, c); // (1,2,3 )

        if (aCount < 1 && bCount<1 &&cCount<1)
        {
            aCount++;

            perm(a, c, b);
        }
        else
            if (aCount==1 && bCount < 1 && cCount<1)
            {

                bCount++;
                perm(b, a, c);
            }
            else
                if (aCount == 1 && bCount == 1 && cCount < 1)
                 {
                    perm(b,c,a);
                  }
        else
                if (aCount==1 && bCount==1 && cCount < 1)
                {
                    cCount++;
                    perm(c, a, b);  //c b a

                }
               else
                    if (aCount == 1 && bCount == 1 &&  cCount == 1)
                {
                    perm(c, b, a);

                }

            }

各ステップの詳細とともに、すべてのケースをカバーしようとしましたが、それでも突然スタックオーバーフロー例外が発生します。

あなたの貢献に感謝します。

4

3 に答える 3

3

あなたは再帰を試みていると言っていますが、それらの行はすべてコードに表示されます:

perm(a, c, b)
perm(b, a, c)
perm(b, c, a)
perm(c, a, b)
perm(c, b, a)

そしてもちろん、関数の最初の呼び出し:perm(a, b, c)

それははるかに簡単です：

static void perm(int a, int b, int c)
{
    Console.WriteLine("( {0}, {1}, {2} )", a, b, c);
    Console.WriteLine("( {0}, {2}, {1} )", a, b, c);
    Console.WriteLine("( {1}, {0}, {2} )", a, b, c);
    Console.WriteLine("( {1}, {2}, {0} )", a, b, c);
    Console.WriteLine("( {2}, {0}, {1} )", a, b, c);
    Console.WriteLine("( {2}, {1}, {0} )", a, b, c);
}
于 2014-04-20T18:21:58.467 に答える
0

疑似コードを書きます：

permutationABC()
{
    int n=3;
    array SOL[n]/* 1 if you get the element  otherwise 0 if you don't get the element , the meaning of SOL is that SOL[0] is 1 if we had got 'a' , otherwise 0. It's the same for the others */
    initSolWithAllZero(SOL)
    permRecursive(abc,SOL,0,n);
}

permRecursive(SOL,i,n)
{
    if i == n then print(SOL) 
    else
    {
        for k=0 to n
        {
             if SOL[k] == 0 then
             {
                  SOL[k]=1 // take 
                  permRecursive(SOL,i+1,n)
                  SOL[K]=0 // don't take ... go back....
             }
        }
    }
}

時間は O(n*n!) です。 O(n!) は順列の数で、O(n) は印刷時間です。

于 2014-12-30T16:42:16.153 に答える
0

1 つには、次の 2 つのケースのいずれも、無限再帰につながります。

if (aCount == 1 && bCount == 1 && cCount < 1)
{
    perm(b,c,a);
}

と：

if (aCount == 1 && bCount == 1 && cCount == 1)
{
    perm(c, b, a);
}

この理由はaCount、 、bCountまたはcCountを変更しないため、同じケースを繰り返しトリガーすることになります。

それを超えて、問題を再帰的に考えているようには見えません-他の回答で述べたように、すべての順列は1回の呼び出しで表示されるため、そのように機能させると、再帰の深さは2になります.次に、基本的に、すべての再帰呼び出しをprintステートメントに置き換え、非再帰関数を含めることができます。

再帰的な解決策として、現在の呼び出しで単一の文字を処理し、次の呼び出しに再帰する解決策を考えてみてください。

あなたがそれを理解できない場合は、より詳細な説明：

  • 最初の文字から開始します。
  • 現在の文字を残りの各文字 (それ自体を含む、つまり何もしない) と交換してみてください。
  • 次の文字に戻ります。
  • 最後の文字で、すべての文字を出力します。

    • ヒント - 配列と現在のインデックスを関数に渡します。

    于 2014-04-20T21:54:38.843 に答える