1

我正在编写一个程序，该程序将取 1-10 之间的数字并显示所有可能的排列数字的方式。

防爆输入：3 输出：

   1 2 3
   1 3 2
   2 1 3
   2 3 1
   3 1 2
   3 2 1

每当我输入 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;
}
4

5 回答 5

6

9!(362880) 和(3628800) 是在执行尽可能多的递归调用时会10!溢出调用堆栈的巨大数字。因为必须存储所有局部变量和形式参数。您要么必须增加堆栈大小，要么将递归转换为迭代。

在 Linux 上，您可以执行以下操作：

ulimit -s unlimited

将堆栈大小设置为无限制。默认值通常为 8MB。

于 2013-02-27T21:50:30.197 回答
2

计算排列可以迭代地完成，但即使你递归地做，也不需要有一个巨大的堆栈（就像建议增加你的系统堆栈的答案一样）。事实上，你只需要很少的筹码量。考虑一下：

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 个元素。

编辑：我冒昧地为您的重新排列功能添加了一个递归计数器，它现在打印如下：

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;
}
于 2013-02-27T22:15:46.927 回答
1

我会让你的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);
}
于 2013-02-27T21:59:52.383 回答
0

这不是深度递归的任务。尝试发明一些对堆栈更友好的算法。与堆栈大小相比，以下代码在速度方面存在相当大的问题......它有点慢，例如对于 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);
}
于 2013-02-27T22:09:53.953 回答
0

您的程序不必要地使用了太多递归。它在实际足够的情况下使用n!递归。n

要仅使用n递归，请考虑递归函数的以下逻辑：

  • 它接收一组nums[]唯一n的数字来排列
  • 这些排列可以有不同的第一个数字，因为数组中n有不同的数字n
  • （关键步骤）循环遍历 的元素nums[]，并在每次迭代中创建一个新数组，但删除当前元素，然后递归到相同的函数，将这个较短的数组作为参数传递
  • 随着递归的深入，参数数组会越来越小
  • 当只剩下一个元素时，递归结束

使用此算法，您的递归不会比您的递归更深，n并且不会出现分段错误。关键在于关键步骤，您可以在其中构建一个新的数字数组，该数组始终比输入数组短 1 项。

作为旁注，请确保在提交之前检查程序的输出，例如运行它| sort | uniq | wc -l以确保您获得正确数量的组合，并检查是否没有重复| sort | uniq -d（如果输出应该为空，如果没有重复）。

剧透警报：这是我C++使用上述算法的变体的实现： https ://gist.github.com/janosgyerik/5063197

于 2013-02-28T04:28:26.550 回答