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

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

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

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

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

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

Задача про метеостанции - C++
На южном полюсе расположены N пронумерованных метеорологических станций. Каждая станция соединена с другими станциями линиями связи. В...

Задача про 2 рюкзака - C++
Дано n предметов a1..an, и дан вес каждого из них. Требуется разделить все предметы на две группы так, чтобы вес каждой из груп был...

Задача про зайца - C++
В небольшой посадке живет заяц. Выскочив из норы и бегая по снегу, он оставил следы. Определить где находится заяц. ВХОДНЫЕ ДАНЫЕ Карта...

Задача про монахов - C++
Условие такое: Имеется n монахов и m пирогов. Ведущий монах съедает за один раз 10 пирогов, обычный - 5, ученик монаха - 0.5. Вывести все...

Задача про торт - C++
/*Задача интересная и на самом деле не сложная, но в виду того что я кодю вторые сутки, не могу придумать алгоритм. Хочу отметить, что мне...

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

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

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

Задача про температуру - C++
Здравствуйте! Напишите программу, определяющую в какие дни температура воздуха превышает среднее значение температуры в это время...

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Модератор
Эксперт CЭксперт С++
6960 / 4131 / 586
Регистрация: 29.11.2010
Сообщений: 10,956
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     Задача про кузнечиков
Ответ Создать тему
Опции темы

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