АвторСообщение
постоянный участник




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


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

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

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

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
Ответов - 23 , стр: 1 2 All [только новые]







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


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

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

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

Я вегетарианец не потому, что я люблю животных, просто я ненавижу растения. © А.Уитни Браун. Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


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


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

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


Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




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


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




Может я вернусь? Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 539
Зарегистрирован: 17.03.08
ссылка на сообщение  Отправлено: 23.10.10 01:10. Заголовок: Saruman пишет: 1. Сн..


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

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

I love Sinclair, DOS and URQ Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 375
Зарегистрирован: 20.01.06
ссылка на сообщение  Отправлено: 23.10.10 01:25. Заголовок: а как вам такая ЗАДА..


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

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

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

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

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

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

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

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 376
Зарегистрирован: 20.01.06
ссылка на сообщение  Отправлено: 23.10.10 01:27. Заголовок: qwerty пишет: напис..


qwerty пишет:

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

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


Сообщение: 306
Зарегистрирован: 13.03.07
ссылка на сообщение  Отправлено: 25.10.10 05:32. Заголовок: Прога сама по себе б..


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

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


Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


Сообщение: 307
Зарегистрирован: 13.03.07
ссылка на сообщение  Отправлено: 25.10.10 05:39. Заголовок: Второй вариант работ..


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

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


Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 541
Зарегистрирован: 17.03.08
ссылка на сообщение  Отправлено: 25.10.10 15:49. Заголовок: uux, всё можно сдела..


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

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

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

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

--

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

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

I love Sinclair, DOS and URQ Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


Сообщение: 308
Зарегистрирован: 13.03.07
ссылка на сообщение  Отправлено: 26.10.10 00:36. Заголовок: qwerty пишет: прост..


qwerty пишет:

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



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

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

Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


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


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

Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 377
Зарегистрирован: 20.01.06
ссылка на сообщение  Отправлено: 26.10.10 09:20. Заголовок: uux пишет: => д..


uux пишет:

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

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

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



мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




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


uux пишет:

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

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

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


Сообщение: 310
Зарегистрирован: 13.03.07
ссылка на сообщение  Отправлено: 28.10.10 14:49. Заголовок: Вот мой вариант. Вро..


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

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

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



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

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


Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 379
Зарегистрирован: 20.01.06
ссылка на сообщение  Отправлено: 28.10.10 21:58. Заголовок: uux пишет: зациклива..


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

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

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

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


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

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




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


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

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


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

--

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

мой дневник: http://ariom.ru/forum/t4591-0.html Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 542
Зарегистрирован: 17.03.08
ссылка на сообщение  Отправлено: 28.10.10 22:33. Заголовок: qwerty, по-моему, об..


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

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

I love Sinclair, DOS and URQ Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


Сообщение: 311
Зарегистрирован: 13.03.07
ссылка на сообщение  Отправлено: 29.10.10 00:01. Заголовок: Ну, анализ значений ..


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

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

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

qwerty пишет:

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



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




Спасибо: 0 
Профиль Цитата Ответить



Сообщение: 9
Зарегистрирован: 12.01.11
ссылка на сообщение  Отправлено: 28.01.11 16:41. Заголовок: Про поезд. Сюжет отл..


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

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

Спасибо: 0 
Профиль Цитата Ответить



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


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

Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 454
Зарегистрирован: 20.01.06
ссылка на сообщение  Отправлено: 14.05.15 15:04. Заголовок: Очередная задача: В..


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

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

Спасибо: 0 
Профиль Цитата Ответить
постоянный участник




Сообщение: 160
Зарегистрирован: 06.11.08
ссылка на сообщение  Отправлено: 14.05.15 15:36. Заголовок: qwerty, а теперь всё..


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


Я за мир во всём мире. За отдельно взятые инопланетные цивилизации ответственности не несу... Спасибо: 0 
Профиль Цитата Ответить
постоянный участник


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


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


Спасибо: 0 
Профиль Цитата Ответить
Ответов - 23 , стр: 1 2 All [только новые]
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 209
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет