1

ええと、再帰は私にとっていつも面倒です。

指定された文字列の順列を計算するこの関数で再帰がどのように機能するかを誰かに説明してもらえますか?

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

2 つの再帰呼び出しの後にステートメントが続く場合、再帰はどのように機能しますか? 私がはっきりしていることを願っています。

ありがとう。

4

1 に答える 1

1

コードを英語で読み上げてみてください。

この関数は、i 番目の要素から始まり、n 番目の要素で終わる文字列 a の順列を生成します。

i と n が等しい場合は、1 つの要素と 1 つの順列しかありません。

さもないと;

両端を含む i と n の間の各 j について: - i 番目の要素と j 番目の要素の位置を交換します。-最初の i 要素の順序に変更されないすべての順列を生成します。- i 番目と j 番目の要素を再び交換します。

再帰呼び出しがループしているということは、それが数回実行されることを意味します。- 文字列の潜在的な最初の文字ごとに 1 回。

具体的な例で上記が意味することは、アルゴリズムが文字列「1234」に対して行うことです。

最初に、"1" で始まり、"234" のすべての順列が続く文字列を生成します。つまり、たまたま "1" で始まる "1234" のすべての順列です。

次に、「2」で始まる順列をすべて生成します。

そして、すべては「3」から始まります。

最後に、「4」で始まるすべての順列。

"1234" のすべての順列は "1"、"2"、"3"、または "4" で始まるため、文字列 "1234" のすべての順列が生成されます。

これが帰納法によって機能することを証明し、「読者の演習として残します」。

于 2013-08-29T11:15:37.640 に答える