Question

РЕШИТЬ ТОЛЬКО НА С++ Лесенки Лесенкой называется набор кубиков, в котором каждый следующий горизонтальный слой содержит меньше кубиков, чем слой под ним. Требуется подсчитать количество различных лесенок, которые могут быть построены ровно из N кубиков. Входные данные Вводится одно число N(1≤N≤50). Выходные данные Выведите искомое количество лесенок. Примеры Ввод 3 Вывод 2

Answer 1

Ответ:

#include <iostream>

using namespace std;

int func(int a, int b)

{

  if(!b)

      return 1;

  int count = 0;

  for(int i = 1; i < a; ++i)

    if(b - i >= 0)

      count += func(i, b - i);

  return count;

}

int main()

{

  int n;

  cin >> n;

  int count = 0;

  for(int i = 1; i <= n; ++i)

      count += func(i, n - i);

  cout << count;

  return 0;

}

Answer 2

Для решения задачи на подсчет количества различных лесенок с использованием языка C++, мы можем воспользоваться динамическим программированием.

Создадим массив dp, где dp[i] будет представлять количество различных лесенок из i кубиков. Заполним этот массив снизу вверх, начиная с одного кубика и заканчивая N кубиками.

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> dp(N + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] += dp[j];
        }
    }

    cout << dp[N] << endl;

    return 0;
}

В данном примере мы используем массив dp для хранения количества лесенок для каждого количества кубиков от 0 до N. Мы начинаем с 1 кубика и, для каждого дополнительного кубика, считаем количество возможных лесенок, учитывая предыдущие слои. В конечном итоге выводим результат для N кубиков.