Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
#1

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

26.05.2012, 17:18. Просмотров 1286. Ответов 4
Метки нет (Все метки)

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

Задача про гостей - C++
Задача: представьте, что вы намерены пригласить к себе шестерых гостей, но за вашим столом могут поместиться всего лишь 4 человека....

Задача про дату! - C++
Три файла: 1.date.cpp 2.date.h (заголовочный) 3.main.cpp Ну собственно в main.cpp, cout месяц не тот выводит.... И если в assert...

Задача про слона 0о - C++
Нам задали прикольную задачу. От пункта А до пункта Б 12км. На каждом километре есть склад. Склады заполнены бананами(кол-во...

Задача про рюкзак - C++
Из заданных N предметов выбрать такие, чтобы суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость. ...

Задача про скобки - C++
Всем привет. Недавно показали мне такую задачу: ... намекнув на рекурсию. Кто-нибудь знает, как это решается? Спасибо :) ...

Задача про планировщик - C++
Друзья, очень надо, код написать помогите а, нужно в консольном приложении visual studio 2008 ...

4
MrGluck
Модератор
Эксперт CЭксперт С++
7497 / 4613 / 694
Регистрация: 29.11.2010
Сообщений: 12,631
26.05.2012, 17:47 #2
Да over9000. Захотел - прыгнул вперед, захотел - назад.
0
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
26.05.2012, 17:59  [ТС] #3
кузнечик умеет прыгать на 1,2,...,k столбиков вперед
0
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 обращений к ячейкам. Довольно похоже на оптимальныое решение.
1
Jeron95
11 / 11 / 1
Регистрация: 26.05.2012
Сообщений: 54
26.05.2012, 20:16  [ТС] #5
Если честно, ничего не прояснило

Добавлено через 34 минуты
Я понял, что если прыгать до k столбика то это сумма всех предыдущих вариантов добраться, а до k+1 сколько?
0
26.05.2012, 20:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2012, 20:16
Привет! Вот еще темы с ответами:

Задача про матрицу - C++
Вообщем завтра сдать надо бы по хорошему. Мне осталось сделать 1 задачу, которую я не знаю как делать. Может напишет кто-нибудь,...

Задача про дроби - C++
Сделал вроде всё правильно, но задача не работает и выдаёт ошибку на компиляции: 1> Для всех выходных данных обновления не требуется....

Задача про фермера - C++
Фермер хочет построить на своей земле как можно больший по площади сарай. Но на его участке есть деревья и хозяйственные постройки, которые...

Задача про Лестницу - C++
Условия формулируются так: Есть лестница высотой в n ступенек (плюс «нулевая» - площадка, где мы стоим вначале). На каждой ступеньке...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.