递归函数计数和打印 1 到 n-1 的分区

Question

我正在尝试编写一个递归函数（它必须是递归的）来打印出 1 到 n-1 的分区和分区数。例如，总和为 4 的 4 个组合：

我只是在使用该功能时遇到了很多麻烦。下面这个功能不起作用。有人可以帮我吗？

 int partition(int n, int max)
{

  if(n==1||max==1)
    return(1);
  int counter = 0;
  if(n<=max)
    counter=1;
  for(int i = 0; n>i; i++){
          n=n-1;
          cout << n << "+"<< i <<"\n";
          counter++;
          partition(n,i);         
        }

  return(counter);
}

Answer 1

这是解决您的问题的良好开端：

#include <stdlib.h>
#include <stdio.h>

void partition(int n, int sum, int *summands, int num_summands)
{
  int i;

  if (sum == n)  // base case of recursion
  {
    if (num_summands > 1)  // don't print n by itself
    {
      for (i = 0; i < num_summands; ++i)
        printf("%d ", summands[i]);

      printf("\n");
    }
  }
  else
  {
    /* TODO: fill in recursive case */
    /* Iteratively recurse after appending one additional, varying summand to summands */
    /* It might be easier to first generate all permutations of the sums */
    /* and then figure out how to reduce that down to only the unique sets of summands (think sorting) */
  }
}

int main(int argc, char **argv)
{
  if (argc == 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int n = atoi(argv[1]);

  if (n <= 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int summands[n+1];               // NOTE: +1's are to make summands[-1] always safe inside recursion

  summands[0] = 1;                 // NOTE: make summands[-1] == 1 at top level of recursion
  partition(n, 0, summands+1, 0);  // NOTE: +1's are to make summands[-1] always safe inside recursion

  return 0;
}

如果您需要对找到的总和进行计数，则可以向 partition 添加一个额外参数，该参数是一个指向 (int) 到目前为止找到的总和计数的指针。您只会在打印基本案例中增加该计数。在 main 中，您将传递一个指向零初始化整数的指针，而在递归中，您只需传递指针。当你回到 main 时，你可以打印你找到的总和数。

Answer 2

这是一个简单的伪代码，看看你是否理解，初始调用是用 recPartition(n,1)

int A[100]
int n
int cnt = 0
recPartition(int remaining,int indx)
    if(remaining <0 )
       return
    if(remaining == 0)
        print from 1 to indx in A
        ++cnt
        return
    for i from 1 to remaining
         if(i!=n)
             A[indx] = i
             recPartition(remaining-i,indx+1)

递归函数计数和打印 1 到 n-1 的分区

Recursive function counting and printing partitions of 1 to n-1

c++

recursion

partition