Программирование на Паскале ))))

[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!/(n-1)!

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

 

[Darkcosinus]

s:=n!/(n-1)!

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]

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

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

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

 

[Darkcosinus]

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

Ну-ну, и при x=0 словим division by zero, а при x, ну например, 8 - type mismatch

 

[Vladimir_S]

Ну-ну, и при x=0 словим division by zero, а при x, ну например, 8 - type mismatch

Тогда надо условие иначе ставить и оговаривать диапазоны и ограничения. А так как Вы сформулировали - всё удовлетворяет! Кидаешь 3 - на выходе 5 и наоборот . Откуда я знаю - может быть там на входе перечисляемый тип с двумя значениями - 3 и 5?

А хотите во всём диапазоне - пожалуйста: y = 8 - x . О как мы могём!

 

[Darkcosinus]

А так как Вы сформулировали - всё удовлетворяет!

Эта задача задавалась при приёме на работу в крупную софтверную компанию, в которой за такую фразу уволят в момент Типы данных, диапазоны входных данных - всё это можно было уточнить, а если не уточнить, то написать ограничения.

А хотите во всём диапазоне - пожалуйста: y = 8 - x . О как мы могём!

Вот это уже правильное решение.

 

[Vladimir_S]

Ох, как хорошо, что я не собираюсь устраиваться в крупную софтверную кампанию! А вообще, если серьезно, - не согласен категорически! Программирование - деятельность точная, ибо компьютер понимает всё буквально, и программист очень быстро от него заражается подобным мироощущением. А если заказчик невнятно формулирует задачу и отказывает программисту в приеме на работу по причине неспособности последнего влезть в заказчикову подкорку, то это, полагаю, на совести заказчика - буде таковая обнаружится. В связи с этим предлагаю еще раз разобрать формулировку. Обращаю внимание на пояснение - "очевидные if или case не являются оптимальными", т.е. эти операторы РЕШАЮТ задачу! Но ведь не реально перебирать весь диапазон значений аргумента посредством операторов выбора, а значит предполагается всего два значения - 3 и 5. А раз так, то вариант с произведением ничуть не хуже варианта с суммой.
Простите за оффтоп, но уж если начал... Вот вам этическая задача на базе анекдота. Зайдя в кабинет к начальнику, услужливый подчиненный увидел, что тот пытается запихнуть какие-то бумаги в свежеприобретенный уничтожитель документов, но, очевидно, не знает, как обращаться с аппаратом. Подчиненный, естественно, вызывается помочь, берет бумаги и проделывает всё, как надо. Начальник кивает головой и в конце изрекает: "Мне в двух экземплярах, пожалуйста". Вопрос: кто виноват?

 

[Darkcosinus]

К сожалению реальные условия работы далеки от идеального о них представления

Комментарий про if и case - мой. В исходном тексте условия его нет. Работодатель проверяет, умеет ли человек оптимизировать код и понимает ли, как это делается, или он просто научился писать алгоритмы. Там остальные задачи ещё хлеще

Из реальных примеров - пожалуйста. Из проекта недельной давности. Есть на сайте меню выбора модели авто, всего ~500 наименований, они все есть в базе данных. База часто обновляется. Делается "чтоб работало" - при вызове скрипта читаются все строки из БД и выводятся в меню. Когда сайт прорекламировался, на него пошли посетители, и несколько выборов и сортировок 500 элементов из БД в секунду элементарно эту БД заваливали.
Работает? Конечно. Чья вина, что сайт заваливается? Заказчика, который не написал в ТЗ, что "сайт должен выдерживать N обращений в секунду"? Вы бы как заказчик стали платить такому исполнителю?

Вернёмся к функции - то, что предполагаются два значения - всего лишь догадка. В крупных проектах программист не пишет всю программу целиком, он разрабатывает модуль. Если другой программист не позаботился о корректности выходных данных своего модуля, которые поступают на вход нашего модуля, а в нашем модуле при неверном параметре происходит format c: /s , то кто виноват в последствиях? Вопрос нелёгкий и неоднозначный, но исключения и их последствия уже как-то сами собой должны всплывать в мыслях при разработке...

 

[Vladimir_S]

Из реальных примеров - пожалуйста. Из проекта недельной давности. Есть на сайте меню выбора модели авто, всего ~500 наименований, они все есть в базе данных. База часто обновляется. Делается "чтоб работало" - при вызове скрипта читаются все строки из БД и выводятся в меню. Когда сайт прорекламировался, на него пошли посетители, и несколько выборов и сортировок 500 элементов из БД в секунду элементарно эту БД заваливали.
Работает? Конечно. Чья вина, что сайт заваливается? Заказчика, который не написал в ТЗ, что "сайт должен выдерживать N обращений в секунду"? Вы бы как заказчик стали платить такому исполнителю?

Ситуация интересная. Отвечу так. Поскольку вопрос спорный, я бы не торопился увольнять программиста, а поставил бы ему конкретную задачу по переработке кода, а дальше посмотрел бы, как быстро и эффективно он с этим справится. И если он, скажем, в течение дня сумел бы всё наладить, то никаких претензий к нему я бы предъявлять не стал - напротив, считал бы, что у человека появился опыт, гарантирующий впредь неповторение подобного. Не говоря уже о том, что завал сайта может быть обусловлен вообще слабостью сервера - и тут уж никакой программист не поможет!

 

[Darkcosinus]

Ну в данном случае оптимизация запросов к БД - долг каждого программиста Потому как возможности баз и серверов, использующихся в веб, известны.
Если он ответит "как задачу поставили, так я и сделал, работает ведь", то я бы такого точно держать не стал.
Фишка в том, что каждый день простоя для магазина - это убытки, сравнимые по стоимости с созданием самого магазина.
В общем с точки зрения программиста и его начальника - программер не имел опыта, теперь заимел. С точки зрения заказчика - работа была выполнена непрофессионалами и потом залатана. Вряд ли обратятся в эту компанию ещё раз.

Вот чтобы отсеять таких программеров, которые будут учиться на ошибках в процессе работы в этой компании, и принять тех, которые уже наделали ошибок в другой компании, и теперь не будут, такие тесты и делаются )