Форум программистов, компьютерный форум CyberForum.ru

Задача про кузнечиков - C++

Войти
Регистрация
Восстановить пароль
 
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
26.05.2012, 17:18     Задача про кузнечиков #1
Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов, которым он может допрыгать до n-го столба.
Я знаю что решается динамическим программированием, пытался сам в нём разобрать, но не получилось.
Мне нужен код на Pascal или C++, желательно с подробным объяснением.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 17:18     Задача про кузнечиков
Посмотрите здесь:

C++ Задача про шахматы
Задача про скобки C++
Задача про монахов C++
задача про матрицы C++
C++ Задача про самолет
Задача про планировщик C++
Задача про Лестницу C++
Задача про календарь C++
Задача про карты C++
C++ задача про графы
Задача про дроби C++
C++ Задача про небоскребы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
5667 / 3146 / 357
Регистрация: 29.11.2010
Сообщений: 8,420
26.05.2012, 17:47     Задача про кузнечиков #2
Да over9000. Захотел - прыгнул вперед, захотел - назад.
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
26.05.2012, 17:59  [ТС]     Задача про кузнечиков #3
кузнечик умеет прыгать на 1,2,...,k столбиков вперед
33parrots
3 / 3 / 0
Регистрация: 25.05.2012
Сообщений: 23
26.05.2012, 18:47     Задача про кузнечиков #4
будем обозначать к-во вариантов с позиции, когда осталось Р столбиков f(p). Тогда
f(p)= f(p-1) + f(p-2) + ... + f(p-k),
причём f(0)=1, f(число меньше 0)=0.

И если впадло писать код и n маленькое - пошла рекурсия,
если хочешь нормально - создаём массив размером n, в котором будут храниться f(p) для р=1..n
И пошла индукция, р увеличивем от 1 до n, на каждом шаге сохраняем f(p) в массив. Этот алгоритм требует n раз взять сумму k (по крайней мере не более чем k) элементов, но подлость в том, что такой алгоритм не оптимален.

Ведь на самом деле
f(p) = f(p-1) + f(p-2) + ... + f(p-k) = f(p-1) + f(p-1) - f(p-k-1) = 2*f(p-1) - f(p-k-1)
И тогда для нохождения каждого нового элемента нам нужно 2 операции сложения вместо к операций сложения. Можно заюзать операцию умножения и операцию сложения, здесь вопрос в том, что легче - (операция умножения) или (операция сложения плюс дополнительное обращение к ячейке памяти). Я начинающий программист, на такой вопрос ответа, к сожалению, не знаю.

Итого имеем 2n операций сложения + 3n обращений к ячейкам, либо n операций сложения, столько же операций умножения и 2n обращений к ячейкам. Довольно похоже на оптимальныое решение.
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
26.05.2012, 20:16  [ТС]     Задача про кузнечиков #5
Если честно, ничего не прояснило

Добавлено через 34 минуты
Я понял, что если прыгать до k столбика то это сумма всех предыдущих вариантов добраться, а до k+1 сколько?
Yandex
Объявления
26.05.2012, 20:16     Задача про кузнечиков
Ответ Создать тему
Опции темы

Текущее время: 07:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru