Отправлено: 22.10.10 11:17. Заголовок: Интересные задачки

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

итак:
В дремучем царстве, в тридевятом государстве, на высоком холме стоит старый поезд. Представляет собой поезд кольцо - много-много совершенно одинаковых вагонов сцеплены в круг так, что не понятно где начало, а где конец. Во всех вагонах, поддаваясь неизвестной логике (тобишь случайно) включен или выключен свет. Ты стоишь в каком-то вагоне и можешь переходить из одного в другой и включать\выключать там свет. Естественно из окон ничего не видно, а мелков (и иных субстанций), что бы пометить вагон из которого начал своё путешествие - нет.

Требуется посчитать количество вагонов и тогда магические оковы спадут и свет победит зло.

// а сеттинг-то каков! сюрр, хоррор и психоделика с элементами мрачной сказки. и- логика, естессно))

 Отправлено: 22.10.10 12:29. Заголовок: субстанций вишь у ме..

субстанций вишь у меня нет... а штаны у меня есть? Короче, варианты решения задачи:

1. Снять что-то из одежды и оставить в вагоне - на полке - во избежание гномиков-воров, которые могут стибрить оставленное на полу. Выключаем свет. Потом идем по вагонам всюду включая свет, считая вагоны Как дошли до темного - включаем и проверяем, не лежит ли на полке моя мантия/кепочка/футболочка (волосок из бороды, знак на пыльном стекле, выбитое окно или разбитая лампочка и т.п.) Если да - мы описали круг! Задача решена с одного оборота!

2. Ладно, предположим, дело происходит во сне и не написАть неприличное слово на стекле, как сделал бы нормальный человек, ни напИсать в углу вагона, пометив его как сделал бы любой нормальный пес нельзя... то есть надо действовать строго в соответствии с условиями задачи. Блин... не знаю! Случайная последовательность при случайной длине поезда - это черт знает что такое!!!

 Отправлено: 22.10.10 21:45. Заголовок: Идешь, считаешь гром..

А как магические оковы определяют, что количество вагонов нам известно? Типа, проговариваешь вслух количество плюс кодовое слово? Тогда можно просто считать: "один вагон <кодовое слово>", "два вагона <кодовое слово>" и т. д. Когда будет названо правильное число вагонов в сочетании с кодовым словом, магические оковы поведутся, как олень, и спадут. Звук грохота падающих оков одновременно будет означать, что мы определили-таки количество вагонов.

Скрытый текст

На самом деле, алгоритм решения такой. Сначала идем на два вагона, скажем, против часовой стрелки и в каждом зажигаем свет. Затем идем на три вагона в противоположном направлении и везде тушим свет. И так далее, каждый раз меняя направление, включение/выключение света и на один увеличивая число вагонов. На некой итерации, обрабатывая цепочку длиной в n вагонов, мы обнаружим, что вагон с "не тем" состоянием света (выключенным, если в предыдущий раз мы свет включали, и включенным, если выключали) встретится нам слишком рано (через n-1 вагонов). Общее число вагонов составит n-2. Данные выкладки проще всего проверить на поезде из двух вагонов.

 Отправлено: 23.10.10 00:14. Заголовок: Значит, делаем следу..

У меня такой вариант, по-моему, более быстрый.
Скрытый текст

Значит, делаем следующим образом: :Start Тот вагон, в котором мы находимся, назовем "первичный вагон". Включаем в нем свет. : Loop Идем в одном направлении, отсчитывая вагоны от первичного до тех пор, пока не дойдем до вагона с включенным светом. Выключаем в нем свет и возвращаемся в обратном направлении к первичному вагону (благо мы отсчитывали). IF Если в первичном вагоне свет выключился THEN следовательно, мы сделали один оборот & goto HappyEnd ELSE Если свет в первичном вагоне остался включенным, значит, тот вагон, в котором мы выключили, свет был не первичным. & Goto Loop :HappyEnd Число вагонов, которое мы отсчитали до вагона, в котором в последний раз выключили свет = общее число вагонов в кольце.

 Отправлено: 23.10.10 01:10. Заголовок: Saruman пишет: 1. Сн..

Saruman пишет:

цитата:

1. Снять что-то из одежды и оставить в вагоне

мож Гор напишет об этом очередные Блудни))
uux интересные мысли))
Агент 007, круто!

 Отправлено: 23.10.10 01:25. Заголовок: а как вам такая ЗАДА..

а как вам такая ЗАДАЧКА: нужно написать прогу(а лучше- алгоритм)

ДАНО: дан входной файл, состоящий из конечного кол-ва строк вида:

<номер строки>. LET <имя переменной>= <логическое выражение>;
<номер строки>. IF <логическое выражение> GO TO <номер строки>;
<номер строки>. END.

где
<номер строки> - это просто какие-то уникальные номера, которые служат метками строк.
<имя переменной> - допустимы всего два имени переменных: A и B. все переменные имеют булевский тип.
<логическое выражение>- может быть..
.. либо числом 0 или 1(понимаются как булевские FALSE и TRUE),
.. либо переменной (A или B),
.. либо конструкцией вида not(<логическое выражение>)

END. - завершает выполнение проги. при этом последняя строка данного файла обязана содержать именно END. а не что-то другое.

НАДО: написать по-возможности простую прогу, для определения того, может ли зациклиться прога, представленная во входном файле, или же она достигнет END за конечное время при любых начальных значениях переменных A и B

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

вот, как-то так, если склероз мне не изменяет память.

 Отправлено: 23.10.10 01:27. Заголовок: qwerty пишет: напис..

qwerty пишет:

цитата:

написать по-возможности простую прогу

ну, полноценную прогу делать долго, а вот кратко описать простенький алгоритм- гораздо проще.

 Отправлено: 25.10.10 05:32. Заголовок: Прога сама по себе б..

Прога сама по себе будет достаточно простая, правда, выполняться будет долго;).

Скрытый текст

Пусть в программе n операторов IF. На первом проходе составляем список строк (меток), выделив из них те, которые содержат операторы IF и END. Для IFов еще запоминаем, на какую метку осуществляется переход при выполнении условия. Затем выполняем серию прогонов: на первом прогоне считаем, что для всех IF условие НЕ выполняется. Для каждого последующего прогона "переключаем" условие на "истину" сначала для одного оператора (n прогонов), затем для двух операторов и т. д. (т. е. перебираем все возможные комбинации условий для IFов). Перед каждым прогоном сбрасываем список "посещенных" IF'ов. Прогон заканчивается по одному из двух условий: либо мы встречаем END, либо попадаем на ранее посещенный IF второй раз. При возникновении второго условия прекращаем работу и радостно рапортуем о зацикливании. Если это условие ни разу не возникло при переборе всех возможных комбинаций, значит, зацикливание исключено в принципе. Всего потребуется 2n прогонов.

 Отправлено: 25.10.10 05:39. Заголовок: Второй вариант работ..

Второй вариант работает быстрее, но, наверно, менее надежно.

Скрытый текст

Анализируем условные операторы. Если IF осуществляет переход вверх по цепочке и между строкой, на которую осуществлен переход, и осуществившим его условным оператором нет END, значит, в этом месте теоретически возможно зацикливание.

 Отправлено: 25.10.10 15:49. Заголовок: uux, всё можно сдела..

uux, всё можно сделать проще и быстрее))

ну, о простоте сложно судить, но общий принцип более быстрого (и при этом- надёжного) алгоритма можно описать коротко.

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

короч- твой вариант принят, но есть и другие))

--

и всё-таки твой надёжный вариант уж слишком долог- если учесть, что существует всего 4-ре начальных комбинации входных переменных => всего 4-ре варианта того, как прога будет исполняться с начала до конца- можно его ускорить.

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

 Отправлено: 26.10.10 00:36. Заголовок: qwerty пишет: прост..

qwerty пишет:

цитата:

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

=> длительность выполнения программы - не критерий ее простоты;).

Оффтоп: кто будет спорить, что пузырьковый алгоритм - самый простой способ сортировки списка?;)

 Отправлено: 26.10.10 00:39. Заголовок: Да, и еще вопрос: а ..

Да, и еще вопрос: по условию задачи у нас инструкция END в программе только одна или как в среднестатистическом квесте на урке?;)

 Отправлено: 26.10.10 09:20. Заголовок: uux пишет: => д..

uux пишет:

цитата:

=> длительность выполнения программы - не критерий ее простоты;).

именно. мысль была в том, что:

цитата:

ну, о простоте сложно судить, но общий принцип более быстрого (и при этом- надёжного) алгоритма можно описать коротко.

 Отправлено: 26.10.10 09:26. Заголовок: uux пишет: Да, и ещ..

uux пишет:

цитата:

Да, и еще вопрос: по условию задачи у нас инструкция END в программе только одна или как в среднестатистическом квесте на урке?;)

я так понимаю, что особой разницы нет. если придумаешь, как использовать ограничение на кол-во эндов, и если с одним эндом можно придумать интересный алгоритм- будут интересно посмотреть. а вообще это как бы оператор, и натыкать его можно сколько угодно. единственное ограничение, на то, что последняя строка- обязательно END, связано с тем, чтобы было проще отследить все варианты завершения проги: т е выполнение завершается однозначно только эндом.

ч/з три-четыре дня выложу мой вариант решения. правда, если объективно взглянуть, то преймущества разных алгоритмов довольно условны(как я уже говорил)- просто другой интересный вариант.

 Отправлено: 28.10.10 14:49. Заголовок: Вот мой вариант. Вро..

Вот мой вариант. Вроде должно работать, хотя тестовых прогонов я не делал по причине нехватки времени. Правда, я его приблизил-таки к некоему языку программирования;). Надеюсь, qwerty меня простит.

Курсивом выделены вставки, описывающие действия, код для которых писать было в лом.

Скрытый текст

ways=0 ; Количество веток выполнения, которые надо проверить :step_by_step ; процедура нормального построчного просмотра кода Построчный просмотр кода до тех пор, пока не встретим IF или END ; Встретили END -> проверяем, нужна ли дальнейшая проверка, и выходим из процедуры if (встретили END) then proc process_end & end ; Встретили условный оператор -> повышаем количество проверяемых веток на 2, обрабатываем, по мере обработки снижаем число проверенных веток if (встретили IF) then ways=ways+2 & proc begin_if & proc step_by_step & ways=ways-1 & proc exec_goto & proc step_by_step & proc end_if & ways=ways-1 ; Если мы здесь, значит, успешного завершения не произошло, но и условный оператор не зациклился; продолжаем просмотр после него goto step_by_step end :process_end ; Проверка завершения по END ; Непроверенных веток не осталось -> рапортуем об успешном завершении и заканчиваем работу if ways<=0 then pln НИШТЯК, ВСЁ ОК & forget_procs & end end :begin_if ; Начальная обработка, когда встретили условный оператор ; Если данный оператор уже обрабатывался в рамках данной ветки, произошло зацикливание if (Данный оператор уже есть в списке) then pln ЗАЦИКЛИВАНИЕ & forget_procs & end Добавляем оператор в список end :exec_goto ; Выполнение безусловного перехода Пропускаем строки до той, на которую происходит условный переход end :end_if ; Конечная обработка после завершения проверки очередного условного оператора Удаляем текущий условный оператор из списка посещенных end

Поскольку данный алгоритм не анализирует условия операторов и значения переменных, он будет несколько избыточен. Т. е. программа, которая успешно пройдет этот тест, не зациклится, однако для непрошедших возможны варианты. Скажем, следующая программа на практике зацикливаться не будет, но и тест не пройдет.

 
 10 A=0 
 20 IF A THEN GOTO 10 
 30 END 
 

 Отправлено: 28.10.10 21:58. Заголовок: uux пишет: зациклива..

uux пишет:

цитата:

зацикливаться не будет, но и тест не пройдет

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

uux, я вынужден перед тобой извиниться. видишь ли, к этой задаче не было решения. при обсуждении на одном форуме мне понравился такой вариант:

Скрытый текст

1) смотрим метку END. и смотрим, откуда она вызывается. 2)Далее смотрим те строки, откуда она вызывается. 3)Далле смотрим, откуда вызываются строки, вызвающие END. и т.д. 4)Если дошли до 1й строки (несколькими способами даже), то смотрим, при каких значениях А и В вызывается строка, вудущая к END. Если при всех, то проверяем, какие параметры вызвают вызов тртьей ступени и т.д. 5)Ели выходит, что END. вызывается при любых А и В, то све нормально, если мы к END можем прийти не всегда, то не все нормально

НО, попробовав, расписать его точно и чётко, вижу, что у него есть существенные недостатки.

щазз пишу свой вариант. а потом буду готов обсуждать всяческие недостатки.

 Отправлено: 28.10.10 22:12. Заголовок: в-общем, получается ..

в-общем, получается так:

Скрытый текст

придётся перебрать прогу при каждой комбинации значений переменных(в нашем случае их всего 4-ре), и для каждой отдельно выяснить, завершается когда-нибудь прога при таких начальных значениях переменных, или нет. как это сделать: просматриваем прогу, выполняя все положенные переходы(на след строку или по goto), и учитывая изменения значений переменных. и запоминаем, какие строки мы посещали, и какими были тогда значения переменных. и если мы попали на строку, на которой уже были, и при этом среди значений запомненных для неё переменных уже есть такие, с которыми мы на неё попали сейчас, то делаем вывод, что прога зацикливается. иначе- мы в конце концов доберёмся до какого-нибудь энда. да, и можно не стирать метки при прогоне следующей комбинации, а наоборот- если зациклились, то пометить все непомеченные комбинации на строках как 'плохие', если достигли энда- как 'хорошие'. и если при очередном прогоне попадаем на строку, в которой наши текущие значения переменных уже помечены, то мы сразу делаем соотв вывод, и не нужно гонять дальше по той же колее. ну, и ещё, конечно, если нашли одно зацикливание, то на этом можно бы и остановиться.

ну, вот так. проще не получается.

--

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

 Отправлено: 28.10.10 22:33. Заголовок: qwerty, по-моему, об..

qwerty, по-моему, оба решения, из двух твоих последних сообщений, можно объединить в нечто получше.

и ещё: если бы переменные были бы, например, целого типа (integer), то полный перебор был бы и долог и не нужен.

 Отправлено: 29.10.10 00:01. Заголовок: Ну, анализ значений ..

Ну, анализ значений переменных и условий перехода автоматом означает, что мы пишем интерпретатор к проге, да не простой, а с дополнительными сервисными функциями. Это будет явно решение "в лоб" и явно алгоритм простым не получится (результирующая программа окажется в разы сложнее анализируемой). Тогда уж проще будет действительно четыре раза запустить прогу со всеми возможными вариантами комбинаций начальных значений переменных и проверить, произошло ли зацикливание.

Есть еще такая светлая мысль: в принципе мой вариант решения можно доработать, чтобы он выявлял все потенциальные зацикливания (просто давал метки операторов IF, по которым получается замкнутая петля). Потом отдельно для этих замкнутых петель анализировать значения переменных, чтобы проверить, какие зацикливающие переходы никогда не наступят. Это, возможно, будет проще, хотя и вряд ли - мы все равно фактически реализуем полноценный интерпретатор, только применяем его в меньшем объеме - не ко всему коду, а только к сомнительным участкам.

И еще, хотел подискутировать;).

qwerty пишет:

цитата:

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

Абстрактную учебную задачу мой алгоритм, конечно, не решает. А теперь представь, что перед нами реальная задача по отладке программы. Попутно - как это всегда в жизни бывает - в программу вносятся изменения, в частности, автор экспериментирует с операторами присваивания. Подход с анализом условных переходов без привязки к конкретным проверяемым условиям (за конкретный алгоритм говорить не берусь, так как, повторюсь, он не тестировался) позволит автору выявить потенциально опасные участки, могущие вызвать зацикливания, и заставит его внимательнее отнестись к их модификации либо побудит его переписать их таким образом, чтобы зацикливания были исключены в принципе (ну, где это возможно, конечно). Формально решающий поставленную учебную задачу интерпретатор проги, привязывающийся к конкретным значениям переменных, в этом смысле будет иметь меньшую ценность, так как его, по-хорошему, надо будет запускать после каждого изменения программы. И, как верно заметил noname: а что мы будем делать с интерпретатором, если входные переменные примут ну хотя бы целый тип?

 Отправлено: 28.01.11 16:41. Заголовок: Про поезд. Сюжет отл..

Про поезд. Сюжет отличный, живо себе представляю. Делал бы так:
1. стою в вагоне - включил свет.
2. перешел на 1 вагон назад, выключил там свет
3. перешел на два вагона вперед (через вагон со светом), выключил там свет
4. перешел на три вагона назад (через вагон со светом), выключил там свет
5. перешел на четыре вагона вперед (через вагон со светом) и выключил свет там
6. продолжаю действовать аналогично

На телефоне закончились символы, см. следующий пост:

 Отправлено: 28.01.11 16:48. Заголовок: действуя таким образ..

действуя таким образом, если поезд на самом деле закольцован, двигаясь в какую-нибудь сторону, я выключу свет в первоначальном вагоне. Тогда возвращаясь в обратную сторону на один вагон дальше (количество вагонов я каждый раз благоразумно запоминал), я уже не обнаружу вагон со светом вообще и смогу с уверенностью сказать, что к этому моменту все вагоны остались без света. я зажгу свет в текущем вагоне и пойду вперед, считая вагоны, пока по кругу не вернусь к освещенному. это количество и будет решением...

 Отправлено: 14.05.15 15:04. Заголовок: Очередная задача: В..

Очередная задача:

В волшебной стране жили мужественные рыцари, свирепые драконы и прекрасные принцессы. Рыцари убивают драконов, драконы съедают принцесс, а принцессы изводят до смерти рыцарей. Всего было 100 рыцарей, 101 принцесса и 102 дракона. Древнее заклинание, наложенное на всех, запрещает убивать тех, кто погубил нечетное число жертв. В настоящее время в этой стране остался всего один житель. Кто это и почему?

 Отправлено: 14.05.15 15:36. Заголовок: qwerty, а теперь всё..

qwerty,
а теперь всё это в квест! :)

 Отправлено: 14.05.15 21:31. Заголовок: Это принцесса. Поч..