Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Jeron95
11 / 11 / 2
Регистрация: 26.05.2012
Сообщений: 54
#1

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

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

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

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

Задача про графы
помогите если не сложно Тексты нужно переписывать в тело сообщения!

Задача про рюкзак
Всем привет! Есть программа, которая решает задачу про рюкзак. Когда у меня...

Задача про слона 0о
Нам задали прикольную задачу. От пункта А до пункта Б 12км. На каждом...

Задача про теплоход
Теплоход проходит за P1 по течению и R1 часа против течения S км. Он же за R2 ч...

4
MrGluck
Модератор
Эксперт CЭксперт С++
7981 / 4862 / 1423
Регистрация: 29.11.2010
Сообщений: 13,237
26.05.2012, 17:47 #2
Да over9000. Захотел - прыгнул вперед, захотел - назад.
0
Jeron95
11 / 11 / 2
Регистрация: 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 / 2
Регистрация: 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
Привет! Вот еще темы с решениями:

Задача про карты
Написать программу, которая предлагает пользователю ввести порядковый номер...

задача про Перегоны
На некоторой железнодорожной ветке расположено N станций, которые...

Задача про триугольник
Треугольник задан координатами своих вершин. Найти периметр и площадь.

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


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

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

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