Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

ПРОШУ ПОМОГИТЕ С С++

leyla nuriyeva Ученик (86), открыт 3 недели назад
Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним.
Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.
Входные данные

1
Результат работы

1
Входные данные

3
Результат работы

2
3 ответа
R.H. Мастер (1201) 3 недели назад
 #include <iostream> 
#include <vector>

using namespace std;

int countStaircases(int N) {
// Создаем двумерный массив dp размером (N+1) x (N+1) и заполняем его нулями
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));

// Инициализируем базовый случай
for (int k = 0; k <= N; ++k) {
dp[0][k] = 1; // 1 способ построить лесенку из 0 кубиков
}

// Заполняем массив dp по описанному выше рекуррентному соотношению
for (int n = 1; n <= N; ++n) {
for (int k = 1; k <= N; ++k) {
dp[n][k] = dp[n][k - 1];
if (n >= k) {
dp[n][k] += dp[n - k][k - 1];
}
}
}

// Ответ находится в dp[N][N]
return dp[N][N];
}

int main() {
int N;
cout << "Введите количество кубиков N: ";
cin >> N;

int result = countStaircases(N);
cout << "Количество различных лесенок: " << result << endl;

return 0;
}
ауцыв уафсыв Гуру (4666) 3 недели назад
 #include <iostream> 
#include <vector>

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

// dp[i][j] - количество способов представить число i с максимальным слагаемым j
std::vector<std::vector<int>> dp(N + 1, std::vector<int>(N + 1, 0));

// Инициализация: для числа 0 есть 1 способ разложения (пустое множество)
dp[0][0] = 1;

for (int sum = 1; sum <= N; ++sum) {
for (int last = 1; last <= sum; ++last) {
// Перебираем все возможные предыдущие слагаемые, которые меньше, чем текущее
for (int prev = last - 1; prev >= 0; --prev) {
dp[sum][last] += dp[sum - last][prev];
}
}
}

// Суммируем все варианты разбиений числа N
int result = 0;
for (int last = 1; last <= N; ++last) {
result += dp[N][last];
}

std::cout << result << std::endl;

return 0;
}
Алексей Потапов Профи (797) 3 недели назад
 #include <iostream> 
#include <vector>

using namespace std;

int countLadders(int N) {
// Создаем массив для хранения результатов
vector<int> dp(N + 1, 0);
dp[0] = 1; // 1 способ построить лесенку из 0 кубиков

// Перебираем количество кубиков
for (int i = 1; i <= N; ++i) {
// Перебираем возможные верхние слои
for (int j = 1; j <= i; ++j) {
dp[i] += dp[i - j];
}
}

return dp[N];
}

int main() {
int N;
cout << "Введите количество кубиков: ";
cin >> N;

int result = countLadders(N);
cout << "Количество различных лесенок: " << result << endl;

return 0;
}
Похожие вопросы