PeGaSuS

Приветик всем!!!
вот задача которая была на городской олимпиаде 2007 года не знаю кто может решить этоо:

Зайчик по дорожке длиной N может прыгать только вперед. Длина прыжка зайчика не должна превышать K(1>=K, N<=100). Требуется вывести число возможных способов для прохождения зайчиком всей пути.
Например
При N=3, K=2 для зайчика возможны след>> прыжки : 1,1,1 1,2 2,1
В этом случае ответ равен 3.
Входные данные: N и K.

Кто сможет написать please помогите!!
а вообще кому не лень можете добавлять интересные задачки))

Dram

Я в этом году тоже ходил на олимпиаду по информатике думал мож че из паскаля вспомню но нет фиг посидели поржали над задачками и ушли

PeGaSuS

уж очень они смешные были????

Darkcosinus

Меня посылали на олимпиаду по программированию, так там проверяющие знали только BASIC, это полный пейсец. Я написал им полностью все алгоритмы на C++ и получил 0 баллов. Больше на олимпиады не ходил.

Единственные задачки, которые представляют интерес - это реальные задания из проектов, за которые платятся деньги Учебные задачи обычно высосаны из пальца и очень редко близки к программерским будням.

А задачка интересная... нужно найти все комбинации чисел, не превышающих K, которые в сумме дают N.

Задача, кстати, имеет решение даже при K>N. На этот случай нужно ввести, допустим, P, которое равно MIN(K,N).

Максимальное число прыжков соответственно будет при K=1 и равно N.

Думаю, решать стоит перебором "в лоб"... Хотя если олимпиада универская, можно и по формулам комбинаторики
Идея перебора такова:
0) Создаём переменную для кол-ва вариантов, допустим I=0
1) Вариантов первого прыжка у нас P. I=I+P
2) Для каждого из P прыжков считаем оставшееся расстояние D=(N-P)
3) Если D=0, то выходим из этой ветки
4) Если D>0, то считаем кол-во вариантов для следующего прыжка. Их будет V=MIN(D,P). I=I+V

Видно, что шаги 1 и 4 идентичны, можно оформить это всё в виде рекурсии и начинать с I=0 и D=P.
Мысли пока сумбурные, может и напутал чего...

Vladimir_S

Алекс, Вы простите великодушно, в задачу не вникал, но то, что Вы написали, есть просто s:=n . Зачем же так мудрёно?

Darkcosinus

s=n? Это формула чего?
Тут простой комбинаторикой не обойтись. Если уж брать комбинаторику, тогда формулу сочетания с повторениями, и всё оно примет вид

сумма ((X+N-1)! / ((X-1)! * N!))
где X принимает значения от 1 до P

Но по этой формуле получим только все варианты движения зайца. Естественно далеко не все они нам подойдут, т.к. многие пути будут заведомо длиннее N. А как отсеивать без прямого перебора, я не представляю.

Поэтому всё-таки не думаю, что комбинаторика тут жизнеспособна.

AlexZir

Извиняюсь, ошибочка вышла, исправил, удалил формулу.
Вник в задачу, сочетание с повторениями здесь тоже не пойдет. Но обычно такого рода задания должны решаться более-менее простым способом. Иначе участники не успеют ничего решить. Так что должно быть простое решение.

__________________
Убить всех человеков!

PeGaSuS

thankS everybody. если честно я еще не смогла вникнуть в то о чем вы толкуете((

Darkcosinus

Простое решение - перебор, алгоритм которого я написал.

Кстати кому интересно, вот задачка ещё:
Написать наиболее оптимальным образом функцию, которая возвращает 5 при переданном ей параметре 3, и возвращает 3 при параметре 5
Сразу скажу, что очевидные if или case не являются оптимальными )

Vladimir_S

Ну это мы еще можем: y = 15 : x . Во!