Автор Тема: Выход из цикла или смерть Кощея  (Прочитано 92087 раз)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Выход из цикла или смерть Кощея
« : Январь 10, 2013, 11:42:46 pm »
Этот пост адресован тем, кто считает наличие exit/break внутри цикла плохим тоном. В идеале, тем, кто может показать, чем это плохо, но где ж таких возьмешь :)
Те, кто лепит exit/break в теле цикла без малейших колебаний, могут дальше не читать.

Как известно, смерть Кощея находится в игле, игла в яйце, яйцо в утке, утка в зайце, заяц в сундуке. Сундуков у нас много (массив), а задачи рассмотрим две.
1. Найти первую смерть Кощея, т. е., иглу (считаем, что таких сундуков может быть много).
2. Найти первый сундук, в котором нет смерти – там чего-нибудь не хватает.

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

При данных ограничениях мне приходят в голову только решения, использующие exit/break  :(
Некрасиво, но что поделаешь…
Вот решения на псевдокоде, неотличимом от C#.




Я оцениваю ситуацию как неудовлетворительную. С одной стороны, задача банально-тривиальная. C другой стороны, я вынужден морщиться и идти на компромисс.
Все дело в недостатке выразительных средств.

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

Не следует ограничивать свою фантазию, речь идет, скорее, о языке мышления.
« Последнее редактирование: Январь 10, 2013, 11:44:49 pm от Peter Almazov »

DddIzer

  • Гость
Re: Выход из цикла или смерть Кощея
« Ответ #1 : Январь 11, 2013, 01:51:42 am »
Вопрос-1я задача..- она всегда имеет решение (Смерть находится в по крайней мере 1 сундуке)?

DddIzer

  • Гость
Re: Выход из цикла или смерть Кощея
« Ответ #2 : Январь 11, 2013, 02:07:18 am »
Если это так... то введя логическую переменную  и  используя цикл do while  можно  избавиться
1. От уродливого заголовка цикла
2. Брейка
3. Последнего внутреннего условного оператора - заменив его на присваивание логической переменной выражения  (игла  != null)

akron1

  • Jr. Member
  • **
  • Сообщений: 76
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #3 : Январь 11, 2013, 03:47:18 am »
вместо break; -- i = сундуки.Length;

akron1

  • Jr. Member
  • **
  • Сообщений: 76
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #4 : Январь 11, 2013, 03:51:29 am »
вместо break; -- i = сундуки.Length;

Упс, виноват, не пройдет. Не сохраняется индекс
« Последнее редактирование: Январь 11, 2013, 03:53:44 am от akron1 »

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #5 : Январь 11, 2013, 05:02:34 am »
Печенкой чую, что тут хорошо прокатило бы что-то вроде монады Maybe.
Y = λf.(λx.f (x x)) (λx.f (x x))

X512

  • Newbie
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #6 : Январь 11, 2013, 05:11:01 am »
Это же банальный линейный поиск:
i := 0;
WHILE (i < LEN(сундуки)) & ((ЗАЯЦ(сундуки[i]) = NIL) OR (УТКА(ЗАЯЦ(сундуки[i])) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки[i]))) = NIL)) DO INC(i) END
Короткое решение безо всяких break'ов.

albobin

  • Full Member
  • ***
  • Сообщений: 198
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #7 : Январь 11, 2013, 05:12:48 am »
1. Разрешить передачу null  в параметре функций ЗАЯЦ, УТКА ...  (будет возвращать тоже null)
2. использовать цикл repeat until

Тогда нет нужды в цепочке if-ов (как "бонус")

Valery

  • Full Member
  • ***
  • Сообщений: 101
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #8 : Январь 11, 2013, 05:17:09 am »
Правильное решение у x512.
Единственное, что надо добавить - логическую переменную. Чтобы не писать длинные условия.
Логическая переменная покажет еще и общность обоих циклов.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #9 : Январь 11, 2013, 05:19:56 am »
Правильное решение у x512.
Единственное, что надо добавить - логическую переменную. Чтобы не писать длинные условия.
Логическая переменная покажет еще и общность обоих циклов.
Нет. Потому, что в условии задачи сказано:
Цитировать
разборка предметов стоит дорого
Y = λf.(λx.f (x x)) (λx.f (x x))

Valery

  • Full Member
  • ***
  • Сообщений: 101
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #10 : Январь 11, 2013, 05:22:48 am »
Дык разборка - она хоть в теле разборка, хоть в условии - та же разборка. Или имеется ввиду какая-то другая разборка?

X512

  • Newbie
  • *
  • Сообщений: 45
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #11 : Январь 11, 2013, 05:29:22 am »
На Си можно избежать дублирования кода пользуясь тем фактом, что оператор присваивания возвращает значение:
i = 0;
while ((i < колВоСундуков) && (
   !(заяц = ЗАЯЦ(сундуки[i]))
|| !(утка = УТКА(заяц)))
|| !(яйцо = ЯЙЦО(утка))
|| !(игла = ИГЛА(яйцо))
)) ++i;
PS: прошлый раз не заметил, что там ещё и игла есть...

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #12 : Январь 11, 2013, 05:32:05 am »
Дык разборка - она хоть в теле разборка, хоть в условии - та же разборка. Или имеется ввиду какая-то другая разборка?
Во-первых в решении X512 из сундука заяц извлекается по нескольку раз за итерацию цикла, а в предложенном референсном решении только один раз.

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

PS. Одно из основных умений программиста (да и математика тоже, и физика) - уметь полностью читать и понимать постановку задачи. Увы, это умение похоже довольно редкое.
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Выход из цикла или смерть Кощея
« Ответ #13 : Январь 11, 2013, 05:33:46 am »
На Си можно избежать дублирования кода пользуясь тем фактом, что оператор присваивания возвращает значение:
i = 0;
while ((i < колВоСундуков) && (
   !(заяц = ЗАЯЦ(сундуки[i]))
|| !(утка = УТКА(заяц)))
|| !(яйцо = ЯЙЦО(утка))
|| !(игла = ИГЛА(яйцо))
)) ++i;
PS: прошлый раз не заметил, что там ещё и игла есть...
Да, вот это уже похоже на правду.
Y = λf.(λx.f (x x)) (λx.f (x x))

DddIzer

  • Гость
Re: Выход из цикла или смерть Кощея
« Ответ #14 : Январь 11, 2013, 05:47:41 am »
но языкозависимо... что не есть гуд