Программирование на Паскале ))))
Приветик всем!!!
вот задача которая была на городской олимпиаде 2007 года не знаю кто может решить этоо: Зайчик по дорожке длиной N может прыгать только вперед. Длина прыжка зайчика не должна превышать K(1>=K, N<=100). Требуется вывести число возможных способов для прохождения зайчиком всей пути. Например При N=3, K=2 для зайчика возможны след>> прыжки : 1,1,1 1,2 2,1 В этом случае ответ равен 3. Входные данные: N и K. Кто сможет написать please помогите!! а вообще кому не лень можете добавлять интересные задачки)) :) |
Я в этом году тоже ходил на олимпиаду по информатике думал мож че из паскаля вспомню но нет фиг посидели поржали над задачками и ушли
|
уж очень они смешные были???? :)
|
Меня посылали на олимпиаду по программированию, так там проверяющие знали только 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. Мысли пока сумбурные, может и напутал чего... |
Цитата:
|
Цитата:
Тут простой комбинаторикой не обойтись. Если уж брать комбинаторику, тогда формулу сочетания с повторениями, и всё оно примет вид сумма ((X+N-1)! / ((X-1)! * N!)) где X принимает значения от 1 до P Но по этой формуле получим только все варианты движения зайца. Естественно далеко не все они нам подойдут, т.к. многие пути будут заведомо длиннее N. А как отсеивать без прямого перебора, я не представляю. Поэтому всё-таки не думаю, что комбинаторика тут жизнеспособна. |
Извиняюсь, ошибочка вышла, исправил, удалил формулу.
Вник в задачу, сочетание с повторениями здесь тоже не пойдет. Но обычно такого рода задания должны решаться более-менее простым способом. Иначе участники не успеют ничего решить. Так что должно быть простое решение. |
thankS everybody. если честно я еще не смогла вникнуть в то о чем вы толкуете((
|
Простое решение - перебор, алгоритм которого я написал.
Кстати кому интересно, вот задачка ещё: Написать наиболее оптимальным образом функцию, которая возвращает 5 при переданном ей параметре 3, и возвращает 3 при параметре 5 :) Сразу скажу, что очевидные if или case не являются оптимальными ) |
Цитата:
|
Часовой пояс GMT +4, время: 21:48. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.