Рекурсивная функция подсчета и печати разделов от 1 до n-1

Я пытаюсь написать рекурсивную функцию (она должна быть рекурсивной), чтобы распечатать разделы и количество разделов от 1 до n-1. Например, 4 комбинации, сумма которых равна 4:

1 1 1 1
1 1 2
1 3
2 2

У меня просто большие проблемы с функцией. Эта функция ниже не работает. Может кто-то мне помочь, пожалуйста?

 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);
}

c++ recursion partition
person CSCI_newbie    schedule 06.03.2015    source источник
comment
Эта функция ниже не работает. Что она делает? Что выводит с помощью предоставленного образца ввода? И вы понимаете, почему это так, или у вас есть какие-либо подозрения, почему это не работает?   -  person WhozCraig    schedule 06.03.2015
comment
макс равно n-1. Вывод: Пожалуйста, введите число: 4 3+0 2+0 1+0 1+1 2+1 счетчик: 2 @WhozCraig   -  person CSCI_newbie    schedule 06.03.2015
comment
Итак, если задано число N, вы хотите найти все уникальные наборы натуральных чисел, каждый из которых находится в диапазоне [1, N), сумма которых равна N рекурсивным образом?   -  person jschultz410    schedule 06.03.2015
comment
да, но в диапазоне от 1 до n-1   -  person CSCI_newbie    schedule 06.03.2015
comment
@CSCI_newbie Я нашел решение. Все было не так просто. Вот несколько советов: пусть ваша рекурсивная функция принимает N, текущую сумму, текущий массив слагаемых и количество слагаемых. Базовый случай рекурсии - когда sum == N. В этом случае просто распечатайте массив и вернитесь. Посмотрите, сможете ли вы разобраться в рекурсивном случае. Возможно, было бы проще сначала рекурсивно вывести все перестановки суммы, а затем выяснить, как свести ее только к уникальным наборам слагаемых.   -  person jschultz410    schedule 06.03.2015

Ответы (2)


arrow_upward
0
arrow_downward

Это простой псевдокод, посмотрите, понимаете ли вы, первоначальный вызов с 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)
person Tamim Addari    schedule 06.03.2015
comment
Если бы мы вызвали это с 4, разве это не напечатало бы 1 1 1 1\n2 \n2 1 \n3 \n2 1 1 \n2 \n3 1 \n??? - person jschultz410; 06.03.2015
comment
о да, мы можем легко сохранить значение во внешнем массиве. отредактировал ответ - person Tamim Addari; 06.03.2015
comment
Это лучше, но разве он не делает все перестановки? Например на 4, 1 1 2 и 2 1 1? - person jschultz410; 06.03.2015
comment
ОП не запрашивал все перестановки, ему нужны были все комбинации в его примере. - person Tamim Addari; 06.03.2015
comment
Я знаю. Я говорю, что ваш алгоритм создает одни и те же комбинации несколько раз (как перестановки друг друга). - person jschultz410; 06.03.2015

arrow_upward
1
arrow_downward

Вот хорошее начало вашей проблемы:

#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 вы должны передать указатель на нулевое инициализированное целое число, а в рекурсии вы просто передадите указатель. Когда вы вернетесь на главную, вы можете вывести количество найденных сумм.

person jschultz410    schedule 06.03.2015