c - 再帰によるセグメンテーション違反

Question

1 から 10 までの数字を取り、その数字を並べ替えるすべての可能な方法を表示するプログラムを作成しています。

Ex 入力: 3 出力:

9 または 10 を入力するたびに、プログラムはセグメンテーション違反を発生させ、コアをダンプします。問題は、再帰アルゴリズムが何度も呼び出されていることだと思います。必要な再帰呼び出しの量を制限する方法を誰かが指摘してくれませんか? これが私の現在のコードです：

void rearange(int numbers[11], int index, int num, int fact) {

  int temp = numbers[index];
  numbers[index] = numbers[index-1];
  numbers[index-1] = temp;

  int i;
  for (i = 1; i <= num; ++i) // print the current sequence
  {
    printf("%d ", numbers[i]);
  }
  printf("\n");

  fact--;  // decrement how many sequences remain
  index--; // decrement our index in the array

  if (index == 1) // if we're at the beginning of the array
    index = num;    // reset index to end of the array

  if (fact > 0) // If we have more sequences remaining
    rearange(numbers, index, num, fact);    // Do it all again! :D
}

int main() {
  int num, i; // our number and a counter

  printf("Enter a number less than 10: ");
  scanf("%d", &num); // get the number from the user

  int numbers[11]; // create an array of appropriate size
  // fill array
  for (i = 1; i <= num; i++) { // fill the array from 1 to num
    numbers[i] = i;
  }

  int fact = 1; // calculate the factorial to determine
  for (i = 1; i <= num; ++i) // how many possible sequences
  {
    fact = fact * i;
  }

  rearange(numbers, num, num, fact); // begin rearranging by recursion

  return 0;
}

score 6 · Accepted Answer

9!(362880) と10!(3628800) は、再帰呼び出しを何度も行うと呼び出しスタックがオーバーフローする巨大な数値です。すべてのローカル変数と仮パラメーターを保存する必要があるためです。スタックサイズを増やすか、再帰を反復に変換する必要があります。

Linux では、次のことができます。

ulimit -s unlimited

スタックサイズを無制限に設定します。デフォルトは通常 8MB です。

score 2 · Accepted Answer

順列の計算は反復的に行うことができますが、再帰的に行う場合でも、巨大なスタックを用意する必要はありません (システムスタックを増やすことを提案する回答のように)。実際、必要なスタックはごくわずかです。このことを考慮：

0 1      <- this needs **2** stackframes 
1 0                and an for-loop of size 2 in each stackframe

0 1 2    <- this needs **3** stackframes 
0 2 1              and an for-loop of size 3 in each stackframe
1 0 2
1 2 0
2 1 0
2 0 1

9 つの要素を並べ替えるには、 9つのスタックフレームと、各スタックフレームの 9 つの要素を使用する for ループが必要です。

編集:再帰カウンターを再配置関数に追加する自由を取りました。次のように出力されます。

Enter a number less than 10: 4
depth 1      1 2 4 3
depth 2      1 4 2 3
depth 3      4 1 2 3
depth 4      4 1 3 2
depth 5      4 3 1 2
depth 6      3 4 1 2
depth 7      3 4 2 1
depth 8      3 2 4 1
depth 9      2 3 4 1
depth 10      2 3 1 4
depth 11      2 1 3 4
depth 12      1 2 3 4
depth 13      1 2 4 3
depth 14      1 4 2 3
depth 15      4 1 2 3
depth 16      4 1 3 2  which is obviously wrong even if you do it recursively.
depth 17      4 3 1 2
depth 18      3 4 1 2
depth 19      3 4 2 1
depth 20      3 2 4 1
depth 21      2 3 4 1
depth 22      2 3 1 4
depth 23      2 1 3 4
depth 24      1 2 3 4
....

再帰リーフのみが出力されるため、深さは一定で小さくなければなりません (入力した数値に等しい)。

編集2：

わかりました、コードを書きました。やってみて：

#include "stdio.h"
void betterRecursion(int depth, int elems, int* temp) {
    if(depth==elems) {
        int j=0;for(;j<elems;++j){
            printf("%i ", temp[j]);
        }
        printf("   (at recursion depth %u)\n", depth);
    } else {
        int i=0;for(;i<elems;++i){
            temp[depth] = i;
            betterRecursion(depth+1, elems, temp);
        }
    }
}
int main() {
    int temp[100];
    betterRecursion(0, 11, temp); // arrange the 11 elements 0...10
    return 0;
}

score 1 · Accepted Answer

私はあなたのrearange関数を反復的にします-do while追加し、再帰呼び出しを削除します:

void rearange(int numbers[11], int index, int num, int fact) {
    int temp;
    do
    {
      temp = numbers[index];
      numbers[index] = numbers[index-1];
      numbers[index-1] = temp;

      int i;
      for (i = 1; i <= num; ++i) // print the current sequence
      {
        printf("%d ", numbers[i]);
      }
      printf("\n");

      fact--;  // decrement how many sequences remain
      index--; // decrement our index in the array

      if (index == 1) // if we're at the beginning of the array
        index = num;    // reset index to end of the array

    } while (fact > 0);
}

score 0 · Accepted Answer

あなたのプログラムは不必要に多くの再帰を使用しています。n!実際にnは十分な場合に再帰を使用しています。

再帰のみを使用するnには、再帰関数について次のロジックを検討してください。

配列する一意の番号の配列nums[]を受け取りますn
配列には異なる番号があるため、アレンジメントにはn異なる最初の番号を含めることができますn
(重要なステップ) の要素をループし、nums[]各反復で新しい配列を作成しますが、現在の要素は削除され、この短い配列をパラメーターとして渡す同じ関数に再帰します。
より深く再帰するにつれて、パラメーター配列はますます小さくなります
残りの要素が 1 つだけになったら、再帰の終わりです

このアルゴリズムを使用すると、再帰はより深くnならず、セグメンテーション違反も発生しません。重要なのは、入力配列よりも常に 1 項目短い数値の新しい配列を作成する重要なステップにあります。

ネタバレ注意:C++上記のアルゴリズムのバリエーションを使用した私の実装は次のとおりです: https://gist.github.com/janosgyerik/5063197

score 0 · Accepted Answer

これは、深い再帰のタスクではありません。よりスタックフレンドリーなアルゴリズムを発明してみてください。次のコードは、スタックサイズよりも速度に問題があります...たとえば n=1000 の場合は少し遅いですが、動作します。

#include <stdio.h>

void print_arrangement(int n, int* x)
{
  int i;
  for(i = 0; i < n; i++)
  {
  printf("%s%d", i ? " " : "", x[i]);
  }
  printf("\n");
}

void generate_arrangements(int n, int k, int* x)
{
    int i;
    int j;
    int found;

    if (n == k)
    {
        print_arrangement(n, x);
    }
    else
    {
    for(i = 1; i <= n; i++)
    {
        found = 0;
        for(j = 0; j < k; j++)
        {
            if (x[j] == i)
            {
                found = 1;
            }
        }
        if (!found)
        {
            x[k] = i;
            generate_arrangements(n, k + 1, x);
        }
    }   
    }
}

int main(int argc, char **argv)
{
  int x[50];
  generate_arrangements(50, 0, x);
}

c - 再帰によるセグメンテーション違反

5 に答える 5

Related

Reference