пытаясь написать рекурсивную функцию, которая подсчитывает количество последовательностей, суммирующих до этого числа C ++

Question

Хорошо, вот что я пытаюсь сделать.Пользователь вводит число.Я пытаюсь написать рекурсивную функцию, которая подсчитывает количество последовательностей, которые суммируются до этого числа (пользовательский ввод).

Например:

Тогда число последовательностей, которые суммируют6 - это 11 (включая самого 6).

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3

Я также стараюсь не повторять последовательности, например, 2 + 2 + 1 + 1 и 1 + 1 + 2 + 2.

Причина, по которой у меня нетвключенный код, я не могу найти рекурсивный способ сделать эту работу, поэтому я ищу некоторое руководство.Заранее спасибо!

ДОПОЛНЕНИЕ:

Хорошо, вот мой мыслительный процесс.6 можно разделить как ...

6
5+1
4+2
3+3

, но это еще не конец, если вы берете 5 + 1 и считаете, что часть +1 завершена;Вы используете тот же трюк, чтобы продолжить.

4+1+1
3+2+1

, но затем они начинают повторяться ..... и я не продвигаюсь дальше этого второго шага в моем плане.

Хорошо, так что код мудрый, это то, что я придумал самостоятельно.Ищите предложения, чтобы это исправить.

int sum(int number, int min, int counter)
{
    int temp=0, n;
    n=number+temp;
    if (number>=(n/2)& number!=min)
    {
        while (number>=(n/2))
        {
            cout << number << "+"<< temp <<"\n";
            number --;
            temp ++;
            counter ++;
        }
    }
    sum(temp, 1,counter);
    return counter;
}

int main()
{
    int number;

    cout << "Please enter the number: ";
    cin >> number ;
    cout << "\n";

    sum(number, 1, 0);

    return 0;
}

Я понимаю, что это все запутано.

Answer 1

Подсказка: попробуйте найти функцию, которая дает число последовательностей с суммой n и членами, не превышающими k .

РЕДАКТИРОВАТЬ:
Проститьмне, если это звучит грубо, но ... ваш обновленный код все неправильно.Трудно понять, что вы хотели.Я могу догадаться, но это было бы бессмысленно.

Вот что я имел в виду: последовательность должна быть в неуклонном порядке, например, «2 2 1 1 1 1».Итак, сколько таких последовательностей составляет до 6?Ну, найдите количество таких последовательностей, начиная с 1, затем количество последовательностей, начинающихся с 2, и так далее до 6, и сложите их.А сколько последовательностей начинается с 2 и складывается до шести?(Вот здесь и начинается рекурсия.) В каждой такой последовательности первый член равен 2, а остальные составляют до 4 , а срок не превышает 2 , поэтому мы должны найти количество последовательностейдобавление до 4 без термина больше 2 .Итак, сначала напишите подпись, затем цикл итерации, затем рекурсивный вызов, и все готово.

РЕДАКТИРОВАТЬ:
Хорошо, здесь все, кроме цикла:

int partition(int n, int max)
{
  if(n==0)
    return(0);
  int ret = 0;
  if(n<=max)
    ret=1;
  for(...)
  {
    ...
  }
  return(ret);
}

Можете ли вы заполнить пробелы?

Answer 2

Алгоритм хорошо охвачен этим вопросом.

Answer 3

Определите P (n) как количество способов разбить n, ограничив n целым числом, n> = 1.

Определите p (n, k) как число способов разбить n, используя числа не больше k, ограничив k целым числом, k> = 1, k <= n. </p>

Из этого следует, что P (n) = сумма (i: 1..n) p (n, i).

Чтобы найти p (n, k), сначала обратите внимание, что мы аккуратно избегаем двойного счета, просто сохраняя разделение разделенным: сначала возьмем самый большой кусок. Таким образом, первый блок может иметь любой размер от 1 до k, а затем остальные фрагменты должны составлять остальную часть общего n и быть не больше первого фрагмента.

Таким образом, p (n, k) = сумма (i: 1..k) p (n - i, i).

В качестве базового случая p (1, 1) = 1.

---

Пример реализации, очень не гарантированно будет вообще эффективен или даже скомпилирован (но он должен дать вам основную идею) - спойлеры!

// A utility function to represent the result of appending to a vector,
// as a new vector (without affecting the previous one).
template <typename T>
vector<T> operator<<(vector<T> copy, T to_append) {
    // We passed by value to get a copy implicitly.
    copy.push_back(to_append);
    return copy;
}

// A utility function to append one vector to another.
template <typename T>
vector<T>& operator+=(vector<T>& original, const vector<T>& to_append) {
    // 'copy' is in namespace std:: and defined in <algorithm>.
    // 'back_inserter' is in namespace std:: and defined in <iterator>.
    copy(to_append.begin(), to_append.end(), back_inserter(original));
    return original;
}

vector<vector<int> > partitions(int remaining, int limit, vector<int> prefix) {
    // Finds the partitions of some larger number which start with the
    // numbers in 'prefix', such that the rest of the "chunks" sum to
    // 'remaining' and are all no larger than 'limit'.

    // 'max' is in namespace std:: and defined in <algorithm>. We restrict
    // the 'limit' to be no more than 'remaining'.
    limit = max(remaining, limit);

    vector<vector<int> > result;

    // Base case. 
    if (remaining == 1) {
        return result << (prefix << 1); // note the parentheses are required!
    }

    for (int i = limit; i > 0; --i) {
        result += partitions(remaining - i, i, prefix << i);
    }

    return result;
}

Answer 4

Пусть f (n) будет функция, которую мы хотим, которая генерирует последовательности целых чисел, которые добавляют к n, без перестановок

Define

f (n) = g (n, n)

g (n, p) = {i \ in 1..min (n, p): [ig (ni, i)]}

Answer 5

Они называются целочисленными разделами, и существует простой способ вычислить количество разделов любого числа с помощью промежуточной функции.Взгляните сюда: Целочисленный раздел .

Answer 6

Я думаю, что это близко к теории вероятностей
количество комбинаций набора {1,2,3,4,5,6}, дающих сводку 6