ПРОШУ ПОМОГИТЕ С++
Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним.
Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.
Входные данные
1
Результат работы
1
Входные данные
3
Результат работы
2
#include <iostream>
#include <vector>
using namespace std;
int countLadders(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i] += dp[i - j];
}
}
int result = 0;
for (int i = 1; i <= n; ++i) {
result += dp[n - i];
}
return result;
}
int main() {
int n;
cin >> n;
cout << countLadders(n) << endl;
return 0;
} Один из вариантов решения этой задачи на C++:
#include <fstream>
using namespace std;
int get_count(int prev_level, int n) {
if (0 == n) return 1;
int count = 0;
for (int level = 1; level < prev_level; ++level) {
count += get_count(level, n - level);
}
return count;
}
int main() {
ifstream ifst("input.txt");
ofstream ofst("output.txt");
int n, count = 0;
ifst >> n;
for (int level = 1; level <= n; ++level) {
count += get_count(level, n-level);
}
}
В функции main выполняется генерация кубиков в первом уровне. В нём может быть от 1 до n кубиков. Функция get_count возвращает единицу, если количество кубиков равно нулю — то есть лесенку удалось сгенерировать. Для остальных случаев запускается рекурсивная функция с различными наборами данных, уменьшая количество кубиков на текущем уровне и увеличивая на следующем.
