Oberon space
General Category => Общий раздел => Тема начата: Peter Almazov от Январь 10, 2013, 11:42:46 pm
-
Этот пост адресован тем, кто считает наличие exit/break внутри цикла плохим тоном. В идеале, тем, кто может показать, чем это плохо, но где ж таких возьмешь :)
Те, кто лепит exit/break в теле цикла без малейших колебаний, могут дальше не читать.
Как известно, смерть Кощея находится в игле, игла в яйце, яйцо в утке, утка в зайце, заяц в сундуке. Сундуков у нас много (массив), а задачи рассмотрим две.
1. Найти первую смерть Кощея, т. е., иглу (считаем, что таких сундуков может быть много).
2. Найти первый сундук, в котором нет смерти – там чего-нибудь не хватает.
Ограничения такие: разборка предметов стоит дорого, и после выхода из цикла недостаточно иметь индекс сундука. Нужно сохранить промежуточные переменные, содержавшие смерть. Использовать функцию, чтобы упрятать разборку, недопустимо, по причине снижения эффективности.
Кстати, басни про преждевременную оптимизацию здесь неуместны еще и потому, что вариант с функцией безобразен (на Обероне и пр.). Она по-любому будет иметь побочные эффекты (менять внешние переменные или параметры) и будет не строгой функцией, а черт знает чем.
Строгая функция могла бы возвращать кортеж, содержащий булев результат и запчасти разборки, но я плохо представляю, как запихнуть все это в заголовок цикла. Этот вариант можно привести для интереса, но по эффективности он не проходит.
При данных ограничениях мне приходят в голову только решения, использующие exit/break :(
Некрасиво, но что поделаешь…
Вот решения на псевдокоде, неотличимом от C#.
(http://s018.radikal.ru/i516/1301/11/09acc354c0a9.png)
(http://s018.radikal.ru/i502/1301/10/3cb7edb8ee8a.png)
Я оцениваю ситуацию как неудовлетворительную. С одной стороны, задача банально-тривиальная. C другой стороны, я вынужден морщиться и идти на компромисс.
Все дело в недостатке выразительных средств.
Что предлагается сделать.
Изобрести (или вспомнить где-то реализованную) конструкцию для цикла, которая позволяла бы записать решение без компромиссов, образцово-показательно, эффективно.
ИКР, короче. Идеальный конечный результат.
Не следует ограничивать свою фантазию, речь идет, скорее, о языке мышления.
-
Вопрос-1я задача..- она всегда имеет решение (Смерть находится в по крайней мере 1 сундуке)?
-
Если это так... то введя логическую переменную и используя цикл do while можно избавиться
1. От уродливого заголовка цикла
2. Брейка
3. Последнего внутреннего условного оператора - заменив его на присваивание логической переменной выражения (игла != null)
-
вместо break; -- i = сундуки.Length;
-
вместо break; -- i = сундуки.Length;
Упс, виноват, не пройдет. Не сохраняется индекс
-
Печенкой чую, что тут хорошо прокатило бы что-то вроде монады Maybe.
-
Это же банальный линейный поиск:
i := 0;
WHILE (i < LEN(сундуки)) & ((ЗАЯЦ(сундуки[i]) = NIL) OR (УТКА(ЗАЯЦ(сундуки[i])) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки[i]))) = NIL)) DO INC(i) END
Короткое решение безо всяких break'ов.
-
1. Разрешить передачу null в параметре функций ЗАЯЦ, УТКА ... (будет возвращать тоже null)
2. использовать цикл repeat until
Тогда нет нужды в цепочке if-ов (как "бонус")
-
Правильное решение у x512.
Единственное, что надо добавить - логическую переменную. Чтобы не писать длинные условия.
Логическая переменная покажет еще и общность обоих циклов.
-
Правильное решение у x512.
Единственное, что надо добавить - логическую переменную. Чтобы не писать длинные условия.
Логическая переменная покажет еще и общность обоих циклов.
Нет. Потому, что в условии задачи сказано:
разборка предметов стоит дорого
-
Дык разборка - она хоть в теле разборка, хоть в условии - та же разборка. Или имеется ввиду какая-то другая разборка?
-
На Си можно избежать дублирования кода пользуясь тем фактом, что оператор присваивания возвращает значение:
i = 0;
while ((i < колВоСундуков) && (
!(заяц = ЗАЯЦ(сундуки[i]))
|| !(утка = УТКА(заяц)))
|| !(яйцо = ЯЙЦО(утка))
|| !(игла = ИГЛА(яйцо))
)) ++i;
PS: прошлый раз не заметил, что там ещё и игла есть...
-
Дык разборка - она хоть в теле разборка, хоть в условии - та же разборка. Или имеется ввиду какая-то другая разборка?
Во-первых в решении X512 из сундука заяц извлекается по нескольку раз за итерацию цикла, а в предложенном референсном решении только один раз.
Во-вторых после выхода из цикла все должно остаться в разобраном состоянии, что мы и видим в референсном решении, в решении же X512 нам предлагается заново по индексу разбирать сундук.
Ограничения такие: разборка предметов стоит дорого, и после выхода из цикла недостаточно иметь индекс сундука. Нужно сохранить промежуточные переменные, содержавшие смерть.
PS. Одно из основных умений программиста (да и математика тоже, и физика) - уметь полностью читать и понимать постановку задачи. Увы, это умение похоже довольно редкое.
-
На Си можно избежать дублирования кода пользуясь тем фактом, что оператор присваивания возвращает значение:
i = 0;
while ((i < колВоСундуков) && (
!(заяц = ЗАЯЦ(сундуки[i]))
|| !(утка = УТКА(заяц)))
|| !(яйцо = ЯЙЦО(утка))
|| !(игла = ИГЛА(яйцо))
)) ++i;
PS: прошлый раз не заметил, что там ещё и игла есть...
Да, вот это уже похоже на правду.
-
но языкозависимо... что не есть гуд
-
i = 0;
заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц));
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
condition = (!(заяц = null)|| !(утка = null)|| !(яйцо = null)|| !(игла = null));
while ((i < колВоСундуков) && condition)
{++i;
заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц);
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
condition = (!(заяц = null)|| !(утка = null)|| !(яйцо = null)|| !(игла = null));
}
И что?
-
Зачем так длинно, достаточно только иглу сравнить
-
i = 0;
заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц));
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
condition = (!(заяц = null)|| !(утка = null)|| !(яйцо = null)|| !(игла = null));
while ((i < колВоСундуков) && condition)
{++i;
заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц);
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
condition = (!(заяц = null)|| !(утка = null)|| !(яйцо = null)|| !(игла = null));
}
И что?
Подозреваю, что например "утка = УТКА(заяц);" если заяц==null, не приведет ни к чему хорошему.
-
Зачем так длинно, достаточно только иглу сравнить
только в том случае если есть гарантированная смерть
-
1. Разрешить передачу null в параметре функций ЗАЯЦ, УТКА ... (будет возвращать тоже null)
-
1. Разрешить передачу null в параметре функций ЗАЯЦ, УТКА ... (будет возвращать тоже null)
так это само-собой. я говорю про ( i < колВоСундуков) - в различных возможных ипостасях
-
Печенкой чую, что тут хорошо прокатило бы что-то вроде монады Maybe.
По сути вот она:
Это же банальный линейный поиск:
i := 0;
WHILE (i < LEN(сундуки)) & ((ЗАЯЦ(сундуки[i]) = NIL) OR (УТКА(ЗАЯЦ(сундуки[i])) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки[i]))) = NIL)) DO INC(i) ENDКороткое решение безо всяких break'ов.
;D
-
Печенкой чую, что тут хорошо прокатило бы что-то вроде монады Maybe.
По сути вот она:
Это же банальный линейный поиск:
i := 0;
WHILE (i < LEN(сундуки)) & ((ЗАЯЦ(сундуки[i]) = NIL) OR (УТКА(ЗАЯЦ(сундуки[i])) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки[i]))) = NIL)) DO INC(i) ENDКороткое решение безо всяких break'ов.
;D
Пардон, нет, это на монаду maybe не годится из-за ((ЗАЯЦ(сундуки) = NIL) OR (УТКА(ЗАЯЦ(сундуки)) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки))) = NIL)
-
На Си можно избежать дублирования кода пользуясь тем фактом, что оператор присваивания возвращает значение:
i = 0;
while ((i < колВоСундуков) && (
!(заяц = ЗАЯЦ(сундуки[i]))
|| !(утка = УТКА(заяц)))
|| !(яйцо = ЯЙЦО(утка))
|| !(игла = ИГЛА(яйцо))
)) ++i;
PS: прошлый раз не заметил, что там ещё и игла есть...
Вот, а вот это уже вполне тянет на суть монады Maybe!
-
1. Разрешить передачу null в параметре функций ЗАЯЦ, УТКА ... (будет возвращать тоже null)
так это само-собой. я говорю про ( i < колВоСундуков) - в различных возможных ипостасях
Ну, тогда надо тот код из http://oberspace.dyndns.org/index.php/topic,425.msg13051.html#msg13051
лучше упростить
i = 0;
condition =false ;
while ((i < колВоСундуков) && (! condition)
{ заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц);
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
condition = игла != null;
i++;
}
Здесь ищем иглу, а при condition = игла == null ищем недостачу
-
эта форма мне нравится...-побочных эффектов "по-любому возникающих" я не вижу...
-
точнее - если можно пожертвовать в угоду наглядности мизерной потерей быстродействия на 4 безусловных вызова функций то ваш вариант, если нет - свой :)
-
точнее - если можно пожертвовать в угоду наглядности мизерной потерей быстродействия на 4 безусловных вызова функций то ваш вариант, если нет - свой :)
Да он как бы и не мой :) Я предполагал без переменной и repeat-until ну или do-while как у Вас в http://oberspace.dyndns.org/index.php/topic,425.msg13034.html#msg13034
Хотя просто while с переменной, наверное, всё же лучше.
PS.
Навесить ифы можно во всех вариантах.
-
Что предлагается сделать.
Изобрести (или вспомнить где-то реализованную) конструкцию для цикла, которая позволяла бы записать решение без компромиссов, образцово-показательно, эффективно.
ИКР, короче. Идеальный конечный результат.
Не следует ограничивать свою фантазию, речь идет, скорее, о языке мышления.
Ну вот мой вариант:
// Найти первый комплект с иглой
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) continue;
утка = заяц.ИзвлечьУтку(); if (утка == null) continue;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) continue;
игла = яйцо.ИзвлечьУтку(); if (игла == null) break;
}// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) break;
утка = заяц.ИзвлечьУтку(); if (утка == null) break;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) break;
игла = яйцо.ИзвлечьУтку(); if (игла == null) break;
}
-
Пётр Алмазов призывал: "Не следует ограничивать свою фантазию".
:)
вариант без переменной condition
ищем нормальную иглу
i = 0;
игла=null ;
while (i < колВоСундуков) && (игла == null)
{ заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц);
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
i++;
}
ищем недостачу
i = 0;
игла=игла_без_йаду ;
while (i < колВоСундуков) && (игла != null)
{ заяц = ЗАЯЦ(сундуки[i]);
утка = УТКА(заяц);
яйцо = ЯЙЦО(утка);
игла = ИГЛА(яйцо);
i++;
}
-
Этот пост адресован тем, кто считает наличие exit/break внутри цикла плохим тоном. В идеале, тем, кто может показать, чем это плохо, но где ж таких возьмешь :)
Чем плохо сказать-то можно. Представьте себе цикл на 300 строчек с глубоко вложенными if, внутри которых иногда есть break|continue|return (цикл писался и дописывался студентами года два). Хочется переписать его разбив на процедуры, но из-за глубоко вложенных break|continue|return эта задачка не так то уж проста.
Я бы так написал:
Поиск первого сундука с иглой:
if (сундуки.Length > 0)
{
игла = null;
int i = 0;
do
{
заяц = ЗАЯЦ(сундуки[i++]);
if (заяц != null)
{
утка = УТКА(заяц);
if (утка != null)
{
яйцо = ЯЙЦО(утка);
if (яйцо != null)
{
игла = ИГЛА(яйцо);
}
}
}
}
while ((i < сундуки.Length) && (игла == null));
if (игла != null)
{
// нашли первый сундук с иглой
сундук = сундуки[i - 1];
//...
}
}
Поиск первого сундука без иглы:
if (сундуки.Length > 0)
{
игла = null;
int i = 0;
do
{
заяц = ЗАЯЦ(сундуки[i++]);
if (заяц != null)
{
утка = УТКА(заяц);
if (утка != null)
{
яйцо = ЯЙЦО(утка);
if (яйцо != null)
{
игла = ИГЛА(яйцо);
}
}
}
}
while ((i < сундуки.Length) && (игла != null));
if (игла == null)
{
// нашли первый сундук без иглы
сундук = сундуки[i - 1];
//...
}
}
-
добавим чуть-чуть "грязи" ))
TYPE
Element = OBJECT( List.Element )
data: Element;
PROCEDURE[EXTENSIBLE] UnpackTo( VAR to: Element ): BOOLEAN =
VAR
res: BOOLEAN;
BEGIN
res := SELF.data # NIL;
to := SELF.data;
END UnPack;
END Element;
Смерть = OBJECT ( Element )
END Смерть;
Игла = OBJECT ( Element )
PROCEDURE UnpackTo( to: Смерть ): BOOLEAN = INHERITED;
END Игла;
Яйцо = OBJECT ( Element )
PROCEDURE UnpackTo( to: Игла ): BOOLEAN = INHERITED;
END Яйцо;
Утка = OBJECT ( Element )
PROCEDURE UnpackTo( to: Яйцо ): BOOLEAN = INHERITED;
END Утка;
Заяц = OBJECT ( Element )
PROCEDURE UnpackTo( to: Утка ): BOOLEAN = INHERITED;
END Утка;
Сундук = OBJECT ( Element )
PROCEDURE UnpackTo( to: Заяц ): BOOLEAN = INHERITED;
END Сундук;
VAR
сундук, заяц, утка, яйцо, игла, смерть : Element := NIL;
list := List.Ref;
....
(* приск первого сундука с иглой *)
WHILE list.HasMoreElements() AND смерть = NIL DO
сундук := list.GetNext();
IF сундук.UnpackTo( заяц ) AND
заяц .UnpackTo( утка ) AND
утка .UnpackTo( яйцо ) AND
яйцо .UnpackTo( игла ) AND
игла .UnpackTo( смерт ) THEN
Log.String("капец Кащею");
END;
END;
-
Чтобы вложенные предметы были доступны по очереди, сделал их через вложенные ссылки.
У меня получилось так.
Сам алгоритм:
existSearchDeath := FALSE; (* смерть Кощея пока не найдена *)
WHILE
(i < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchDeath (* проверка, что смерть Кощея еще не найдена *)
DO
IF
(ds.сhests^[i].hare # NIL) (* проверка, что в сундуке есть заяц *)
& (ds.сhests^[i].hare^.duck # NIL) (* проверка, что в зайце есть утка *)
& (ds.сhests^[i].hare^.duck^.egg # NIL) (* проверка, что в утке есть яйцо *)
& (ds.сhests^[i].hare^.duck^.egg^.needle # NIL) (* проверка, что в яйце есть игла *)
THEN
existSearchDeath := TRUE (* смерть Кощея найдена *)
END; (* проверка наличия смерти Кощея в сундуке *)
INC(i) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
END
Модуль поиска:
MODULE searchdeathscrag;
IMPORT
StdLog, ds := deathscrag;
VAR
i-: INTEGER;
(* номер первого еще не просмотренного сундука, если такой есть *)
(* (i >= 0) & (i <= n) *)
existSearchDeath-: BOOLEAN;
(* existSearchDeath = (следующая смерть Кощея найдена при последнем поиске) *)
(* existSearchDeath -> ((номер последнего найденного сундука со смертью Кощея) = i-1) *)
(* ~existSearchDeath -> (i = n) *)
(* (i = 0) -> ~existDeath *)
k: LONGINT;
(* номер версии набора сундуков, в котором идет поиск *)
PROCEDURE ClearSearch*;
BEGIN
i := 0; (* переход к первому сундуку *)
existSearchDeath := FALSE; (* смерть Кощея не найдена *)
k := ds.k (* сохранение версии набора сундуков *)
END ClearSearch; (* очистка поиска *)
PROCEDURE SearchDeath*(*0:0*);
BEGIN
IF k # ds.k THEN (* проверка версии набора сундуков *)
StdLog.Ln;
StdLog.String("дальнейший поиск невозможен, так как массив сундуков был изменен");
StdLog.Ln;
HALT(0)
END(*0:0*); (* прерывание поиска если номер версии набора сундуков устарел *)
existSearchDeath := FALSE; (* смерть Кощея пока не найдена *)
WHILE
(i < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchDeath (* проверка, что смерть Кощея еще не найдена *)
DO
IF
(ds.сhests^[i].hare # NIL) (* проверка, что в сундуке есть заяц *)
& (ds.сhests^[i].hare^.duck # NIL) (* проверка, что в зайце есть утка *)
& (ds.сhests^[i].hare^.duck^.egg # NIL) (* проверка, что в утке есть яйцо *)
& (ds.сhests^[i].hare^.duck^.egg^.needle # NIL) (* проверка, что в яйце есть игла *)
THEN
existSearchDeath := TRUE (* смерть Кощея найдена *)
END; (* проверка наличия смерти Кощея в сундуке *)
INC(i) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
END
END(*0:0*) SearchDeath; (* поиск смерти Кощея *)
(*
existDeath :=
(ds.chests^[i].hare # NIL) (* проверка, что в сундуке есть заяц *)
& (ds.chests^[i].hare^.duck # NIL) (* проверка, что в зайце есть утка *)
& (ds.chests^[i].hare^.duck^.egg # NIL) (* проверка, что в утке есть яйцо *)
& (ds.chests^[i].hare^.duck^.egg^.needle # NIL) (* проверка, что в яйце есть игла *)
(* проверка наличия смерти Кощея в сундуке *)
*)
BEGIN
ClearSearch (* очистка поиска *)
END searchdeathscrag.
И модуль Кощея:
MODULE deathscrag;
IMPORT
StdLog;
CONST
noExistDeath = TRUE;
(* разрешено не иметь ни одного сундука со смертью Кощея, если число сундуков не нуль *)
multyExistDeath = TRUE;
(* разрешено иметь несколько сундуков со смертью Кощея *)
TYPE TypeChests* =
POINTER TO
ARRAY OF
RECORD
hare*: POINTER TO
RECORD
duck*: POINTER TO
RECORD
egg*: POINTER TO
RECORD
needle*: POINTER TO
RECORD
END (* тип иглы *)
END (* тип яйца *)
END (* тип утки *)
END (* тип зайца *)
END; (* тип сундука *)
(* тип массива сундуков *)
(* тип набора сундуков *)
VAR
сhests-: TypeChests;
(* набор сундуков *)
n-: INTEGER;
(* число сундуков *)
(* (chests # NIL) -> (n = LEN(chests^)) *)
(* (chests = NIL) -> (n = 0) *)
k-: LONGINT;
(* номер версии набора сундуков *)
PROCEDURE IncK (*0:0*);
BEGIN
IF k < MAX(LONGINT) THEN
INC(k) (* переход к номеру новой версии набора сундуков *)
ELSE
StdLog.String("дальнейшие версии набора сундуков невозможны, перезагрузите модули");
HALT(0)
END(*0:0*)
END(*0:0*) IncK; (* установка нового номера версии набора сундуков *)
PROCEDURE ClearChests* (*0:0*);
BEGIN
n := 0; (* количество сундуков в новом пустом наборе *)
IncK(*0:0*); (* переход к номеру новой версии набора сундуков *)
сhests := NIL; (* создание пустого массива сундуков *)
END(*0:0*) ClearChests; (* установка пустого массива сундуков *)
(* forall j (0 <= j <= LEN(a))(0 <= a[j] <= 4) *)
(* noExistDeath OR (exist j (0 <= j <= LEN(a))(a[j] = 4)) *)
(* multyExistDeath OR
(forall j1, j2 (0 <= j1,j2 <= LEN(a))((a[j1] = 4) & (a[j2] = 4) -> (j1 = j2))) *)
PROCEDURE NewChests* (IN a: ARRAY OF BYTE; OUT b: BOOLEAN)(*0:0*);
VAR
bNo, bMulty: BOOLEAN;
j: INTEGER;
(* номер первого сундука с непрописанным содержимым, если такой есть *)
BEGIN
bNo := FALSE; (* сундука со смертью Кощея пока не обнаружено *)
bMulty := FALSE; (* несколько сундуков со смертью Кощея пока не обнаружено *)
b := TRUE; (* ошибок данных пока не обнаружено *)
n := LEN(a); (* новое количество сундуков в наборе; LEN(a) > 0 *)
NEW(сhests, n); (* создание нового набора сундуков *)
j := 0; (* переход к первому сундуку с непрописанным содержимым,
если такой есть *)
WHILE
(j < n) (* проверка, что сундуки с непрописанным содержимым еще остались *)
& b (* проверка, что ошибок данных пока не обнаружено *)
DO
IF a[j] = 0 THEN
сhests^[j].hare := NIL (* сундук остается пустым *)
ELSE
NEW(сhests^[j].hare); (* помещение зайца в сундук *)
IF a[j] = 1 THEN
сhests^[j].hare^.duck := NIL (* зайц остается пустым *)
ELSE
NEW(сhests^[j].hare^.duck); (* помещение утки в зайца *)
IF a[j] = 2 THEN
сhests^[j].hare^.duck^.egg := NIL (* утка остается пустой *)
ELSE
NEW(сhests^[j].hare^.duck^.egg); (* помещение яйца в утку *)
IF a[j] = 3 THEN
сhests^[j].hare^.duck^.egg^.needle := NIL (* яйцо остается пустым *)
ELSIF a[j] = 4 THEN
NEW(сhests^[j].hare^.duck^.egg^.needle); (* помещение иглы в яйцо *)
IF ~bNo THEN (* проверка, что сундука со смертью Кощея еще не обнаружено *)
bNo := TRUE (* первый сундук со смертью Кощея обнаружен *)
ELSIF ~bMulty THEN (* проверка, что только один сундук со смертью Кощея
обнаружен *)
bMulty := TRUE; (* несколько сундуков со смертью Кощея обнаружено *)
b := multyExistDeath (* ошибка данных обнаружена, если не разрешено иметь
несколько сундуков со смертью Кощея *)
END
ELSE
b := FALSE (* ошибка данных обнаружена *)
END
END
END
END; (* установка содержимого j-го сундука,
либо прекращение установки при ошибке данных *)
INC(j) (* переход к следующему сундуку с непрописанным содержимым,
если такой есть *)
END;
b := b & (noExistDeath OR bNo); (* ошибка данных обнаружена, если не имеется ни одного
сундука со смертью Кощея и это не разрешено *)
IF ~b THEN
ClearChests(*0:0*) (* создание пустого массива сундуков при наличии ошибки данных *)
ELSE
IncK(*0:0*) (* переход к номеру новой версии набора сундуков *)
END(*0:0*)
END(*0:0*) NewChests; (* создание нового массива сундуков с новым содержимым *)
(* b -> (в массиве 'a' ошибок данных нет,
новый массив сундуков установлен согласно содержимому массива 'a') *)
(* ~b -> (в массиве 'a' есть ошибки данных, новый массив сундуков пустой) *)
BEGIN
k := -1; (* номер версии, предшествующий версии первого набора сундуков *)
ClearChests (* установка первого массива сундуков *)
END deathscrag.
Перевод:
смерть кощей сундук заяц утка яйцо игла
death scrag chest hare duck egg needle
-
Сундуков много, операция разборки дорогая, но вот после цикла таких операций одну такую лишнюю позволить - ни-ни.
Использовать функцию, чтобы упрятать разборку, недопустимо, по причине снижения эффективности.
Какое снижение эффективности? При росте тяжести операции разборки, резко падают затраты на любые обёртки. В ряде языков на такой ужасный случай есть inline.
Чтобы попусту не ворчать:
i := 0;
WHILE
(i < LEN(сундуки)) &
(
~ЗАЯЦ(сундуки[i], заяц) OR
~УТКА(заяц, утка) OR
~ЯЙЦО(утка, яйцо)
)
DO
INC(i);
END;
Мои функции обычно возвращают только BOOLEAN, а результат в виде OUT-параметров. Так что сложностей не возникает.
-
WHILE list.HasMoreElements() AND смерть = NIL DO
сундук := list.GetNext();
IF сундук.UnpackTo( заяц ) AND
заяц .UnpackTo( утка ) AND
утка .UnpackTo( яйцо ) AND
яйцо .UnpackTo( игла ) AND
игла .UnpackTo( смерт ) THEN
Log.String("капец Кащею");
END;
END;
+1. Близко к идеальному. Смотришь и всё сразу понятно.
-
добавим чуть-чуть "грязи" ))
...
игла .UnpackTo( смерт ) THEN
...
А разве не в каждой игле лежит смерть? Что-то этот уровень вложенности я пропустил.
Если еще искать сундук без смерти Кощея, то будет такой алгоритм:
WHILE
(j < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchNoDeath (* проверка, что сундук без смерти Кощея еще не найден *)
DO
IF
(ds.сhests^[j].hare = NIL) (* проверка, что в сундуке есть заяц *)
OR (ds.сhests^[j].hare^.duck = NIL) (* проверка, что в зайце есть утка *)
OR (ds.сhests^[j].hare^.duck^.egg = NIL) (* проверка, что в утке есть яйцо *)
OR (ds.сhests^[j].hare^.duck^.egg^.needle = NIL) (* проверка, что в яйце есть игла *)
THEN
existSearchNoDeath := TRUE (* сундук без смерти Кощея найдена *)
END; (* проверка отсутствия смерти Кощея в сундуке *)
INC(j) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
END
(*
existSearchNoDeath :=
(ds.chests^[j].hare = NIL) (* проверка, что в сундуке есть заяц *)
OR (ds.chests^[j].hare^.duck = NIL) (* проверка, что в зайце есть утка *)
OR (ds.chests^[j].hare^.duck^.egg = NIL) (* проверка, что в утке есть яйцо *)
OR (ds.chests^[j].hare^.duck^.egg^.needle = NIL) (* проверка, что в яйце есть игла *)
(* проверка отсутствия смерти Кощея в сундуке *)
*)
А в мой модуль поиска searchdeathscrag нужно добавить:
VAR
j-: INTEGER;
(* номер первого еще не просмотренного сундука, если такой есть *)
(* (j >= 0) & (j <= n) *)
existSearchNoDeath-: BOOLEAN;
(* existSearchNoDeath = (следующий сундук без смерти Кощея найден при последнем поиске) *)
(* existSearchNoDeath -> ((номер последнего найденного сундука без смерти Кощея) = j-1) *)
(* ~existSearchNoDeath -> (j = n) *)
(* (j = 0) -> ~existDeath *)
l: LONGINT;
(* номер версии набора сундуков, в котором идет поиск сундука без смерти Кощея *)
PROCEDURE ClearSearchNoDeath*;
BEGIN
j := 0; (* переход к первому сундуку *)
existSearchNoDeath := FALSE; (* сундук без смерти Кощея не найден *)
l := ds.k (* сохранение версии набора сундуков *)
END ClearSearchNoDeath; (* очистка поиска *)
PROCEDURE SearchNoDeath*(*0:0*);
BEGIN
IF k # ds.k THEN (* проверка версии набора сундуков *)
StdLog.Ln;
StdLog.String("дальнейший поиск невозможен, так как массив сундуков был изменен");
StdLog.Ln;
HALT(0)
END(*0:0*); (* прерывание поиска если номер версии набора сундуков устарел *)
existSearchNoDeath := FALSE; (* сундук без смерти Кощея пока не найден *)
WHILE
(j < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchNoDeath (* проверка, что сундук без смерти Кощея еще не найден *)
DO
IF
(ds.сhests^[j].hare = NIL) (* проверка, что в сундуке есть заяц *)
OR (ds.сhests^[j].hare^.duck = NIL) (* проверка, что в зайце есть утка *)
OR (ds.сhests^[j].hare^.duck^.egg = NIL) (* проверка, что в утке есть яйцо *)
OR (ds.сhests^[j].hare^.duck^.egg^.needle = NIL) (* проверка, что в яйце есть игла *)
THEN
existSearchNoDeath := TRUE (* сундук без смерти Кощея найден *)
END; (* проверка отсутствия смерти Кощея в сундуке *)
INC(j) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
END
END(*0:0*) SearchNoDeath; (* поиск сундука без смерти Кощея *)
(*
existSearchNoDeath :=
(ds.chests^[j].hare = NIL) (* проверка, что в сундуке есть заяц *)
OR (ds.chests^[j].hare^.duck = NIL) (* проверка, что в зайце есть утка *)
OR (ds.chests^[j].hare^.duck^.egg = NIL) (* проверка, что в утке есть яйцо *)
OR (ds.chests^[j].hare^.duck^.egg^.needle = NIL) (* проверка, что в яйце есть игла *)
(* проверка отсутствия смерти Кощея в сундуке *)
*)
...
ClearSearchNoDeath (* очистка поиска сундука без смерти Кощея *)
Но мне следует переделать свой вариант через методы.
-
Вот в MUMPSе можно придумать структуру данных (сундуки) с которой проще работать,
и весь код сведётся к :
s i=""
f s i=$o(sunduki(i)) q:i="" q:$d(sunduki(i,"заяц","утка","яйцо","игла"))
в переводе на литературный будет примерно так:
Организуем цикл перебора по порядку всех индексов массива sunduki() до достижении конца массива или
наличии записи о зайце в сундуке, утки в зайце, яйце в утке и игле в яйце.
Если же ищется недостача, то всё отличие будет в одной закорючке - апострофе (инверсия лог.значения)
q:'$d(sunduki(i,"заяц","утка","яйцо","игла"))
По выходу i будет индексом при котором условие выполнилось или
пустой строкой (""), если безрезультатно.
Тут следует сказать, что какие-либо специфические данные об сундуке, зайцах, утках и т.д тоже могут быть в этом же
массиве sunduki. Например :)
sunduki(i,"заяц","вес")
sunduki(i,"заяц","утка","жирность")
sunduki(i,"заяц","утка","яйцо","игла","быстродействие")
-
Суть проблемы в следующем.
Традиционный цикл while имеет одну точку выхода – логическое выражение в заголовке цикла. В данной задаче (совсем не такой уж редкой, кстати) вычисление условия выхода – многоступенчатый процесс, в котором надо закешировать промежуточные переменные. Поэтому точку выхода надо растянуть до области выхода. В цикле while на Си это можно сделать с некоторой натяжкой, но, это конечно, изврат.
Практическая реализация предлагается такая: добавить ключевое слово АndWhile.
По русски, кстати, тоже будет неплохо: Пока ...ИПока...
Сразу пример, чтобы было понятно.
(http://s006.radikal.ru/i213/1301/22/fca770120b9b.png)
Тело цикла (строка "i=i+1") будет выполняться пока истинна коньюнкция всех охран – выражений после while и andwhile. Соответственно, после выхода из цикла будет истинна коньюнкция отрицаний всех охран.
В принципе, слово andwhile годится и для цикла do{….} while. Некошерно, конечно начинать с and когда еще не было просто while, но ничего лучше мне не удалось придумать.
Внедрить это в язык проще пареной репы, т. к. andwhile – это замаскированный if-exit.
Но на практике такое внедрение приведет к грандиозному, эпическому провалу.
Во-первых, andwhile нельзя засовывать в скобочные конструкции (в if, например) внутри цикла. Но это еще можно проверить.
(http://i057.radikal.ru/1301/a8/5f904d4b7357.png)
Во-вторых, в области выхода (от первого while до последнего andwhile) нельзя выполнять никаких действий, влияющих на инвариант цикла. Только вычисление условий выхода и кеширование переменных. Как показывает практика, объяснить это не то что "ополченцам", но и легиону программистов совершенно невозможно. А формализовать это и проверить нельзя (не вижу как).
Поэтому все будет переврано и сделано через жопу самыми невероятными способами.
-
Соответственно, после выхода из цикла будет истинна коньюнкция отрицаний всех охран.
Дизъюнкция, конечно же.
-
по мотивам из обсуждения http://forum.oberoncore.ru/viewtopic.php?f=27&t=3175&p=57993&hilit=andif#p57987 ?
-
Я тоже думал над этим, иногда полезно, нужно ввести какой-то механизм типа "конвейер операций" или "конвейер условий"
-
ну или как-то так ;) :
IF (( a
AND := BEGIN ... RETURN b END
AND := BEGIN ... RETURN c END )
OR d
OR := BEGIN ... RETURN e END )
THEN
...
END;
-
Скажу опять про тот же MUMPS.
нужная конструкция получается влёт
действие0
if условие1 действие1
if if условие2 действие2
if if условие3 действие3
....
if if условиеN действиеN
понять поведение можно по имитирующей конструкции с использованием вспомогательной переменной t
t:=true
действие0
if условие1 then действие1 else t:=false end
if t and условие2 then действие2 else t:=false end
if t and условие3 then действие3 else t:=false end
...
if t and условиеN then действиеN else t:=false end
-
На Обероне я бы сделал, наверное, так:
PROCEDURE Store (obj: ANYPTR; VAR ptr: ANYPTR): BOOLEAN;
BEGIN
ptr := obj;
RETURN obj # NIL
END Store;
i := 0;
WHILE (i < сундуки.length) &
~( Store(ЗАЯЦ(сундуки[i]), заяц)) & Store(УТКА(заяц(Заяц)), утка)) &
Store(ЯЙЦО(утка(Утка)), яйцо)) & Store(ИГЛА(яйцо(Яйцо)), игла)) )
DO
INC(i)
END
Единственное, чтобы передать переменную по VAR-параметру, она должна иметь тип ANYPTR. Отсюда потом каждый раз приведение типа.
-
А теперь решение... на ДРАКОНе (да простит меня уважаемый топикстартер :) )
Про что я всегда и пытался говорить - такие случаи разруливаются на плоскости безболезненно.
Посмотрите на вертикальный блок, проверяющий все !null и между проверками добывающий очередной объект.
Это наглядное выражение проверки конъюнкции условий с промежуточными действиями.
Два исхода - когда конъюнкция истинна (мы обладаем иглой) и когда она ложна (и мы продолжаем цикл).
И у самого цикла два исхода - "нашли"-"не нашли".
Поставьте палец где-нибудь внизу цикла - и сразу увидите постусловие (просто пробежавшись назад по маршруту, приведшему в данную точку, и собрав все условия на пути (или их отрицания) в конъюнкцию). Понятная структура, понятные логические свойства (делаю разрез в любой точке и знаю предусловие для данной точки).
А теперь расходитесь в стороны, господа, и дайте Петру ружьё :)
-
Голосую за вариант Ильи :)
PROCEDURE Store (obj: ANYPTR; VAR ptr: ANYPTR): BOOLEAN;
...Я думал примерно в том же направлении. Только с отдельными процедурами для каждого типа.
А еще можно эти процедуры в массив запихать. И спускаться по этому массиву... (можно рекурсивно)
-
А теперь решение... на ДРАКОНе (да простит меня уважаемый топикстартер :) )
Дейкстра ни разу не прав -- GOTO considered rules!!!
-
Соотношение ДРАКОНа и принципов Дейкстры рассматривалось - ДРАКОН не противоречит идеологии доказательного программирование в случае ухода от линейно-блочной топологии управления к плоской. Структурной двумерной, скажем так.
http://2010.it-edu.ru/docs/C4/a4a%20Ермаков%20И.Е1287620722076198.doc
-
(http://s018.radikal.ru/i525/1301/4d/777bd7a94af8.png)
Вот этот драконообразный бред от Ильи является ярким подтверждением моих слов о том, что
"объяснить это не то что "ополченцам", но и легиону программистов совершенно невозможно. Поэтому все будет переврано и сделано через жопу самыми невероятными способами."
Товарищ забыл тело цикла, i=i+1.
О чем еще тут можно говорить?
А ведь Илья далеко не самый глупый в этом легионе.
-
А ведь Илья далеко не самый глупый в этом легионе.
Да ладно - Легион- скажете тоже...
-
Легион на эту хрень не заставишь даже смотреть...
-
Товарищ забыл тело цикла, i=i+1.
О чем еще тут можно говорить?
А ведь Илья далеко не самый глупый в этом легионе.
Пётр, я его и в WHILE забываю иногда, если пишу для текста, а не программу. Так что разницы никакой.
А у Вас, мне кажется, ярко выраженное символьное мышление, только символьное. Вы не воспринимаете графическую форму в принципе - и ту информацию (как раз с позиции доказательного программирования), которую она может проявить. Видимо, это у Вас индивидуальные особенности воприятия.
Впрочем, у меня тоже большинство графики идёт "мимо кассы", знакомо.
-
Легион на эту хрень не заставишь даже смотреть...
А есть тупицы, которых не заставишь смотреть ни на что, что не блестит с первого взгляда.
Я предпочитаю искать там, где не ищут другие, потому что "не блестит".
-
Сразу пример, чтобы было понятно.
(http://s006.radikal.ru/i213/1301/22/fca770120b9b.png)
Тело цикла (строка "i=i+1") будет выполняться пока истинна коньюнкция всех охран – выражений после while и andwhile. Соответственно, после выхода из цикла будет истинна коньюнкция отрицаний всех охран.
Ада:
(http://s018.radikal.ru/i511/1301/f7/a7642b68cb30.png)
Ну и продублирую, а то мало ли что там с картинкой случится:
-- найти первый комплект без иглы
for i in сундуки'Range loop
заяц := ЗАЯЦ(сундуки(i));
exit when заяц = null;
утка := УТКА(заяц);
exit when утка = null;
яйцо := ЯЙЦО(утка);
exit when яйцо = null;
игла := ИГЛА(яйцо);
exit when игла = null;
end loop;
-
Впрочем, у меня тоже большинство графики идёт "мимо кассы", знакомо.
Да, я про это и говорю, но, с другой стороны, тот же Жаринов, не в состоянии вразумительно ответить на вопрос о преимуществах восприятия двумерных форм (точне, его ответы не только не вызывают желания тренировать это восприятие - но вызывают отвращение к этой тематике).
-
Если в программе "мало ветвлений", то никакой практически пользы от графики не обнаружится.
Как только становится "много ветвлений" (какая-нибудь логика на верхнем уровне бизнес-приложения, или логика в системах управления типа вот таких циклов - они там любят быть как раз, в СУ) - начинает проявляться польза - и, мне кажется, я достаточно много попытался объяснить, почему, с примерами.
-
Впрочем, у меня тоже большинство графики идёт "мимо кассы", знакомо.
Да, я про это и говорю, но, с другой стороны, тот же Жаринов, не в состоянии вразумительно ответить на вопрос о преимуществах восприятия двумерных форм (точне, его ответы не только не вызывают желания тренировать это восприятие - но вызывают отвращение к этой тематике).
С другой стороны я лично хорошо знаю, а точнее плотно работаю (в одном проекте) с людьми у которых явно преобладает восприятие двумерных форм над символьным мышлением. Любой элементарнейший алгоритм воспринимается только в виде чего-то двумерного (конечный автомат там нарисованый, или блок-схема).
Эти люди - электронщики. Не те которые процессора на fpga в VHDL делают, а те которые там платы разводят, под микроконтроллеры пишут и т.д.
Я с ужасом думаю, что будет если придется им объяснять что-то не тривиальное. То, что на ЯВУ декомпозируется легко и просто (особенно с учетом типизации и прочего) а вот попробуй ка это на 2D схеме нарисовать... 2D схема это ж уровень ассемблера.
-
Между прочим, Пётр всегда возмущается на ДРАКОН с позиций, что ДРАКОН посягает на "дейкстровское миропонимание".
А Дейкстра, согласитесь, в первую очередь занимался проблемами циклических участков алгоритмов, вычисляющего характера.
И ДРАКОН там нахрен не сдался.
А там, где начинается ветвистая логика, принятие решений, там инварианты как-то вообще, знаете, не помогают :)
-
Если в программе "мало ветвлений", то никакой практически пользы от графики не обнаружится.
Как только становится "много ветвлений" (какая-нибудь логика на верхнем уровне бизнес-приложения, или логика в системах управления типа вот таких циклов - они там любят быть как раз, в СУ) - начинает проявляться польза - и, мне кажется, я достаточно много попытался объяснить, почему, с примерами.
Если становится действительно МНОГО ветвлений, то графика также становится бесполезное - ибо все в черточках, графика становится перегруженной и не воспринимается вообще.
У графики одна проблема - она работает в очень узком диапазоне. Если ветвлений совсем мало - графика бесполезна, если ветвлений весьма много, графика опять бесполезна. Где-то по середине графика может дать более наглядное представление алгоритма для одного класса людей.
-
Ада:
-- найти первый комплект без иглы
for i in сундуки'Range loop
заяц := ЗАЯЦ(сундуки(i)); exit when заяц = null;
утка := УТКА(заяц); exit when утка = null;
яйцо := ЯЙЦО(утка); exit when яйцо = null;
игла := ИГЛА(яйцо); exit when игла = null;
end loop;
Нет принципиального отличия от моего варианта:
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) break;
утка = заяц.ИзвлечьУтку(); if (утка == null) break;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) break;
игла = яйцо.ИзвлечьУтку(); if (игла == null) break;
}
-
Эти люди - электронщики. Не те которые процессора на fpga в VHDL делают, а те которые там платы разводят, под микроконтроллеры пишут и т.д.
Я когда-то таким же электронщиком-микроконтроллерщиком был, в PCAD'e/Компасе3D схемы/платы/чертежи рисовал, и ничего, нормально программный код воспринимал. Правда, предпочитал распечатывать, что бы не на маленьком экране, а на куче листов бумаги видеть...
-
Ада:
-- найти первый комплект без иглы
for i in сундуки'Range loop
заяц := ЗАЯЦ(сундуки(i)); exit when заяц = null;
утка := УТКА(заяц); exit when утка = null;
яйцо := ЯЙЦО(утка); exit when яйцо = null;
игла := ИГЛА(яйцо); exit when игла = null;
end loop;
Нет принципиального отличия от моего варианта:
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) break;
утка = заяц.ИзвлечьУтку(); if (утка == null) break;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) break;
игла = яйцо.ИзвлечьУтку(); if (игла == null) break;
}
Принципиальной разницы, как и написал Петр Алмазов, действительно нет.
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
-
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
Хм. А разве оператором break можно выйти откуда-то ещё кроме как из цикла?
-
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
Хм. А разве оператором break можно выйти откуда-то ещё кроме как из цикла?
Конечно. Из switch.. case'а можно.
-
На Обероне я бы сделал, наверное, так:
PROCEDURE Store (obj: ANYPTR; VAR ptr: ANYPTR): BOOLEAN;
BEGIN
ptr := obj;
RETURN obj # NIL
END Store;
i := 0;
WHILE (i < сундуки.length) &
~( Store(ЗАЯЦ(сундуки[i]), заяц)) & Store(УТКА(заяц(Заяц)), утка)) &
Store(ЯЙЦО(утка(Утка)), яйцо)) & Store(ИГЛА(яйцо(Яйцо)), игла)) )
DO
INC(i)
END
Единственное, чтобы передать переменную по VAR-параметру, она должна иметь тип ANYPTR. Отсюда потом каждый раз приведение типа.
Во-первых. переусложнено (появилась дополнительная процедура).
Во-вторых я уже запутался - чем ЗАЯЦ, Заяц и заяц отличаются друг от друга? Вроде-бы изначально было ровно две сущности: ЗАЯЦ и заяц. А тут внезнапно третья появилась.
Короче, на Си такое пишется намного проще, понятней и компактней :-) Как говорится, наглядное преимущество Си (как потомка Algol-68).
-
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
Ооокей. Тогда так:
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) goto exit;
утка = заяц.ИзвлечьУтку(); if (утка == null) goto exit;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) goto exit;
игла = яйцо.ИзвлечьУтку(); if (игла == null) goto exit;
}
exit:; ;D
-
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
Ооокей. Тогда так:
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) goto exit;
утка = заяц.ИзвлечьУтку(); if (утка == null) goto exit;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) goto exit;
игла = яйцо.ИзвлечьУтку(); if (игла == null) goto exit;
}
exit:; ;D
Это усугубляет положение - goto еще более общая конструкция чем break. и у него точно также как и у break нет никакой связи с if'ом (в отличие от пары exit when)
-
Но есть нюанс - exit when созданы друг для друга именно в контексте цикла, в отличае от if () break
Ооокей. Тогда так:
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) goto exit;
утка = заяц.ИзвлечьУтку(); if (утка == null) goto exit;
яйцо = утка.ИзвлечьУтку(); if (яйцо == null) goto exit;
игла = яйцо.ИзвлечьУтку(); if (игла == null) goto exit;
}
exit:; ;D
омг, вот накопипастил ))) Вот что значит не проверять компилятором, компилятор наверняка бы поругался на несоответствие типов ))
// Найти первый комплект без иглы -- низкоуровневая имитация монады Maybe
for (int i = 0; i < сундуки.Length; i++)
{
заяц = сундуки[i]; if (заяц == null) goto exit;
утка = заяц.ИзвлечьУтку(); if (утка == null) goto exit;
яйцо = утка.ИзвлечьЯйцо(); if (яйцо == null) goto exit;
игла = яйцо.ИзвлечьИглу(); if (игла == null) goto exit;
}
exit:;
-
Это усугубляет положение - goto еще более общая конструкция чем break. и у него точно также как и у break нет никакой связи с if'ом (в отличие от пары exit when)
Только goto, только хардкор!
Ничего лишнего! Никаких break, никаких continue, никаких exit when!!!
Чем проще язык, тем легче сделать для него компилятор! (это же и есть главный девиз оберонов, не так ли?)
-
Ничего лишнего! Никаких break, никаких continue, никаких exit when!!!
:) А я то думал что второй вариант вам как функциональщику окажется ближе.. (т.е. они предпочитают использовать
сделать(опоределить) что-то, когда выполняется нечто... нежели если выполняется нечто то делать что-то).
-
Если в программе "мало ветвлений", то никакой практически пользы от графики не обнаружится.
Как только становится "много ветвлений" (какая-нибудь логика на верхнем уровне бизнес-приложения, или логика в системах управления типа вот таких циклов - они там любят быть как раз, в СУ) - начинает проявляться польза - и, мне кажется, я достаточно много попытался объяснить, почему, с примерами.
Боюсь, что НЕТ (я имею ввиду рядового программиста -не архитектора, или управляющего, также НЕ имеются ввиду. разводчики плат....)).
-
Ада:
(http://s018.radikal.ru/i511/1301/f7/a7642b68cb30.png)
Ну и продублирую, а то мало ли что там с картинкой случится:
-- найти первый комплект без иглы
for i in сундуки'Range loop
заяц := ЗАЯЦ(сундуки(i));
exit when заяц = null;
утка := УТКА(заяц);
exit when утка = null;
яйцо := ЯЙЦО(утка);
exit when яйцо = null;
игла := ИГЛА(яйцо);
exit when игла = null;
end loop;
Еще одно подтверждение тезиса про легион.
Вы поймите, что все разработчики языков шизанулись на выходе из цикла.
В таких конструкциях получается, что для продолжения цикла нужна истина в в заголовке цикла и ложь в условия выхода (exit when). Вот это несовпадение логических знаков и портит всю малину.
Но только тем, у кого есть что портить.
Остальным - пох...
-
А еще можно эти процедуры в массив запихать. И спускаться по этому массиву... (можно рекурсивно)
Типа так (если ничего не напутал):
func_array = {get_rabbit, get_duck, get_egg, get_needle}
result_array = {}
i = 0
box_count = #box_array
max_level = #func_array
while i < box_count and not result_array[max_level] do
i = i + 1
j = 0
last = box_array[i]
repeat
j = j + 1
current_func = func_array[j]
last = current_func(last)
result_array[j] = last
until j == max_level or not last
end
if result_array[max_level] then
print(i)
end
-
Еще одно подтверждение тезиса про легион.
Вы поймите, что все разработчики языков шизанулись на выходе из цикла.
В таких конструкциях получается, что для продолжения цикла нужна истина в в заголовке цикла и ложь в условия выхода (exit when). Вот это несовпадение логических знаков и портит всю малину.
Но только тем, у кого есть что портить.
Остальным - пох...
Ниче не понял... наоборот в условии выхода (exit when заяц=null) должна быть истина.. разве нет?
-
Вы не воспринимаете графическую форму в принципе
Графическую форму я воспринимаю.
Вот доказательство http://oberspace.dyndns.org/index.php/topic,172.msg2841.html#msg2841 :)
-
Еще одно подтверждение тезиса про легион.
Вы поймите, что все разработчики языков шизанулись на выходе из цикла.
В таких конструкциях получается, что для продолжения цикла нужна истина в в заголовке цикла и ложь в условия выхода (exit when). Вот это несовпадение логических знаков и портит всю малину.
Но только тем, у кого есть что портить.
Остальным - пох...
Именно это я и хотел показать этим примером :-)
Я прекрасно понимаю почему то что в Аде не является тем, что было там. Впрочем, до конца осознать ценность ИПока я тоже пока не могу. Но различие вижу.
-
Ниче не понял... наоборот в условии выхода (exit when заяц=null) должна быть истина.. разве нет?
Самого Exit не должно быть. Должно быть ключевое слово продолжения цикла.
-
Ниче не понял... наоборот в условии выхода (exit when заяц=null) должна быть истина.. разве нет?
Самого Exit не должно быть. Должно быть ключевое слово продолжения цикла.
вы считаете что "continue when заяц<>null" более правильно?
-
Да. Но выглядит безобразно. Мой вариант - andwhile.
-
Легион на эту хрень не заставишь даже смотреть...
А есть тупицы, которых не заставишь смотреть ни на что, что не блестит с первого взгляда.
Я предпочитаю искать там, где не ищут другие, потому что "не блестит".
боюсь что дерьмо есть универсальная отправная точка для ваших изысков ибо оно "не блестит" стопудово... как не крути... а насчет "запаха" у вас случайно предпочтений нет?
-
Да. Но выглядит безобразно. Мой вариант - andwhile.
надо подумать.. с одной стороны.. программа всего лишь отображение на ЯП некоторого алгоритма... с другой стороны.. плодить вариации управляющих инструкций ЯП (для повышении "естественности" такого отображения).. слишком накладно. кстати.. а что вам не нравится в линейном решении Albobin a?
-
(http://s018.radikal.ru/i525/1301/4d/777bd7a94af8.png)
Вот этот драконообразный бред от Ильи является ярким подтверждением моих слов о том, что
"объяснить это не то что "ополченцам", но и легиону программистов совершенно невозможно. Поэтому все будет переврано и сделано через жопу самыми невероятными способами."
Товарищ забыл тело цикла, i=i+1.
О чем еще тут можно говорить?
А ведь Илья далеко не самый глупый в этом легионе.
Не согласен про бред.
Хорошая схема.
Если бы она еще формально была получена, то товарищ бы в принципе не смог забыть про i := i +1.
А то, что забыл - это в пост "Мои типичные ошибки".
-
Чет я пропустил, что нужен еще вариант поиска комплекта без иглы.
-- ищем первый комплект без иглы
i = 0
box_count = #box_array
max_level = #func_array
j = max_level
while i < box_count and j == max_level do
i = i + 1
j = 0
last = box_array[i]
repeat
j = j + 1
current_func = func_array[j]
last = current_func(last)
result_array[j] = last
until j == max_level or not last
end
if j < max_level then
print(i)
print(box_array[i], unpack(result_array))
end
ps http://repl.it/HAD
-
i := 0;
WHILE
(i < LEN(сундуки)) &
(
~ЗАЯЦ(сундуки[i], заяц) OR
~УТКА(заяц, утка) OR
~ЯЙЦО(утка, яйцо)
)
DO
INC(i);
END;
+1
Имхо самый ходовой вариант. Я бы делал именно так (и обычно делаю так).
И похожая тема уже была кстати на оберкоре:
http://forum.oberoncore.ru/viewtopic.php?f=27&t=3175
-
ps http://repl.it/HAD
Если в браузере русские символы кракозябрами, то нужно принудительно выставить кодировку страницы UTF-8
-
И похожая тема уже была кстати на оберкоре:
http://forum.oberoncore.ru/viewtopic.php?f=27&t=3175
Да-да. И даже был мой пост в моем блоге: http://valexey.blogspot.ru/2011/01/and-then-in-c.html
-
...
Если бы она еще формально была получена, то товарищ бы в принципе не смог забыть про i := i +1.
А то, что забыл - это в пост "Мои типичные ошибки".
Не нужно для подобных задач просто while использовать. См. адский пример. То есть везде где это возможно следует использовать спец. формы циклов вроде foreach. Узкая специализация позволяет избавиться от многих ошибок.
-
i := 0;
WHILE
(i < LEN(сундуки)) &
(
~ЗАЯЦ(сундуки[i], заяц) OR
~УТКА(заяц, утка) OR
~ЯЙЦО(утка, яйцо)
)
DO
INC(i);
END;
+1
Имхо самый ходовой вариант. Я бы делал именно так (и обычно делаю так).
И похожая тема уже была кстати на оберкоре:
http://forum.oberoncore.ru/viewtopic.php?f=27&t=3175
да не пойдет же это , причем по ЧЕТКО сформулированному ИСХОДНОМУ условию... зайцевость, уткость. нужно сохранять... а не просто удостоверять на отсутствие...
-
Тык сохраняется же ???
Тут:
ЗАЯЦ(сундуки, заяц)
заяц - OUT параметр...
-
Использование функций без побочных эффектов для извлечения различных элементов (сундуков, зайцев, уток, яиц, игл, смертей Кощея) друг из друга невозможно, так как структурные значения не могут быть результатами функций. Если выводить ссылку на значение, то это уже изменяет значение динамической переменной (побочный эффект).
Как например здесь:
i := 0;
WHILE (i < LEN(сундуки)) & ((ЗАЯЦ(сундуки[i]) = NIL) OR (УТКА(ЗАЯЦ(сундуки[i])) = NIL) OR (ЯЙЦО(УТКА(ЗАЯЦ(сундуки[i]))) = NIL)) DO INC(i) END
....
(* приск первого сундука с иглой *)
WHILE list.HasMoreElements() AND смерть = NIL DO
сундук := list.GetNext();
IF сундук.UnpackTo( заяц ) AND
заяц .UnpackTo( утка ) AND
утка .UnpackTo( яйцо ) AND
яйцо .UnpackTo( игла ) AND
игла .UnpackTo( смерть ) THEN
Log.String("капец Кащею");
END;
END;
PROCEDURE Store (obj: ANYPTR; VAR ptr: ANYPTR): BOOLEAN;
BEGIN
ptr := obj;
RETURN obj # NIL
END Store;
i := 0;
WHILE (i < сундуки.length) &
~( Store(ЗАЯЦ(сундуки[i]), заяц)) & Store(УТКА(заяц(Заяц)), утка)) &
Store(ЯЙЦО(утка(Утка)), яйцо)) & Store(ИГЛА(яйцо(Яйцо)), игла)) )
DO
INC(i)
END
Впрочем само условие задачи (автор) требует, чтобы сохранялись промежуточные значения элементов. Так что без побочных эффектов не обойтись, если пользоваться одним выражением проверки.
Если представлять значения элементов самими указателями (как у меня), то их разыменованные значения (хранящие структуру вложенности элементов) станут изменяемыми во внешних модулях, то есть интерфейс модуля "сундуков Кощея" будет недостаточно изолирован. К тому же ссылочные структуры засоряют память.
Использование собственно процедур для извлечения различных элементов друг из друга, не позволит выполнять проверку в одном выражении. Придеться использовать вложенные операторы или же последовательные операторы с лишними проверками: (это собственно к вопросу о циклах)
existSearchDeath := FALSE; (* смерть Кощея пока не найдена *)
WHILE
(i < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchDeath (* проверка, что смерть Кощея еще не найдена *)
DO
ds.сhests^[i].Hare(hare); (* извлечение зайца из сундука *)
IF hare # nullHare THEN (* проверка, что в сундуке есть заяц *)
hare.Duck(duck); (* извлечение утки из зайца *)
IF duck # nullDuck THEN (* проверка, что в зайце есть утка *)
duck.Egg(egg); (* извлечение яйца из утки *)
IF egg # nullEgg THEN (* проверка, что в утке есть яйцо *)
egg.Needle(needle); (* извлечение иглы из яйца *)
IF needle # nullNeedle THEN (* проверка, что в яйце есть игла *)
needle.Death(death); (* извлечение смерти Кощея из иглы *)
existSearchDeath := death # nullDeath; (* смерть Кощея найдена, если игла не пустая *)
END
END
END
END;
INC(i) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
ENDили
existSearchDeath := FALSE; (* смерть Кощея пока не найдена *)
WHILE
(i < ds.n) (* проверка, что непросмотренные сундуки еще остались *)
& ~existSearchDeath (* проверка, что смерть Кощея еще не найдена *)
DO
ds.сhests^[i].Hare(hare); (* извлечение зайца из сундука *)
b := hare # nullHare; (* заяц найден, если сундук не пустой *)
IF b THEN (* проверка, что в сундуке есть заяц *)
hare.Duck(duck); (* извлечение утки из зайца *)
b := duck # nullDuck; (* утка найдена, если зайц не пустой *)
END;
IF b THEN (* проверка, что в зайце есть утка *)
duck.Egg(egg); (* извлечение яйца из утки *)
b := egg # nullEgg; (* яйцо найдено, если утка не пустая *)
END;
IF b THEN (* проверка, что в утке есть яйцо *)
egg.Needle(needle); (* извлечение иглы из яйца *)
b := needle # nullNeedle; (* игла найдена, если яйцо не пустое *)
END;
IF b THEN (* проверка, что в яйце есть игла *)
needle.Death(death); (* извлечение смерти Кощея из иглы *)
existSearchDeath := death # nullDeath; (* смерть Кощея найдена, если игла не пустая *)
END;
INC(i) (* переход к следующему (еще непросмотренному) сундуку, если такой есть *)
END
-
Коммент на каждой строчке - это жестоко ;)
-
Использование функций без побочных эффектов для извлечения различных элементов (сундуков, зайцев, уток, яиц, игл, смертей Кощея) друг из друга невозможно, так как структурные значения не могут быть результатами функций. Если выводить ссылку на значение, то это уже изменяет значение динамической переменной (побочный эффект)...
Мутно как-то..
1. Не во всех языках это так (а задача не была ограничена КОНКРЕТНЫМ языком)
2. Не очень понятно про какой "побочный" эффект вы говорите... в классике им называют изменение значения глобальной переменной в подпрограмме..
-
разумеется если параметр в явном виде не передавался (я говорю в данном случае про передачу по ссылке)
-
Тык сохраняется же ???
Тут:
ЗАЯЦ(сундуки, заяц)
заяц - OUT параметр...
угу сорри .. понял.. однако один черт albobin ское решение более нравится... возможно потому , что оно следует из грамотного определения зайцев (включающего в себя проверку на существование).
-
не самих зайцев.. а функции ЗАЯЦ.. сорри за неточность
-
Коммент на каждой строчке - это жестоко ;)
;D ;D ;D ;D а нефиг время тратить на дурацкие задачки.. тогда и сурьезные люди будут вас считать человеком... ;)
-
Коммент на каждой строчке - это жестоко ;)
Правильно, это когда комментарий к каждой лексеме.
У меня бывают приступы формализма и педантизма.
...
2. Не очень понятно про какой "побочный" эффект вы говорите... в классике им называют изменение значения глобальной переменной в подпрограмме..
разумеется если параметр в явном виде не передавался (я говорю в данном случае про передачу по ссылке)
Динамические переменные по определению глобальны, они доступны (в общем случае) через глобальные идентификаторы.
Даже если функция создает новое сслылочное значение (размещает новую динамическую переменную) только под выдаваемый результат, это изменяет глобальное окружение после завершения вызова функции. Даже если в дальнейшем это новое сслылочное значение будет утеряно (станет недоступным) в том выражении где сидел этот вызов, все равно это считается побочным эффектом.
-
Коммент на каждой строчке - это жестоко ;)
Правильно, это когда комментарий к каждой лексеме.
У меня бывают приступы формализма и педантизма.
...
2. Не очень понятно про какой "побочный" эффект вы говорите... в классике им называют изменение значения глобальной переменной в подпрограмме..
разумеется если параметр в явном виде не передавался (я говорю в данном случае про передачу по ссылке)
Динамические переменные по определению глобальны, они доступны (в общем случае) через глобальные идентификаторы.
Даже если функция создает новое сслылочное значение (размещает новую динамическую переменную) только под выдаваемый результат, это изменяет глобальное окружение после завершения вызова функции. Даже если в дальнейшем это новое сслылочное значение будет утеряно (станет недоступным) в том выражении где сидел этот вызов, все равно это считается побочным эффектом.
спасибо, понял, но в цитируемом вами моем сообщении я имел ввиду ссылочный параметр передаваемый в функцию ЗАЯЦ (заяц) по версии Бориса и иже с ним... там идет заполнение существующей переменной.
-
спасибо, понял, но в цитируемом вами моем сообщении я имел ввиду ссылочный параметр передаваемый в функцию ЗАЯЦ (заяц) по версии Бориса и иже с ним... там идет заполнение существующей переменной.
А что это меняет? То, что у переменной только значение меняется, а сама она остается?
Если параметр-переменная "заяц" здесь ссылочная, то присвоение "результата" функции переменной заяц^, это само по себе глобальный эффект.
Если же параметр-переменная "заяц" здесь не ссылочная, даже если она при этом локальная, все равно это функция с глобальным эффектом, хотя этот ее конкретный вызов и без глобального эффекта. Ведь эта функция может вызываться с глобальным эффектом - в каком-то другом месте программы.
Но даже если функция локальна либо неэкспортируема, а содержащий ее модуль всегда вызывает ее без реального глобального эффекта (в силу невыполнения некоторых условных ветвей или холостого присвоения внешним переменным тех же значений из-за ограничений значений и структуры фактических параметров), это не значит что эта функция не даст глобальный эффект каком-то в другом програмном окружении, т.е. будучи помещенной в другой модуль. Главное, что функция в принципе способна на глобальный эффект, что некоторый внешний по отношению к ней алгоритм может использовать функцию с таким же текстом для такого эффекта.
Функция без глобального эффекта при любом вызове в любой возможной программе не должна изменять переменные, лежащие ниже ее по стеку, т.е. созданные в реал-тайм ранее этого вызова, а также изменять любые переменные из кучи и изменять динамические типы (создавать-уничтожать значения типа) раз те в ЯП являются глобальными.
Функция будет без глобального эффекта, если результат произвольного ее вызова, будучи сразу не сохраненным (например, присвоенным параметру пустой процедуры без OUT-параметров), не оказывает никакого воздействия (наблюдаемого средствами языка) на работу программы по сравнению с отсутствием такого вызова.
Не следует смешивать:
- функцию с возможным глобальным эффектом (для некоторой произвольной точки вызова в некоторой произвольной программе),
- функцию с возможным глобальным эффектом (для некоторой произвольной точки вызова в конкретной программе),
- текстовой вызов функции (для конкретной точки в конкретной программе) с возможным глобальным эффектом, и
- реал-тайм вызов функции (для конкретной точки в конкретной программе) с реальным глобальным эффектом.
Первый, с самым слабым условием, вариант и должен служить определением "функии без побочного эффекта".
-
Не следует смешивать:
По-моему ты придумал какую-то собственную терминологию. Функция без побочных эффектов (она же "чистая") - это функция, которая для одних и тех же аргументов всегда возвращает один и тот же результат и сама не вызывает функций с побочными эффектами. Все остальные предложенные "разновидности" - не знаю для чего могут понадобиться.
Применительно к данной задаче чистая функция могла бы возвращать структуру/кортеж. с найденным состоянием.
-
Кроме того, что функция может быть чистой и грязной (с побочными эффектами), она ещё может быть тотальной (гарантированно успешно завершится) и не тотальной (может выдать ошибку или никогда не завершиться).
Например, f(x)=5/x может выдать деление на ноль, и хоть она и является чистой, тотальной она не является.
-
спасибо, понял, но в цитируемом вами моем сообщении я имел ввиду ссылочный параметр передаваемый в функцию ЗАЯЦ (заяц) по версии Бориса и иже с ним... там идет заполнение существующей переменной.
А что это меняет? То, что у переменной только значение меняется, а сама она остается?
Если параметр-переменная "заяц" здесь ссылочная, то присвоение "результата" функции переменной заяц^, это само по себе глобальный эффект.
1. Я не считаю конкретно это изменение ПОБОЧНЫМ эффектом - хотя конечно это изменяет глобальное окружение
2. Вы через чур сильно обобщаете свои рассуждения - следуя этому пути можно всегда предположить, что в одной из этих процедур есть и традиционный побочный эффект (прямое изменение значения глобальной переменной не передающейся через интерфейс подпрограммы).. а раз так то и задача не имеет смысла...
-
Не следует смешивать:
По-моему ты придумал какую-то собственную терминологию. Функция без побочных эффектов (она же "чистая") - это функция, которая для одних и тех же аргументов всегда возвращает один и тот же результат и сама не вызывает функций с побочными эффектами. Все остальные предложенные "разновидности" - не знаю для чего могут понадобиться.
Применительно к данной задаче чистая функция могла бы возвращать структуру/кортеж. с найденным состоянием.
1. тык про это я и говорил... только Vlad - нужно добавить без несанкционированного изменения значений переменных глобального окружениия - в вашем определении.
2. Для более глубокого понимания того, насколько искажается система при ее компьютерном моделировании... и вообще для развития - если есть какая то "генеральная" базовая идея - игра с определениями может довольно много дать...
-
1. Я не считаю конкретно это изменение ПОБОЧНЫМ эффектом - хотя конечно это изменяет глобальное окружение
Любое изменение глобального окружения функции внутри неё является побочным эффектом, будь-то ввод/вывод, прямое или косвенное изменение глобальной переменной.
Если функция хоть как-то влияет на изменение глобального (по отношению к ней) состояния программы, то эта функция имеет побочный эффект.
-
i := 1
while i <= #(сундуки) and игла = nil do
сундук := сундуки[i]; заяц := nil; утка := nil; яйцо := nil; игла := nil
заяц := ЗАЯЦ(сундук)
if заяц ~= nil then утка := УТКА(заяц) end
if утка ~= nil then яйцо := ЯЙЦО(утка) end
if яйцо ~= nil then игла := ИГЛА(яйцо) end
i := i+1
end
i := 1
repeat
сундук := сундуки[i]; заяц := nil; утка := nil; яйцо := nil; игла := nil
заяц := ЗАЯЦ(сундук)
if заяц ~= nil then утка := УТКА(заяц) end
if утка ~= nil then яйцо := ЯЙЦО(утка) end
if яйцо ~= nil then игла := ИГЛА(яйцо) end
i := i+1
until i > #(сундуки) or заяц = nil or утка = nil or яйцо = nil or игла = nil
-
1. Я не считаю конкретно это изменение ПОБОЧНЫМ эффектом - хотя конечно это изменяет глобальное окружение
Любое изменение глобального окружения функции внутри неё является побочным эффектом, будь-то ввод/вывод, прямое или косвенное изменение глобальной переменной.
Если функция хоть как-то влияет на изменение глобального (по отношению к ней) состояния программы, то эта функция имеет побочный эффект.
Если так рассуждать - то Хаскели и проч. "чистые" ФЯВУ - не только таковыми не являются - но потенциально гораздо более опасны чем императивные ЯП. И потом, я не говорю о том, что определение ddn и ваше несостоятельны вообще... скорее о том, что оно неадекватно общее в контексте данной задачи... Я рассматриваю в конкретно этом случае вопрос достаточно просто (осознавая что это результат идеализации), функция - черный ящик,система изолирована, инструкции выполняются последовательно (как в программе, так и в подпрограммах)... С моей точки зрения это вполне естественно - ну не будете же вы рассматривать решения уравнений движения молекул из которых состоит прямолинейно и равномерно движущийся автомобиль с заданной скоростью для выяснения расстояния на которое переместился его центр масс...
-
Если так рассуждать - то Хаскели и проч. "чистые" ФЯВУ - не только таковыми не являются - но потенциально гораздо более опасны чем императивные ЯП.
Насчёт чистоты поспорить можно, но, в принципе, для того что бы какой-то язык был практичным, он должен иметь хотя бы какие-то способы производить ввод/вывод.
А что там за проблема с потенциальной большей опасностью по сравнению с императивными ЯП?
-
while i <= #(сундуки) and игла = nil do
сундук := сундуки[i]; заяц := nil; утка := nil; яйцо := nil; игла := nil
заяц := ЗАЯЦ(сундук)
if заяц ~= nil then утка := УТКА(заяц) end
if утка ~= nil then яйцо := ЯЙЦО(утка) end
if яйцо ~= nil then игла := ИГЛА(яйцо) end
i := i+1
end
Итить твою, как всё очевидно. А мы тут накрутили. Ведь и в самом первом варианте Алмазова достаточно вместо внутреннего if игла # NIL then break вынести & (игла = NIL) в условие цикла.
-
i := 1
while i <= #(сундуки) and игла = nil do
сундук := сундуки[i]; заяц := nil; утка := nil; яйцо := nil; игла := nil
заяц := ЗАЯЦ(сундук)
if заяц ~= nil then утка := УТКА(заяц) end
if утка ~= nil then яйцо := ЯЙЦО(утка) end
if яйцо ~= nil then игла := ИГЛА(яйцо) end
i := i+1
end
i := 1
repeat
сундук := сундуки[i]; заяц := nil; утка := nil; яйцо := nil; игла := nil
заяц := ЗАЯЦ(сундук)
if заяц ~= nil then утка := УТКА(заяц) end
if утка ~= nil then яйцо := ЯЙЦО(утка) end
if яйцо ~= nil then игла := ИГЛА(яйцо) end
i := i+1
until i > #(сундуки) or заяц = nil or утка = nil or яйцо = nil or игла = nil
Почему-то все прочитывают условия задачи так: извратиться любой ценой, но обойтись без exit. При этом предполагается, что этот изврат представляет хоть какую-нибудь ценность.
Я же написал в начале, никаких извратов, никаких компромиссов, затраты ресурсов не должны превышать исходный вариант с exit. Лишнее присваивание – расстрел. Полно ведь ситуаций, когда ресурсы крайне ограничены. Ну, на Марс мы летим.
В таких случаях приходится идти на компромисс и выбирать не красоту, а эффективность.
А Идеальный Конечный Результат – это когда цель достигнута НЕ ценой компромисса. Не жертвуя ни тем, ни другим. И затраты равны нулю.
-
А Идеальный Конечный Результат – это когда цель достигнута НЕ ценой компромисса. Не жертвуя ни тем, ни другим. И затраты равны нулю.
;) тогда имеет смысл рассматривать решения на ассемблере....
-
Итить твою, как всё очевидно. А мы тут накрутили.
Да, я вот смотрел на варианты, представленные оберонщиками, и диву давался -- откуда у них такая извращённая фантазия, столько говнокода накручивать )))
-
... Почему-то все прочитывают условия задачи так: извратиться любой ценой, но обойтись без exit. При этом предполагается, что этот изврат представляет хоть какую-нибудь ценность.
... Лишнее присваивание – расстрел. Полно ведь ситуаций, когда ресурсы крайне ограничены. Ну, на Марс мы летим.
В таких случаях приходится идти на компромисс и выбирать не красоту, а эффективность.
Можно придумать и такую ситуацию - следствие отказа от лишнего присваивания.
В том конкретном цикле, где выход, если чего-то нет. Вышли на какой-то (не первой) итерации, когда наткнулись на отсутствие чего-то, а ведь всё остальное будет же не null . Типа - заяца нет, а яйцо есть , не говоря уж об игле :-)
-
Можно придумать и такую ситуацию - следствие отказа от лишнего присваивания.
В том конкретном цикле, где выход, если чего-то нет. Вышли на какой-то (не первой) итерации, когда наткнулись на отсутствие чего-то, а ведь всё остальное будет же не null . Типа - заяца нет, а яйцо есть , не говоря уж об игле :-)
Да ладно, Петру и так не позавидуешь - и конфетку съесть и на х. сесть и без компромиссов не всякий сподобится, с другой стороны - тем слаще победа...
-
Peter Almazov, я прочитал сейчас ваши условия 5 раз, но так и не понял что вы хотите увидеть.
Если вы хотите избавиться от break в вашем коде, то достаточно вынести условие игла == null в заголовок цикла. Внутри цикла if игла != null с бряком соответственно убрать. Это будет классический линейный поиск. Потери эффективности практически не будет.
-
После того, как я выложил решение, ничего, собственно, и не ожидаю увидеть.
-
Так вы выложили его в исходном посте... гы хорошая шутка (весь этот топик)... +100
-
Peter Almazov, я прочитал сейчас ваши условия 5 раз, но так и не понял что вы хотите увидеть.
Ты пропустил важные строчки:
Этот пост адресован тем, кто считает наличие exit/break внутри цикла плохим тоном...
Те, кто лепит exit/break в теле цикла без малейших колебаний, могут дальше не читать.
т.е. мне он посвящен, к примеру, а тебе нет )
-
while (i != сундуки.Length && игла == null) {
заяц = ЗАЯЦ(сундуки[i]);
if (заяц != null) {
утка = УТКА(заяц);
if (утка != null) {
яйцо = ЯЙЦО(утка);
if (яйцо != null) {
игла = ИГЛА(яйцо);
}
}
}
i = i + 1
}
-
т.е. мне он посвящен, к примеру, а тебе нет )
Прикольно. :) Это как такой вывод на мой счет сделан?
-
Прикольно. :) Это как такой вывод на мой счет сделан?
Ну мне так показалось ;) что ты не против брейка
-
Так вы выложили его в исходном посте... гы хорошая шутка (весь этот топик)... +100
Вы невнимательны.
Решение здесь http://oberspace.dyndns.org/index.php/topic,425.msg13272.html#msg13272
-
2 Kemet
Не помню ни одного случая, чтоб без бряка не получалось написать... Да и вообще не умею я думать бряками.
Но кодеров, пишущих такой код, хочется периодически прибить лопатой и закопать... да...
-
2ilovb,
ну я тоже к ним терпимо отношусь, но глаза мозолят
впрочем, здесь можно было бы замастачить цикл-паук, но уж шибко было лень
я совсем не считаю зазорным использовать переменную, индицирующую достижение результата, или состояние
-
Петр, так чем такой вариант плох?
http://oberspace.dyndns.org/index.php/topic,425.msg13459.html#msg13459
-
Он плох процессом своего рождения.
Автор при этом думал "как бы мне извратиться?"
Т.к. этот аргумент не будет понят с вероятностью 100%, то укажу на более зримые недостатки.
В заголовке цикла лишняя проверки иглы. Можно представить картину, когда все сундуки пустые. В варианте с exit в этом случае не будет ни одной проверки иглы.
Еще более неприятно то, что после того, как игла была найдена, тело цикла (i=i+1 ) все равно выполняется. Если игла в последнем сундуке, то сработает охрана "i != сундуки.Length". Очевидно, что это будет неожиданностью для автора.
Говно, в общем :)
-
Так вы выложили его в исходном посте... гы хорошая шутка (весь этот топик)... +100
Вы невнимательны.
Решение здесь http://oberspace.dyndns.org/index.php/topic,425.msg13272.html#msg13272
угу... не внимателен... сорри.. -упустил этот момент....
-
Он плох процессом своего рождения.
Автор при этом думал "как бы мне извратиться?"
Т.к. этот аргумент не будет понят с вероятностью 100%, то укажу на более зримые недостатки.
Мне вообще не пришлось думать, т.к. автор этого кода ВЫ. Я лишь перенес условие в заголовок цикла.
В заголовке цикла лишняя проверки иглы. Можно представить картину, когда все сундуки пустые. В варианте с exit в этом случае не будет ни одной проверки иглы.
Проверка на null дорогая операция? Вы уверены на 100% что это медленнее варианта с break?
Еще более неприятно то, что после того, как игла была найдена, тело цикла (i=i+1 ) все равно выполняется.
Психологический барьер?
Если игла в последнем сундуке, то сработает охрана "i != сундуки.Length". Очевидно, что это будет неожиданностью для автора.
Т.е. это по вашему безобразие?
if (игла != null) {
result = i-1;
}
Ну делайте так тогда
int i = -1;
while (i != сундуки.Length && игла == null) {
i = i + 1
заяц = ЗАЯЦ(сундуки[i]);
if (заяц != null) {
утка = УТКА(заяц);
if (утка != null) {
яйцо = ЯЙЦО(утка);
if (яйцо != null) {
игла = ИГЛА(яйцо);
}
}
}
}
if (игла != null) {
result = i;
}
-
.. как ваше решение проблемы, но на andwhile среагировал http://oberspace.dyndns.org/index.php?action=post;quote=13341;topic=425.75;last_msg=13468 (http://oberspace.dyndns.org/index.php?action=post;quote=13341;topic=425.75;last_msg=13468)... отношение такое же как циклу Дейкстры.. особых проблем в его отсутствии в явном виде не вижу... хоть убейте...
-
Пётр, если в Ваш код вставить строку
i = сундуки.Length;
при успешном поиске, то условие завершения цикла выполнится без дополнительных переменных
-
Пётр, если в Ваш код вставить строку
i = сундуки.Length;
при успешном поиске, то условие завершения цикла выполнится без дополнительных переменных
Не понял, о чем речь.
Напишите уж полностью.
-
Не понял, о чем речь.
Напишите уж полностью.
Ну как-же - всё просто
while (i != сундуки.Length && игла == null) {
заяц = ЗАЯЦ(сундуки[i]);
if (заяц != null) {
утка = УТКА(заяц);
if (утка != null) {
яйцо = ЯЙЦО(утка);
if (яйцо != null) {
игла = ИГЛА(яйцо);
i = сундуки.Length;
}
}
}
i = i + 1
}
если бы это был FOR например в Модуле-3, то значение переменной цикла за пределами цикла не определено, а если переменная локальна, то вообще недоступна. Так что то, что i в результате не указывает на нужный сундук не важно, т.к. все промежуточные значения "ящиков" сохранены.
-
блин, условие в цикле нужно поменять на "меньше" или в операции добавить -1
-
а еще убрать (игла == null) в условии цикла
-
Ну что вы, это изврат.
Не наш метод.
Вы же видите, что обе, т. н., "задачи" по своей сути тривиальны до крайности. Тут "решать"-то нечего. Профессионал не может позволить себе роскошь задумываться над такой ерундой.
А вот с точки зрения использования выразительных средств это - да, задачи.
-
а еще убрать (игла == null) в условии цикла
а, да, это же я скопировал вариант ilobv, а не Петра. Пётр, кстати, зачем Вы картинку вставили вместо текста?
Вобщем как-то так должно быть
while i < сундуки.Length {
заяц = ЗАЯЦ(сундуки[i]);
if (заяц != null) {
утка = УТКА(заяц);
if (утка != null) {
яйцо = ЯЙЦО(утка);
if (яйцо != null) {
игла = ИГЛА(яйцо);
i = сундуки.Length;
}
}
}
i = i + 1
}
Ну что вы, это изврат.
Не наш метод.
Да ладно Вам, у каждого свои тараканы, одному нужны инварианты, другой носится с циклом Дейкстры, третьему нужна выразительность, четвертому "только хардкор", пятому эффективное решение, ...
Так что и этот вариант ничуть не более извращенный, чем другие.
Вы же видите, что обе, т. н., "задачи" по своей сути тривиальны до крайности. Тут "решать"-то нечего. Профессионал не может позволить себе роскошь задумываться над такой ерундой.
Конечно, задача простейшая, и каждый решает её действительно не задумываясь, по своему, в соответствии со своим представлении о прекрасном.
Но я не согласен, что не стоит и "задумываться над такой ерундой" - сколько раз замечал, что новый подход к решению даже тривиальных задач существенно упрощает решение сложных, ибо большая сложная всегда разбивается на тривиальные.
А вот с точки зрения использования выразительных средств это - да, задачи.
Мы живем в реальном мире и вынуждены ограничивать свои фантазии, ибо иначе они переходят в область вакуумных сфероидов.
В этом смысле последний вариант ничуть не хуже варианта с andwhile, хотя бы потому, что реален.
-
Функция без побочных эффектов (она же "чистая") - это функция, которая для одних и тех же аргументов всегда возвращает один и тот же результат и сама не вызывает функций с побочными эффектами.
Непонятно, зачем только эта рекурсивная добавка в определении.
Такая функция будет вносить (вообще говоря) побочные эффекты в выражения в которых она вызывается.
И вы сделали акцент на влиянии внешнего окружения на функцию (на ее результат), таком влиянии, чтобы ее результат зависел только от значения ее фактических параметров, то есть не зависел:
- от неявно импортиремых (всеми вызываемыми в ней процедурами) внешних переменных (но допустима зависимость от констант и других процедур),
- от разыменованных переменных взятых от ссылочных компонент ее параметров,
- от ссылочных значений созданных при ее вызове.
В то время как побочный эффект есть влияние функции на внешнее окружение.
Все остальные предложенные "разновидности" - не знаю для чего могут понадобиться.
Для того чтобы сделать все выражения без побочных эффектов, они и понадобятся.
Если все функции всегда не изменяют внешнее окружение, а операторы не выдают значений и тем самым не входят в выражения (хороший, годный язык), то все выражения не имеют побочных эффектов.
Я за то, чтобы все функции (а значит и выражения) обязательно были без побочных эффектов, и это проверялось компилятором консервативными методами (по структуре ее ввода-вывода). Конечно, некоторые функции без побочных эффектов будут при этом отсеиваться, те, чья проверка их безпобочности будет неконсервативна, а то может быть и вовсе неразрешима.
А вот условие чистоты функций для меня не обязательно, хотя его проверку тоже можно втиснуть в консервативные рамки и сделать обязательной при компиляции.
Применительно к данной задаче чистая функция могла бы возвращать структуру/кортеж. с найденным состоянием.
Только следует быть осторожным при возвращении ссылки на структуру или структуры со сслылочными компонентами. При одних и тех же аргументах, функция может выдавать структурно одинаковые результаты, но с разными значениями ссылок, т.е. формально другой результат.
Тогда для чистоты придеться явно вносить в вызов функции ссылочные компоненты ее результата - через фактические параметры.
Следует также помнить, что разыменованные ссылочные компоненты результата функции в сам результат уже не входят и не существенны для вопроса одинаковости и различности результатов функции. В частности, если результат функции есть ссылка, то ее результат ограничивается лишь этим ссылочным значением. Это же относится и к ее аргументам.
Кроме того, что функция может быть чистой и грязной (с побочными эффектами), она ещё может быть тотальной (гарантированно успешно завершится) и не тотальной (может выдать ошибку или никогда не завершиться).
Например, f(x)=5/x может выдать деление на ноль, и хоть она и является чистой, тотальной она не является.
Выход из функции по ошибке не является побочным эффектом, т.к. находится вне среды исполнения программы, т.е. вне видимости языка.
Если параметр-переменная "заяц" здесь ссылочная, то присвоение "результата" функции переменной заяц^, это само по себе глобальный эффект.
1. Я не считаю конкретно это изменение ПОБОЧНЫМ эффектом - хотя конечно это изменяет глобальное окружение
2. Вы черезчур сильно обобщаете свои рассуждения - следуя этому пути можно всегда предположить, что в одной из этих процедур есть и традиционный побочный эффект (прямое изменение значения глобальной переменной не передающейся через интерфейс подпрограммы).. а раз так то и задача не имеет смысла...
1. А я считаю, по этой же причине. Такая "функция" является тривиально чистой, она тождественная, потому что "результат" здесь это само ссылочное значение "заяц" (а не "заяц^") равное ссылочному аргументу "заяц" (если конечно "функция" не меняет его значение).
2. Изменение значения глобальной переменной даже передающейся через интерфейс подпрограммы (как параметр-переменная) тоже является побочным эффектом. У функции без побочного эффекта не должно быть VAR/OUT-параметров.
Почему задача не имеет смысла? Не обязательно использовать функции. Требования использовать функции без побочного эффекта тоже нет в условии задачи. Только минимизация числа извлечений и сохранение промежуточных результатов.
Любое изменение глобального окружения функции внутри неё является побочным эффектом, будь-то ввод/вывод, прямое или косвенное изменение глобальной переменной.
Если функция хоть как-то влияет на изменение глобального (по отношению к ней) состояния программы, то эта функция имеет побочный эффект.
Если так рассуждать - то Хаскели и проч. "чистые" ФЯВУ - не только таковыми не являются - но потенциально гораздо более опасны чем императивные ЯП.
"Чистые" ФЯВУ по сути это одни выражения, и никаких операторов.
Если мы хотим изменить "глобальное окружение" в "чистом" ФЯВУ (например, записать в лог), мы должны влючить значение этого "глобального окружения" в параметр функции, а затем вывести новое значение этого "глобального окружения" как компоненту результата.
-
Не знаю, говори ли кто или нет в этой ветке, неохота искать.
Я так понимаю, что Пётр озаботился такой ситуацией.
В теле цикле может быть несколько точек, где условие цикла может стать ложным. Например, имея while (A and B and C), в определённых точках тела цикла, там где фиксируются окончательно значения условий A, B,C. Если одно из этих условий становится ложным, то остальное в теле цикла как бы уже можно и не исполнять. Вот и появился соблазн синтаксически это дело оформить, размазав условие while по телу цикла.
-
Да ладно Вам, у каждого свои тараканы, одному нужны инварианты, другой носится с циклом Дейкстры, третьему нужна выразительность, четвертому "только хардкор", пятому эффективное решение, ...
Так что и этот вариант ничуть не более извращенный, чем другие.
Тараканы мне не интересуют, у меня критерий только один - работает инструмент или нет. Поэтому я всегда прошу приводить примеры.
В вашем варианте нет разницы игла == null или нет. Делаем выводы об успешности...
А фантазию не надо ограничивать, тут цель - чтобы в голове была ясность. Потом просто транслируем на целевой язык.
-
Не знаю, говори ли кто или нет в этой ветке, неохота искать.
Я так понимаю, что Пётр озаботился такой ситуацией.
В теле цикле может быть несколько точек, где условие цикла может стать ложным. Например, имея while (A and B and C), в определённых точках тела цикла, там где фиксируются окончательно значения условий A, B,C. Если одно из этих условий становится ложным, то остальное в теле цикла как бы уже можно и не исполнять. Вот и появился соблазн синтаксически это дело оформить, размазав условие while по телу цикла.
Ровно об этом я и сказал здесь http://oberspace.dyndns.org/index.php/topic,425.msg13272.html#msg13272
Пожалуй, я сделал ошибку в том, что закопал самый главный пост внутри темы.
-
Не знаю, говори ли кто или нет в этой ветке, неохота искать.
Я так понимаю, что Пётр озаботился такой ситуацией.
В теле цикле может быть несколько точек, где условие цикла может стать ложным. Например, имея while (A and B and C), в определённых точках тела цикла, там где фиксируются окончательно значения условий A, B,C. Если одно из этих условий становится ложным, то остальное в теле цикла как бы уже можно и не исполнять. Вот и появился соблазн синтаксически это дело оформить, размазав условие while по телу цикла.
Ровно об этом я и сказал здесь http://oberspace.dyndns.org/index.php/topic,425.msg13272.html#msg13272
Пожалуй, я сделал ошибку в том, что закопал самый главный пост внутри темы.
Ну, как я уже говорил, эта проблема в функциональщине решается монадами. Та же maybe например. То есть там этой проблемы нет в принципе.
-
Там ровно та же проблема, цепочка в maybe не делает exit из себя, а выполняется целиком.
-
Автор при этом думал "как бы мне извратиться?"
А мне кажется, автор думал "как бы обеспечить правильное постусловие?" ;)
-
Он таких слов не знает.
-
Там ровно та же проблема, цепочка в maybe не делает exit из себя, а выполняется целиком.
Вычисление цепочки выражений в монаде Maybe обрывается сразу же, как только одно из выражений в этой цепочке оказывается неуспешным.
Целиком же она выполняется только, если все выражения в ней вычислены успешно.
-
В вашем варианте нет разницы игла == null или нет. Делаем выводы об успешности...
а, ну да, ilovb вынес эту проверку из цикла. но это ж не проблема - вернуть её на место, как в исходном вашем варианте - а нефиг было картинки вставлять вместо текста. Видимо Пётр такую диверсию сделал чтобы никто не смог скопипастить )
-
Там ровно та же проблема, цепочка в maybe не делает exit из себя, а выполняется целиком.
Вычисление цепочки выражений в монаде Maybe обрывается сразу же, как только одно из выражений в этой цепочке оказывается неуспешным.
Это вам только так кажется. А на самом деле до конца цепочки идет проверка на Nothing.
-
Автор при этом думал "как бы мне извратиться?"
А мне кажется, автор думал "как бы обеспечить правильное постусловие?" ;)
Видимо, trurl под автором имел в виду себя, а не ilovb, как я.
Ну тогда приведите инвариант вашего цикла.
Как никак, он входит в правильное постусловие.
-
Там ровно та же проблема, цепочка в maybe не делает exit из себя, а выполняется целиком.
Нет, целиком не выполняется. Как раз делается проверка между звеньями цепочки.
-
Там ровно та же проблема, цепочка в maybe не делает exit из себя, а выполняется целиком.
Вычисление цепочки выражений в монаде Maybe обрывается сразу же, как только одно из выражений в этой цепочке оказывается неуспешным.
Это вам только так кажется. А на самом деле до конца цепочки идет проверка на Nothing.
Кто Вам такое сказал? о_О
data Maybe a = Nothing | Just a
deriving (Eq, Ord, Generic)
instance Monad Maybe where
(Just x) >>= k = k x
Nothing >>= _ = Nothing
(Just _) >> k = k
Nothing >> _ = Nothing
return = Just
fail _ = Nothing
Как видно, как только результатом очередного выражения в цепочке Maybe окажется Nothing, всё выражение обрывается и возвращается Nothing -- никакого продолжения вычислений в стратегии монады Maybe не предусмотрено.
Вы явно путаете с чем-то другим, возможно с монадой IO...
-
Кто Вам такое сказал? о_О
Мне такое сказали авторы книги Real World Haskell http://book.realworldhaskell.org/read/monads.html
Note, though, that the chain is not completely short-circuited. Each (>>=) or (>>) in the chain will still match a Nothing on its left, and produce a Nothing on its right, all the way to the end. It's easy to forget this point: when a computation in the chain fails, the subsequent production, chaining, and consumption of Nothing values is cheap at runtime, but it's not free.
И обманули, гады >:(
-
Кто Вам такое сказал? о_О
Мне такое сказали авторы книги Real World Haskell http://book.realworldhaskell.org/read/monads.html
Note, though, that the chain is not completely short-circuited. Each (>>=) or (>>) in the chain will still match a Nothing on its left, and produce a Nothing on its right, all the way to the end. It's easy to forget this point: when a computation in the chain fails, the subsequent production, chaining, and consumption of Nothing values is cheap at runtime, but it's not free.
И обманули, гады >:(
Какой-то странный абзац, и не удивительно, что он вызвал там кучу удивлённых комментов.
Вот простейший тест:
mbDiv :: Integer -> Integer -> Maybe Integer
x `mbDiv` 0 = Nothing
x `mbDiv` y = Just $ x `div` y
resultOk = do
x <- 10 `mbDiv` 5
y <- 10 `mbDiv` 0 -- тут возвращается Nothing
z <- return $ Just $ 10 `div` 0 -- и до сюда вычисление не доходит
return z
resultBad = do
x <- 10 `mbDiv` 5
y <- 10 `mbDiv` 1 -- тут возвращается Just 10
z <- return $ Just $ 10 `div` 0 -- и здесь падаем по делению на ноль
return z*Main> resultOk
Nothing
*Main> resultBad
Just (Just *** Exception: divide by zeroВсё нормально, монада Maybe работает правильно, как и должна.
-
Как-то я переусложнил тестовый пример, так проще:
result = do
x <- Just 'x'
y <- Nothing
z <- Just 'z'
return zMain> result
Nothing
-
Ведь и в самом первом варианте Алмазова достаточно вместо внутреннего if игла # NIL then break вынести & (игла = NIL) в условие цикла.
Чет я пропустил. Оказывается уже упоминалось до меня :)
-
Функция без побочных эффектов (она же "чистая") - это функция, которая для одних и тех же аргументов всегда возвращает один и тот же результат и сама не вызывает функций с побочными эффектами.
Непонятно, зачем только эта рекурсивная добавка в определении.
Такая функция будет вносить (вообще говоря) побочные эффекты в выражения в которых она вызывается.
И вы сделали акцент на влиянии внешнего окружения на функцию (на ее результат), таком влиянии, чтобы ее результат зависел только от значения ее фактических параметров, то есть не зависел:
- от неявно импортиремых (всеми вызываемыми в ней процедурами) внешних переменных (но допустима зависимость от констант и других процедур),
- от разыменованных переменных взятых от ссылочных компонент ее параметров,
- от ссылочных значений созданных при ее вызове.
В то время как побочный эффект есть влияние функции на внешнее окружение.
Все остальные предложенные "разновидности" - не знаю для чего могут понадобиться.
Для того чтобы сделать все выражения без побочных эффектов, они и понадобятся.
Если все функции всегда не изменяют внешнее окружение, а операторы не выдают значений и тем самым не входят в выражения (хороший, годный язык), то все выражения не имеют побочных эффектов.
Я за то, чтобы все функции (а значит и выражения) обязательно были без побочных эффектов, и это проверялось компилятором консервативными методами (по структуре ее ввода-вывода). Конечно, некоторые функции без побочных эффектов будут при этом отсеиваться, те, чья проверка их безпобочности будет неконсервативна, а то может быть и вовсе неразрешима.
А вот условие чистоты функций для меня не обязательно, хотя его проверку тоже можно втиснуть в консервативные рамки и сделать обязательной при компиляции.
Применительно к данной задаче чистая функция могла бы возвращать структуру/кортеж. с найденным состоянием.
Только следует быть осторожным при возвращении ссылки на структуру или структуры со сслылочными компонентами. При одних и тех же аргументах, функция может выдавать структурно одинаковые результаты, но с разными значениями ссылок, т.е. формально другой результат.
Тогда для чистоты придеться явно вносить в вызов функции ссылочные компоненты ее результата - через фактические параметры.
Следует также помнить, что разыменованные ссылочные компоненты результата функции в сам результат уже не входят и не существенны для вопроса одинаковости и различности результатов функции. В частности, если результат функции есть ссылка, то ее результат ограничивается лишь этим ссылочным значением. Это же относится и к ее аргументам.
Кроме того, что функция может быть чистой и грязной (с побочными эффектами), она ещё может быть тотальной (гарантированно успешно завершится) и не тотальной (может выдать ошибку или никогда не завершиться).
Например, f(x)=5/x может выдать деление на ноль, и хоть она и является чистой, тотальной она не является.
Выход из функции по ошибке не является побочным эффектом, т.к. находится вне среды исполнения программы, т.е. вне видимости языка.
Если параметр-переменная "заяц" здесь ссылочная, то присвоение "результата" функции переменной заяц^, это само по себе глобальный эффект.
1. Я не считаю конкретно это изменение ПОБОЧНЫМ эффектом - хотя конечно это изменяет глобальное окружение
2. Вы черезчур сильно обобщаете свои рассуждения - следуя этому пути можно всегда предположить, что в одной из этих процедур есть и традиционный побочный эффект (прямое изменение значения глобальной переменной не передающейся через интерфейс подпрограммы).. а раз так то и задача не имеет смысла...
1. А я считаю, по этой же причине. Такая "функция" является тривиально чистой, она тождественная, потому что "результат" здесь это само ссылочное значение "заяц" (а не "заяц^") равное ссылочному аргументу "заяц" (если конечно "функция" не меняет его значение).
2. Изменение значения глобальной переменной даже передающейся через интерфейс подпрограммы (как параметр-переменная) тоже является побочным эффектом. У функции без побочного эффекта не должно быть VAR/OUT-параметров.
Почему задача не имеет смысла? Не обязательно использовать функции. Требования использовать функции без побочного эффекта тоже нет в условии задачи. Только минимизация числа извлечений и сохранение промежуточных результатов.
Любое изменение глобального окружения функции внутри неё является побочным эффектом, будь-то ввод/вывод, прямое или косвенное изменение глобальной переменной.
Если функция хоть как-то влияет на изменение глобального (по отношению к ней) состояния программы, то эта функция имеет побочный эффект.
Если так рассуждать - то Хаскели и проч. "чистые" ФЯВУ - не только таковыми не являются - но потенциально гораздо более опасны чем императивные ЯП.
"Чистые" ФЯВУ по сути это одни выражения, и никаких операторов.
Если мы хотим изменить "глобальное окружение" в "чистом" ФЯВУ (например, записать в лог), мы должны влючить значение этого "глобального окружения" в параметр функции, а затем вывести новое значение этого "глобального окружения" как компоненту результата.
1. По всей видимости разница. в восприятии.. вы трактуете данную ситуацию как использование чистой функции вообще... я как использование функции без побочного эффекта в данной задаче... скорее всего неправ я...
2. С чего бы это (точнее не всегда) - если речь идет о классическом (пошаговом, детерменированном) алгоритме в однозадачной системе то по возвращаемое функцией в ссылочном значении эквивалентно чистому присваиванию (а возможные переприсваивания внутри функции не влекут изменения в глобальном окружении) - можно конечно более точно привести необходимые и достаточные условия для этого.. но - см. п1.
3. Я воспринял задачу так - как необходимость использовать функцию не содержащую побочный эффект - причем эффект вынужденный (следующий из паттерна решения основной задачи но не родственный природе самой функции).
4.Я имел ввиду другое.. реально программа в функциональном яп транслируется в си.. и далее... который вполне императивен.. - вы можете сказать когда создаются фактические динамические переменные , а когда нет?.. между тем согласно вашей же фразе (если я правильно ее понял) любое создание динамической переменной есть побочный эффект... отсюда вывод фяву- в общем случае языки с неконтролируемым побочным эффектом ...
-
Ведь и в самом первом варианте Алмазова достаточно вместо внутреннего if игла # NIL then break вынести & (игла = NIL) в условие цикла.
Чет я пропустил. Оказывается уже упоминалось до меня :)
Илье не помогло гадание на драконной гуще и он вляпался в новое ...
-
А что, собственно, не так?
trurl увидел сразу этот вариант, который я бы тоже написал с нуля, если бы столкнулся с такой задачей - и мозги не были бы забиты начальной вашей постановкой :)
-
Пётр, у меня к Вам вопрос, как к человеку, знания которого я уважаю.
Понимаете, когда долгое время кто-то тебе говорит "вот это хрень", но при этом не вдаётся в аргументацию (а ты никак не можешь игнорировать мнение данного человека), то интересен вопрос: а смотрел ли человек твоим взглядом на обсуждаемый предмет, может ли он объяснить, где и в каком месте ты что-то не так видишь?
Я не являюсь "фанатом ДРАКОНа" или даже постоянно где-то его использующим (хотя нишу ему вижу) и меня он вообще интересует с другой точки зрения, чем большинство "драконщиков" - они, как и большинство программистов, не мыслят о программе в терминах состояний и утверждений о состояниях, а я мыслю... И я вижу, что графовое представление мне несёт доп. информацию, которую не несёт напрямую текст (которую надо поднимать в голове из него). Совершенно строгую, математическую информацию. Не говоря про то, что делает возможным какие-то совершенно логически строгие топологии управления, которые хрен выразишь текстом. Я, собственно, это излагал и на форумах, и в статьях.
Я вот чего не понимаю: Вы или не понимаете, о чём я говорю (не видите, какую информацию я получаю из схемы и другим предлагаю), или считаете, что это неважно, или считаете, что это вообще "неправильная информация", или что..?
Вы считаете криминальным использование графовой формы, например, в теории схем программ (схем не в визуальном смысле, а в смысле моделей, на которых оптимизирующие компиляторы строятся и проч.)? В новосибирских работах типа В. Е. Котов, В. К. Сабельфельд Теория схем программ М.: Наука, 1991. Или работы Касьянова и Евстигнеева. Это же классика теории программирования. Почему применение "каких-нибудь" схем Янова для анализа свойств программ - не криминал, а применение ДРАКОНа - да? Или Вы считаете, что "всё это хрень"?
-
Вот что интересует в ДРАКОНе - возможности в этом плане:
-
А что, собственно, не так?
trurl увидел сразу этот вариант, который я бы тоже написал с нуля, если бы столкнулся с такой задачей - и мозги не были бы забиты начальной вашей постановкой :)
"Не так"?!
Ну, мля, как дворниками пообщался.
Сказано же, тело цикла выполняется лишний раз. Здесь это "i=i+1".
Но тело цикла может быть несколько другим.
Н-р, "Достать очередной сундук со дна Марианской впадины".
Или "Уничтожить протоколы разборки сундука, как не оправдавшего надежд, на то что там окажется игла".
Но нашим пейсателям все равно.
-А, давайте ткнем проверку игла <> null в заголовок цикла?
-Давайте! Не изврата ради, а токмо "правильного постусловия" для.
После общения с такими гражданами хочется вымыть руки.
-
Вы считаете криминальным использование графовой формы, например, в теории схем программ (схем не в визуальном смысле, а в смысле моделей, на которых оптимизирующие компиляторы строятся и проч.)? В новосибирских работах типа В. Е. Котов, В. К. Сабельфельд Теория схем программ М.: Наука, 1991. Или работы Касьянова и Евстигнеева. Это же классика теории программирования. Почему применение "каких-нибудь" схем Янова для анализа свойств программ - не криминал, а применение ДРАКОНа - да? Или Вы считаете, что "всё это хрень"?
Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.
-
Для полноты картины ещё добавлю Р-схему модифицированного варианта моего решения. Модификация в плане сокращения записи.
$==========================================================================$
! !
!НЕ Нашли И !
!ЕСТЬ(сундуки) ПУСТО(заяц) !
!------------->$---------------------------------------------------------->!
ВЗЯТЬ(сундук) ! !
ЗАЯЦ(сундук) ! ПУСТО(утка) !
!--------->$----------------------------------------------->!
УТКА(заяц)! !
! ПУСТО(яйцо) !
!--------->$------------------------------------>!
ЯЙЦО(утка)! !
! ПУСТО(игла) !
!--------->$------------------------->!
ИГЛА(яйцо)! !
! ПУСТО(смерть)!
!----------->$------------>!
СМЕРТЬ(игла)! !
! !
!------------>!
Нашли := ДА
-
А что, собственно, не так?
"Не так"?! ... Но нашим пейсателям все равно.
Могу тоже сказать: А что, собственно, не так? :)
Идея размазать while по телу цикла (while+andwhile) не состоятельна по выводу самого автора (Петра) из-за засад.
(Мне она тоже никакого доверия не вызывает.)
Без exit из циклов while можно вполне обходиться.
А придумать можно что угодно усугубляющее. Но тогда и решения должны быть соответствующими.
-
А придумать можно что угодно усугубляющее. Но тогда и решения должны быть соответствующими.
Лично для себя я решил этот вопрос давно..ЕСЛИ ЭТО ВОЗМОЖНО -Я ОРИЕНТИРУЮСЬ НА КОНКРЕТНУЮ ЗАДАЧУ
-
"Не так"?!
Ну, мля, как дворниками пообщался.
Сказано же, тело цикла выполняется лишний раз. Здесь это "i=i+1".
Но тело цикла может быть несколько другим.
Вот пусть оно сначала будет несколько другим, чтобы были веские причины уходить от варианта, который наиболее "прописан" для применения в неотягощённом "марианскими впадинами" случае.
Раскатывать условия из общего условия цикла куда-то в его внутренности - это нужны очень серьёзные агрументы.
Вы в исходном сообщении привели один: операции получения уток-иголок дорогие. Вам и дали решение для этого случая.
Про дороговизну i := i + 1 речи не было.
-
Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.
При чём тут публика? Это проблемы публики, что ей там "по барабану" логические свойства схемы. Мне - нет и меня именно этот аспект интересует.
Если есть просто конкретная нотация (конкретная топология графов). И конкретные примеры выражения на ней.
Если Вы не можете обсуждать вопрос "по существу", без своей личной идиосинкразии, то это Ваша проблема.
-
Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.
Между прочим, три года назад в Новосибирском академгородке я обсуждал ДРАКОН с В. Н. Касьяновым (а затем немного переписывались по этой теме).
Его очень интересует всё, что связано со сводимыми (они же аранжируемые) графами и их применением для анализа свойств программ - он считает, что это недоисследованное и перспективное направление.
-
"Не так"?!
Ну, мля, как дворниками пообщался.
Сказано же, тело цикла выполняется лишний раз. Здесь это "i=i+1".
Но тело цикла может быть несколько другим.
Вот пусть оно сначала будет несколько другим, чтобы были веские причины уходить от варианта, который наиболее "прописан" для применения в неотягощённом "марианскими впадинами" случае.
Раскатывать условия из общего условия цикла куда-то в его внутренности - это нужны очень серьёзные агрументы.
Вы в исходном сообщении привели один: операции получения уток-иголок дорогие. Вам и дали решение для этого случая.
Про дороговизну i := i + 1 речи не было.
Ну, в таком случае, может, хоть вы напишете "правильное постусловие" (http://oberspace.dyndns.org/index.php/topic,425.msg13531.html#msg13531). А то trurl заглох, по своему обыкновению.
Только тогда текст должен присутствовать не в форме "это надо перенести сюда", а полностью.
В конце концов, я же предупреждал, что решение должно быть "образцово-показательно".
-
Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.
Между прочим, три года назад в Новосибирском академгородке я обсуждал ДРАКОН с В. Н. Касьяновым (а затем немного переписывались по этой теме).
Его очень интересует всё, что связано со сводимыми (они же аранжируемые) графами и их применением для анализа свойств программ - он считает, что это недоисследованное и перспективное направление.
Я конечно во всем этом далеко не спец, но я не очень понимаю, при чем тут дракон? Ведь дракон по сути, является всего лишь еще одним синтаксисом, точнее даже не синтаксисом, а визуализации одного синтаксиса, причем без четко оисанной семантики под этим синтаксисом. Это (метод визуализации) в ряде случаев может действительно здорово поднять наглядность алгоритма (а в другом ряде случаев сильно запутать читателя), но при чем тут анализ графов?
По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис. У него неплохо описана семантика (на порядок лучше драконовых). При этом язык маленький, и анализатор строящий по исходнику нужный граф будет написать просто. Именно поэтому моя сестра например выбрала для своих исследований в качестве первого подопытного кролика именно Оберон (а затем Lua).
А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).
-
Если Вы не можете обсуждать вопрос "по существу", без своей личной идиосинкразии, то это Ваша проблема.
Вы правы, я не могу обсуждать вопрос "по существу".
Примерно так же, как врачи не смогут обсуждать "по существу" вопрос "Надо ли мыть руки перед операцией или достаточно помолиться".
-
А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).
Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.
-
А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).
Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.
Кстати, а чем Дракон принципиально от оной блок-схемы отличается?
-
Кстати, а чем Дракон принципиально от оной блок-схемы отличается?
Вот это уже не ко мне :D
-
Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.
Если Вы не понимаете разницы между графом произвольной запутанности и графом с ограниченной топологией, между рисунком, в котором выбор, "куда дальше повести линию" и "куда положить вот это - справа или слева" - и между строгой конструкцией, которая диктует однозначно размещение на плоскости и является конкретным классом графов, то это - баранья упёртость, Пётр. На этом диагнозе и покончим. Все Ваши рассуждения о ДРАКОНе гроша ломаного не стоят, потому что Вы хотите понимаеть, о чём веду речь я. (А не масса бухгалтеров вокруг ДРАКОНа). То ли намеренно придуриваетесь, то ли от своей идиосинкразии у Вас выключается разумное восприятие ... :)
-
На этом диагнозе и покончим.
Разумно.
Ну а с "правильным постусловием" как?
А то вспоминается Тарас Бульба: "Ну что, сынку, помогли тебе твои ляхи графы?"
-
По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис.
С Обероном всё ясно. Его граф - структурный в классическом понимании, т.е. линейно-блочный (последовательность блоков с одним входом и одним выходом).
А интересна более сводобная топология сводимых графов (в которых у любой вершины есть только одна последовательность ведущих в неё доминаторов). ДРАКОН относится именно к этой топологии. Паронджанов определил её конструктивно (в терминах начального объекта и допустимых над ним операций, а дальше говорится, что "всё множество правильных схем - это всё множество, которое можно получить применением этих операций).
А если определять аксиоматически, то это, оказывается, сводимый граф.
Я же привёл там выше ссылку на статью, где это разбиралось.
-
.... помогли тебе твои...
Эх, и не говорите :) нет от них никаких доходов, интерес один...
Ну, в таком случае, может, хоть вы напишете "правильное постусловие" (http://oberspace.dyndns.org/index.php/topic,425.msg13531.html#msg13531). А то trurl заглох, по своему обыкновению.
Только тогда текст должен присутствовать не в форме "это надо перенести сюда", а полностью.
В конце концов, я же предупреждал, что решение должно быть "образцово-показательно".
Если я буду составлять этот цикл с нуля, с полными рассуждениями, то буду делать это так.
Итак, наш метод поиска: последовательный просмотр элементов последовательности, пока не будет обнаружена игла или не конец последовательности.
Целевое постусловие:
в последнем просмотренном сундуке обнаружена игла или нет непросмотренных сундуков
(Проверяем, что учли пограничные случаи: очевидно, что "все сундуки просмотрены и в последнем найдена игла" тоже покрыто нашим постусловием, также учитываем случай пустой последовательности сундуков - сначала я написал "все сундуки просмотрены", но заменил на более однозначное к этому случаю "нет непросмотренных сундуков").
Начнём с определения варьируемых переменных.
Заведём для последовательного просмотра переменную i, пусть она хранит номер первого ещё не просмотренного сундука.
Если бы у нас не было вложенности и был простой просмотр сундуков, то мы бы этой переменной и ограничились. Но мы понимаем, что найденную иглу надо запоминать и вводим переменную "игла", смысл которой - хранить обнаруженную иглу. А так как из нашего метода поиска вытекает, что она может быть найдена только в последнем просмотренном сундуке (а в остальных её нет), то более строго скажем: "игла" хранит результат поиска иглы в i-1-м сундуке или NIL, если i = 0.
Инвариант:
(i > 0) & (i <= len) & (игла = результату поиска иглы в i-1-м сундуке) & (в интервале [0, i-1) нет игол) OR (i = 0) & (игла = NIL)
После введения переменных и формулировки инварианта мы можем более строго сформулировать постусловие нашего поиска:
(игла # NIL) & (игла обнаружена в i-1-м сундуке) & (в интервале [0, i-1) игол не было обнаружено) OR (игла = NIL) & (в интервале [0, len) игл не было обнаружено)
Далее придумывается условие завершения цикла, которое в конъюнкции с инвариантом даст нам такое постусловие:
(игла # NIL) OR (i = len)
Отсюда сам цикл, с обратным условием продолжения:
i := 0;
WHILE (игла = NIL) & (i # len) DO
искать иглу в i-м cундуке;
INC(i)
END
-
По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис.
С Обероном всё ясно. Его граф - структурный в классическом понимании, т.е. линейно-блочный (последовательность блоков с одним входом и одним выходом).
А интересна более сводобная топология сводимых графов (в которых у любой вершины есть только одна последовательность ведущих в неё доминаторов). ДРАКОН относится именно к этой топологии. Паронджанов определил её конструктивно (в терминах начального объекта и допустимых над ним операций, а дальше говорится, что "всё множество правильных схем - это всё множество, которое можно получить применением этих операций).
А если определять аксиоматически, то это, оказывается, сводимый граф.
Я же привёл там выше ссылку на статью, где это разбиралось.
По моему, ты забываешь про вызовы функций. Без них анализ не полон. Сама по себе последовательность statement'ов достаточно скучна и не интересна.
Впрочем, ту статью надо конечно внимательно прочитать будет. Тогда вместо гадания смогу выдать обоснованную критику/анализ.
-
Если я буду составлять этот цикл с нуля, с полными рассуждениями, то буду делать это так.
...
Долго не мог заставить себя прочитать все внимательно до конца. Но все-таки "осилил".
Если оценивать ход решения задачи и полученный результат, то я бы поставил, конечно, "неуд".
Тем не менее, могу сказать, что не все безнадежно. (А поначалу показалось, что безнадежно).
Нет, определенно, есть проблеск надежды.
-
Тем не менее, могу сказать, что не все безнадежно. (А поначалу показалось, что безнадежно).
Нет, определенно, есть проблеск надежды.
Да ну... Тогда я возьму с полки пиражок и буду ждать разбора от сенсея... Надеюсь, что встречно будет также потрачено время на эту задачу.
-
Товарищи, да о чем вы рассуждаете. Обычный линейный поиск.
Илья, вот в этом вашем шаблоне и заключен весь алгоритм:
i := 0;
WHILE (игла = NIL) & (i # len) DO
искать иглу в i-м cундуке;
INC(i)
END
Все что кроме - это операция на гландах через задницу.
-
Если лишнее сравнение в заголовке напрягает, то вот вариант:
http://oberspace.dyndns.org/index.php/topic,425.msg13082.html#msg13082
Тот же линейный поиск + оптимизация
Круче уже некуда.
Что тут формально строить то?
-
Ну, Борис, тут надо понимать, что никто не предлагает такой цикл каждый раз так выводить.
Просто это самотест, понимаем ли свойства циклов или нет.
Мозг сам будет быстро прокручивать многие вещи, когда есть навык разбирать доказательно.
Т.е. тут просто критерий "могу рассказать строго = знаю точно свойства своего кода" или "не могу рассказать строго = возможно, что-то упускаю".
-
Обычный линейный поиск.
И он не типичный. В распространённом случае поисков в последовательностях у нас второй конъюнкт в условии - это проверка i-го элемента (она как раз и оказывается под охраной первого конъюнкта). Здесь же участвует игла из предыдущего сундука.
-
Тем не менее, могу сказать, что не все безнадежно. (А поначалу показалось, что безнадежно).
Нет, определенно, есть проблеск надежды.
Да ну... Тогда я возьму с полки пиражок и буду ждать разбора от сенсея... Надеюсь, что встречно будет также потрачено время на эту задачу.
Не, не будет.
Все, что нужно, было сказано многократно.
Дальше - только своим умом.
Даже, если бы было время.
-
Но тело цикла может быть несколько другим.
Вот пусть оно сначала будет несколько другим
Вот и пусть будет ;)
-
Спор какой-то странный, надо усугубить :)
Вот, если взять "кошерный" линейный поиск: WHILE ~E(i) & ~F(i) DO ... END
E и F - это лог.выражения, первое определяет условие завершения по причине исчерпания возможных итераций,
а второе - условие достижения цели. Параметр i - это номер итерации.
По окончании цикла имеем постусловие: E OR F и при этом E=~F
(на всякий случай сразу скажу - считаем, что за пределами допустимых i F(i)=FALSE )
А обсуждаемый Кащеевский цикл - он из таких: WHILE ~E(i) & ~F(i-1) DO ... END
По окончании которого, кстати, уже не будет выполняться F=~E. (Надо просто иметь это ввиду.)
Вполне довольно распространённая ситуация. Не зря же Пётр озаботился приведением этого цикла к "кошерному" линейному поиску. Если я, конечно, в адеквате :)
Здесь естественно в условии WHILE вместо F(i-1) использовать переменную, вычисляемую на предыдущей итерации. Та же самая 'игла' , например.
-
PS.
Надеюсь, что в последней строчке послания, что касаемо "вместо F(i-1) ... 'игла' ... " не будет воспринято буквально :)
-
Вот, если взять "кошерный" линейный поиск: WHILE ~E(i) & ~F(i) DO ... END
E и F - это лог.выражения, первое определяет условие завершения по причине исчерпания возможных итераций,
а второе - условие достижения цели. Параметр i - это номер итерации.
По окончании цикла имеем постусловие: E OR F и при этом E=~F
(на всякий случай сразу скажу - считаем, что за пределами допустимых i F(i)=FALSE )
А обсуждаемый Кащеевский цикл - он из таких: WHILE ~E(i) & ~F(i-1) DO ... END
По окончании которого, кстати, уже не будет выполняться F=~E. (Надо просто иметь это ввиду.)
Вполне довольно распространённая ситуация. Не зря же Пётр озаботился приведением этого цикла к "кошерному" линейному поиску. Если я, конечно, в адеквате :)
Здесь естественно в условии WHILE вместо F(i-1) использовать переменную, вычисляемую на предыдущей итерации. Та же самая 'игла' , например.
Да неестественно, в том то и дело.
Еще раз могу констатировать, что мало кто (if any) понял, в чем состоит задача. А она состояла в изобретении выразительных средств, которые бы не вели к выносу мозга в виде лишней итерации. Это линейный поиск? Да. Если бы не было запрета на упрятывание куска в функцию, никто бы в этом и не усомнился. И большего эта задача не заслуживает.
Такое средство было показано. (http://oberspace.dyndns.org/index.php/topic,425.msg13272.html#msg13272)
И E=~F после цикла.
//найти первый комплект с иглой
игла = null; //перенес по сравнению с оригиналом
i=0;
while (i != сундуки.Length) {
заяц = ЗАЯЦ(сундуки[i]);
if (заяц != null) {
утка = УТКА(заяц);
if (утка != null) {
яйцо = ЯЙЦО(утка);
if (яйцо != null) {
игла = ИГЛА(яйцо);
}
}
}
andwhile (игла == null);
i = i + 1;
}
После окончания цикла (i == сундуки.Length) OR (игла != null)
-
Еще раз могу констатировать, что мало кто (if any) понял, в чем состоит задача. А она состояла в изобретении выразительных средств, которые бы не вели к выносу мозга в виде лишней итерации.
С выразительными средствами ясно, но и выноса мозга нет. IMHO.
Сплошь и рядом циклы такого рода:
find:=FALSE
WHILE E(i) & ~find DO ... ; find:=бла-бла; i:=i+1 END
Если уж очень хочется, чтобы получилось как в "кошерном" линейном поиске, достаточно вместо просто 'i:=i+1' написать 'IF ~find THEN i:=i+1 END' или после цикла вставить 'IF find THEN i:=i-1 END' то получим как в "кошерном" линейном поиске. Только зачем?
А вот то, что в том цикле, где ищется недостача, в тех вариантах реализации, в которых после окончания цикла переменные (заяц, утка, яйцо,игла) могут быть "несогласованы", - это, если придираться, не есть гуд.
Завершился цикл при обнаружении отсутствия :) утки, а яйцо и игла остались с предыдущей итерации не null.
Но эту уже другая песня, а голос кажись сел :)
-
Еще раз могу констатировать, что мало кто (if any) понял, в чем состоит задача. А она состояла в изобретении выразительных средств, которые бы не вели к выносу мозга в виде лишней итерации.
Гипотетическая конструкция
while (cond1) {
stmt_seq1;
andwhile (cond2);
stmt_seq2;
}смотрится крайне неорганично для сишного синтаксиса (имхо).
Тогда уж хотя бы так:
while (cond1) {
stmt_seq1;
} andwhile (cond2) {
stmt_seq2;
}Правда, в этом случае переменные, определённые в stmt_seq1, не будут доступны в stmt_seq2, что тоже не есть гуд...
С другой стороны, Ваш вариант крайне легко симитировать простым сишным макросом:
#define andwhile(cond) if (!(cond)) break;Это к слову о нужности или ненужности макросов, даже таких простых, как сишные. Не нужно ждать, когда разработчики языков добавят нужную вам конструкцию -- добавьте её сами!
-
Это к слову о нужности или ненужности макросов, даже таких простых, как сишные. Не нужно ждать, когда разработчики языков добавят нужную вам конструкцию -- добавьте её сами!
Тык давайте Немерлееть -- Петр- в эту сторону смотреть не пробовали? - на шарп похоже.. :)
-
Это к слову о нужности или ненужности макросов, даже таких простых, как сишные. Не нужно ждать, когда разработчики языков добавят нужную вам конструкцию -- добавьте её сами!
Тык давайте Немерлееть -- Петр- в эту сторону смотреть не пробовали? - на шарп похоже.. :)
Да тут не нужно немерли, достаточно просто функциональщины без макросов даже. То есть достаточно языка высокого уровня, позволяющего создавать свои абстракции.
-
Это к слову о нужности или ненужности макросов, даже таких простых, как сишные. Не нужно ждать, когда разработчики языков добавят нужную вам конструкцию -- добавьте её сами!
Тык давайте Немерлееть -- Петр- в эту сторону смотреть не пробовали? - на шарп похоже.. :)
Алмазов терпеть не может макросы вообще и немерле в частности )))
-
Да тут не нужно немерли, достаточно просто функциональщины без макросов даже. То есть достаточно языка высокого уровня, позволяющего создавать свои абстракции.
При чём здесь абстракции? достаточно замыканий -- а они даже в древнем смоллтоке есть ))
-
Да тут не нужно немерли, достаточно просто функциональщины без макросов даже. То есть достаточно языка высокого уровня, позволяющего создавать свои абстракции.
Не пойдет... ибо он транслируется в х.з. - а Петр о производительности радеет и без компромиссов :)
-
Это к слову о нужности или ненужности макросов, даже таких простых, как сишные. Не нужно ждать, когда разработчики языков добавят нужную вам конструкцию -- добавьте её сами!
Тык давайте Немерлееть -- Петр- в эту сторону смотреть не пробовали? - на шарп похоже.. :)
Алмазов терпеть не может макросы вообще и немерле в частности )))
тык макросы в Немерли это не макросы в Си... и потом, заметил я, что при удобном случае он приводит шарпейный код... а от туда до Немерли и рукой подать :D
-
Алмазов терпеть не может макросы вообще и немерле в частности )))
Первое верно, а второго я никогда не говорил.
Ибо ни хрена в них не понял.
-
Функция без побочных эффектов (она же "чистая") - это функция, которая для одних и тех же аргументов всегда возвращает один и тот же результат и сама не вызывает функций с побочными эффектами.
...
Такая функция будет вносить (вообще говоря) побочные эффекты в выражения в которых она вызывается.
Добавлю. Чистая, но с побочными эффектами, функция, в общем случае сделает выражения в которых она вызывается также и нечистыми. Значения этих выражений уже не будут задаваться значениями их designator-операндов - это если включить вызовы функций в выражения (express), а не в составные имена (designator).
Потому что, результат побочного изменения (такой функцией) значений внешних переменных (входящих в то же выражение, что и ее вызов) уже не обязан подчиняться требованию чистоты - нечистая функция не будет "для одних и тех же аргументов" всегда устанавливать одно и то же значение внешних designator-операндов.
2. С чего бы это (точнее не всегда) - если речь идет о классическом (пошаговом, детерменированном) алгоритме в однозадачной системе то по возвращаемое функцией в ссылочном значении эквивалентно чистому присваиванию (а возможные переприсваивания внутри функции не влекут изменения в глобальном окружении) - можно конечно более точно привести необходимые и достаточные условия для этого.. но - см. п1.
2. Присваивание глобальной переменной и есть побочный эффект, это оператор, а не функция. Динамическая анонимная переменная, на которую ведет ссылка, это глобальное окружение, и если ее (анонимной переменной) значение меняется - это побочный эффект.
В отличие от самой ссылки-результата (она не является глобальным окружением), чей анонимный вспомогательный объект расположен в стеке выражения, и к значению которой можно получить доступ только в рамках содержащего ее выражения. Когда ссылке-результату, при возврате из вызова функции, присваивается ссылочное значение, ссылающееся на ту или иную глобальную динамическую переменную (не изменяя их), это не создает побочного эффекта.
Надеюсь, вы имеете ввиду то же самое.
Но чтобы еще функция при этом была чистой (в вашей терминологии), необходимо чтобы ее ссылочное значение-результат совпадало со ссылочным значением одной из компонент ее аргументов либо равнялось NIL, иначе (если оно создается, или берется из компонент неявно импортируемых именованных переменных или из компонент анонимных динамических переменных) ссылочный результат невозможно вывести из значений аргументов.
3. Я воспринял задачу так - как необходимость использовать функцию не содержащую побочный эффект - причем эффект вынужденный (следующий из паттерна решения основной задачи но не родственный природе самой функции).
3. Использовать функции с побочным эффектом или не использовать, это вопрос конкретного решения, в том числе характера типизации данных (со ссылками или без). Я не заметил, чтобы автор задачи требовал безпобочности функций.
4. Я имел ввиду другое.. реально программа в функциональном яп транслируется в си.. и далее... который вполне императивен.. - вы можете сказать когда создаются фактические динамические переменные , а когда нет?.. между тем согласно вашей же фразе (если я правильно ее понял) любое создание динамической переменной есть побочный эффект... отсюда вывод фяву - в общем случае языки с неконтролируемым побочным эффектом ...
4. Это неважно куда там все транслируется и что там глобально-динамическое внутри создается, все это ненаблюдаемо средствами самого ФЯП, средствами среды его исполнения. Только создание динамической переменной рассматриваемого языка (а не переменной в его низкоуровневой реализации) является побочным эффектом.
-
Автор выдвигает несколько метафизические требования к минимализму числа выполненных действий, пытаясь ввести новые формы структурных операторов. Забывая, что внутри структурных операторов тоже ведь спрятаны определенные действия (передача управления, установка скрытых флагов).
Даже "лишняя" проверка булевой переменной для него уже неприемлема, хотя это всего лишь вспомогательный флаг для структуризации алгоритма. Надуманного повода со сложностью извлечения объектов будет недостаточно для такого сильного требования.
Если он хочет совсем без лишних проверок и действий, то ему, в общем случае, нужны неструктурные блок-схемы. По крайней мере, ему нужен новый структурный оператор без вложенных субоператоров (операторных параметров, которые и дают лишние проверки и действия). То есть, если поместить все элементы нужной блок-схемы на один структурный уровень - вся "спагетти" переходов между этими элементами блок-схемы перейдет в один структурный оператор со сложной передачей управления внутри себя.
Также, не следует ли объединить извлечение из вещи с проверкой ее внутренности на пустоту?
Это будет такая вот функция извлечения с побочным эффектом:
ИзвлечениеВещь (IN вещь; OUT субвещь) непустой: BOOLEAN(*post: "субвещь" - неопределена, если "вещь" определена, но пуста*)
а также функции перехода к первому и следующему сундуку:
Первый (OUT сундук) есть: BOOLEAN(*post: "сундук" - неопределен, если нет ни одного сундука*)
Следующий (VAR сундук) есть: BOOLEAN(*post: "сундук" - неопределен, если исходное значение "сундук" определено, но следующего за ним нет*)
Алгоритм воплощается в виде такого структурного оператора почти с чисто логическими параметрами-выражениями, то есть почти без операторных параметров.
existDeath := FALSE; (* смерть Кощея пока не найдена *)
BEGINIF (* переход к WHILEIF, если условие истинно (первый сундук есть), и выход из оператора, если ложно *)
First(сhest) (* проверка, что первый сундук есть, и переход к нему *)
WHILEIF (* переход к следующему UNTIL, если условие истинно (сундук пустой), и к следующему ELSIF, если ложно *)
~UnpackChest(сhest, hare) (* проверка, что в сундуке есть заяц и его извлечение *)
UNTIL (* выход из оператора, если условие истинно (следующего сундука нет), и возврат к WHILEIF, если ложно *)
~Next(сhest) (* проверка, что следующий сундук есть, и переход к нему *)
ELSIF (* переход к следующему UNTIL, если условие истинно (заяц пустой), и к следующему ELSIF, если ложно *)
~UnpackHare(hare, duck) (* проверка, что в зайце есть утка, и ее извлечение *)
UNTIL
~Next(сhest)
ELSIF (* переход к следующему UNTIL, если условие истинно (утка пустая), и к следующему ELSIF, если ложно *)
~UnpackDuck(duck, egg) (* проверка, что в утке есть яйцо, и его извлечение *)
UNTIL
~Next(сhest)
ELSIF (* переход к следующему UNTIL, если условие истинно (яйцо пустое), и к следующему ELSIF, если ложно *)
~UnpackEgg(egg, needle) (* проверка, что в яйце есть игла, и ее извлечение *)
UNTIL
~Next(сhest)
ELSIF (* переход к следующему UNTIL, если условие истинно (игла пустая), и к ELSE, если ложно *)
~UnpackNeedle(needle, death) (* проверка, в игле есть смерть Кощея, и ее извлечение *)
UNTIL (* выход из оператора, если условие истинно (следующего сундука нет), и возврат к WHILEIF, если ложно *)
~Next(сhest)
ELSE (* выполнение субоператоров и выход из оператора *)
existDeath := TRUE (* смерть Кощея найдена *)
END;
Очевидно, что минимальное количество действий и проверок зависит от того, как нам доступны данные: с помощью каких структур (со ссылками, без ссылок), процедур и функций. Автор не конкретизировал используемый инструментарий.
Сегмент
BEGINIF (* переход к WHILEIF, если условие истинно (первый сундук есть), и выход из оператора, если ложно *)
First(сhest) (* проверка, что первый сундук есть, и переход к нему *)
здесь можно заменить на сегменты внешнего IF-оператора
IF (* переход к THEN, если условие истинно (первый сундук есть), и выход из оператора, если ложно *)
First(сhest) (* проверка, что первый сундук есть, и переход к нему *)
THEN (* выполнение субоператоров и выход из оператора *)
а после вложенного в него оператора цикла добавить закрывающее END для IF-оператора.
Тогда оператор цикла немного упростится.
Можно после каждого UNTIL-сегмента этого оператора цикла добавить THEN-сегмент
THEN (* выполнение субоператоров и выход из оператора *)
UnassignHare(hare); (* установка неопределенного значения переменной hare *)
UnassignDuck(duck); (* установка неопределенного значения переменной duck *)
UnassignEgg(egg); (* установка неопределенного значения переменной egg *)
UnassignNeedle(needle) (* установка неопределенного значения переменной needle *)
к которому идет переход от этого UNTIL-сегмента, если его условие истинно.
Тогда сделаются неопределенными значения переменных hare, duck, egg и needle, если смерть Кощея не была найдена. Но тогда же будут лишние затирания значений переменных "Вещь", если вещи какого-либо типа из перечисленных ни разу не находились.
Можно перед каждым ELSIF-сегментом этого оператора цикла добавить ";"-сегмент
; (* выполнение субоператоров и переход к следующему ELSIF *)
existВещь := TRUE (* вещь данного типа была обнаружена *)
к которому идет переход от предыдущего WHILEIF- или ELSIF-сегмента, если его условие ложно.
И перед оператором цикла дописать
existHare := FALSE; (* заяц пока не был обнаружен *)
existDuck := FALSE; (* утка пока не была обнаружена *)
existEgg := FALSE; (* яйцо пока не было обнаружено *)
existNeedle := FALSE; (* игла пока не была обнаружена *)
а THEN-сегменты привести к виду
THEN
IF existHare THEN UnassignHare(hare) END;
IF existDuck THEN UnassignDuck(duck) END;
IF existEgg THEN UnassignEgg(egg) END;
IF existNeedle THEN UnassignNeedle(needle) END
Тогда лишних затираний значений вызовами процедур UnassignВещь не будет, но появятся дополнительные переменные existВещь. И будут повторные (лишние) присваивания переменным existВещь в ";"-сегментах, если вещи какого-либо типа из перечисленных находились несколько раз.
Наконец, можно ";"-сегменты заменить такими же UNE-сегментами, но выполняющими свое тело не более одного раза за каждый вызов цикла, а в повторные разы сразу передающими управление следующему сегменту, как будто UNE-сегмент удален.
UNE
existВещь := TRUE
Тогда повторных присваиваний также не будет, но будут лишние передачи управления либо скрытая динамическая кодогенерация.
К сожалению, без использования динамической кодогенерации либо лишних передач управления, либо лишних проверок, присвоений или вызовов процедур невозможно сделать неопределенными значения переменных hare, duck, egg, needle в случае если смерть Кощея не была найдена.
Общая структура такого оператора цикла:
BEGINIF (* expressBoolean истинно: переход к переход к WHILEIF,
expressBoolean ложно: выход из оператора *)
expressBoolean
WHILEIF (* expressBoolean истинно: переход к первому следующему DO | THEN | UNTIL,
expressBoolean ложно: переход к первому следующему ";" | UNE | ELSIF | ELSE | выход из оператора *)
expressBoolean
( DO (* выполнение statementExpress и возврат к WHILEIF *)
statementExpress
| THEN (* выполнение statementExpress и выход из оператора *)
statementExpress
| UNTIL (* expressBoolean истинно: переход к первому следующему THEN | выход из оператора,
expressBoolean ложно: возврат к WHILEIF *)
expressBoolean
[THEN (* выполнение statementExpress и выход из оператора *)
statementExpress])
{{";" (* выполнение statement и переход к первому следующему ";" | UNE | ELSIF *)
statement
| UNE (* выполнение (если ни разу за вызов цикла не выполнялся) statement и переход к первому следующему ";" | UNE | ELSIF *)
statement}
ELSIF (* expressBoolean истинно: переход к первому следующему DO | THEN | UNTIL,
expressBoolean ложно: переход к первому следующему ";" | UNE | ELSIF | ELSE | выход из оператора *)
expressBoolean
( DO (* выполнение statementExpress и возврат к WHILEIF *)
statementExpress
| THEN (* выполнение statementExpress и выход из оператора *)
statementExpress
| UNTIL (* expressBoolean истинно: переход к первому следующему THEN | выход из оператора,
expressBoolean ложно: возврат к WHILEIF *)
expressBoolean
[THEN (* выполнение statementExpress и выход из оператора *)
statementExpress])}
[ ELSE (* выполнение statementExpress и выход из оператора *)
statementExpress]
END
Здесь присутствуют длинные переходы между сегментами оператора, а это не самый приемлемый вариант цикла. Классический случай, когда есть только переходы: к соседнему следующему сегменту, к сегменту возврата (единственному на оператор), и выход из оператора. Не рассматриваем случай структурного выхода по метке или по метке ошибки. Притом, у каждого типа сегмента может быть только один или два вида перехода, фиксированных для него. Два вида перехода у сегмента возможны, когда у оператора имеются скрытые флаги-переменные.
Также, у оператора может быть множество параметров-выражений, задающих своими значениями значения скрытых параметров-переменных и параметров-констант оператора.
Параметры-составные имена у операторов (WITH, :=), и у вызовов процедур тоже, плохи тем, что при той же текстовой записи обозначают как адреса объектов, так и их значения.
Параметры-имена у некоторых операторов (FOR) реализованы неправильно из-за модификации области видимости объектов и пространства имен.
Параметры-типы у операторов (WITH) идеологически неприемлемы, ибо типовым значениям вообще нечего делать в операторной области (тела модулей и процедур), то есть в том числе и в выражениях и в составных именах, типы объектов при вызове (загрузке) процедур и модулей должны быть фиксированы в пределах каждой области видимости.
-
Чистая, но с побочными эффектами, функция
Это оксюморон.
Чистая функция не должна иметь побочных эффектов, иначе это уже не функция, а действие (процедура).
-
Чистая, но с побочными эффектами, функция
Это оксюморон.
Чистая функция не должна иметь побочных эффектов, иначе это уже не функция, а действие (процедура).
Функция, чтобы быть функцией, должна выдавать результат в выражение и вызываться в нем (как подпрограмма) через постфиксную операцию (круглые скобки и запятые) с несколькими параметрами-выражениями этой операции, дающих функциональное значение и значения ее фактических параметров:
expressFunction
"("
[express
{","
express}]
")"
Если результат в выражение выдает непосредственно сам оператор, это уже операторное выражение, а не функция. Хотя, при большом желании, это можно считать подобием INLINE-функции, только с подстановкой ее кода прямо в тексте, а не при компиляции или загрузке как у обычной INLINE.
1. Функция с побочным эффектом общему определению функции удовлетворяет. Во многих ЯП есть функции, но в очень немногих из них все функции не имеют побочных эффектов.
2. Побочный эффект это изменение вызовом функции ее внешнего окружения, а нечистота функции это влияние внешнего окружения не через значения ее фактических параметров на ее результат. Это независимые свойства!
Может быть не только чистая функция без побочных эффектов и нечистая функция с побочными эффектами, но и нечистая функция без побочных эффектов, и чистая функция с побочными эффектами!
-
1. Функция с побочным эффектом общему определению функции удовлетворяет. Во многих ЯП есть функции, но в очень немногих из них все функции не имеют побочных эффектов.
То, что в этих языках процедуры обзывают функциями, ещё не делает их функциями.
2. Побочный эффект это изменение вызовом функции ее внешнего окружения, а нечистота функции это влияние внешнего окружения не через значения ее фактических параметров на ее результат. Это независимые свойства!
Может быть не только чистая функция без побочных эффектов и нечистая функция с побочными эффектами, но и нечистая функция без побочных эффектов, и чистая функция с побочными эффектами!
Чистую функцию без побочных эффектов можно закешировать (мемоизировать, табулировать).
Если значение функции зависит не только от её параметров или функция влияет на своё окружение, производя какие-то действия, их нельзя кешировать, иначе нарушится логика работы программы. Поэтому такие функции (грязные -- зависящие не только от параметров и влияющие на окружение) следует называть процедурами, даже если они возвращают какие-то значения. А ещё лучше -- действиями (actions).
-
1. Функция с побочным эффектом общему определению функции удовлетворяет. Во многих ЯП есть функции, но в очень немногих из них все функции не имеют побочных эффектов.
То, что в этих языках процедуры обзывают функциями, ещё не делает их функциями.
Однако же вы тоже называете их функциями, пользуетесь терминологией Врага! А-а-а!!!
... или функция влияет на своё окружение... Поэтому такие функции (грязные -- зависящие не только от параметров и влияющие на окружение)...
а нужно было говорить:
... или подпрограмма влияет на своё окружение... Поэтому такие подпрограммы (грязные -- зависящие не только от параметров и влияющие на окружение)...
и обзываете просто функцию чистой функцией
... Чистую функцию без побочных эффектов...
Функция не может не быть чистой и без побочных эффектов! Только процедуры могут.
а нужно было говорить:
... Чистую подпрограмму выдающую значение и без побочных эффектов...
С волками жить...
Поэтому такие функции (грязные -- зависящие не только от параметров и влияющие на окружение) следует называть процедурами, даже если они возвращают какие-то значения. А ещё лучше -- действиями (actions).
Такие функции лучше просто запретить. Не должно быть процедур, хоть как их называй, которые выдают значения и имеют побочные эффекты.
А вот чистота функций и выражений излишня. Например, точность вычислений, или диапазон значений, или результат при ошибке (в исходной настройке функции) не обязательно задавать через параметр. Функции могут использовать множество неявно импортируемых констант и даже переменых.
Также неплохо при полном запрете побочных эффектов в выражениях, сделать у функций лениво-вычисляемые параметры, также как у всех операций.
-
http://ru.wikipedia.org/wiki/Чистота_функции (http://ru.wikipedia.org/wiki/Чистота_функции)
В функциональных языках программирования, чистая функция, это функция, которая:
является детерминированной;
не обладает побочными эффектами.
Наличие только одного из свойств недостаточно, для того чтобы функция была чистой.
-
Также неплохо при полном запрете побочных эффектов в выражениях, сделать у функций лениво-вычисляемые параметры, также как у всех операций.
Добро пожаловать в Хаскелл!
-
http://ru.wikipedia.org/wiki/Чистота_функции (http://ru.wikipedia.org/wiki/Чистота_функции)
В функциональных языках программирования, чистая функция, это функция, которая:
является детерминированной;
не обладает побочными эффектами.
Наличие только одного из свойств недостаточно, для того чтобы функция была чистой.
Значит, DddIzer пользовался неправильным определением чистоты, или привел неполное определение. То, что он назвал чистотой (и я вслед за ним) есть в действительности детерминированность.
В функциональных ЯП понятное дело все функции чистые. Там небывает скрытых параметров (кроме предопределенных констант), и глобальных переменных (и даже просто переменных) нет совсем. Операторов там тоже нет.
Также неплохо при полном запрете побочных эффектов в выражениях, сделать у функций лениво-вычисляемые параметры, также как у всех операций.
Добро пожаловать в Хаскелл!
Это следует сделать в императивных ЯП, а не эмигрировать "в функционашку из сраной имперашки".
-
Также неплохо при полном запрете побочных эффектов в выражениях, сделать у функций лениво-вычисляемые параметры, также как у всех операций.
Добро пожаловать в Хаскелл!
Это следует сделать в императивных ЯП, а не эмигрировать "в функционашку из сраной имперашки".
В Хаскелле есть императивное подмножество. Один из разработчиков Хаскелла -- Саймон Пейтон Джонс -- заявил как-то, что Хаскелл является прекраснейшим из императивных языков. Пошутил, наверное...
-
В Хаскелле есть императивное подмножество. Один из разработчиков Хаскелла -- Саймон Пейтон Джонс -- заявил как-то, что Хаскелл является прекраснейшим из императивных языков. Пошутил, наверное...
Хм, а я думал он функциональный. Обманули.
Если там есть хоть какое императивное подмножество, он уже не ФЯП.
-
В Хаскелле есть императивное подмножество. Один из разработчиков Хаскелла -- Саймон Пейтон Джонс -- заявил как-то, что Хаскелл является прекраснейшим из императивных языков. Пошутил, наверное...
Хм, а я думал он функциональный. Обманули.
Если там есть хоть какое императивное подмножество, он уже не ФЯП.
Императивное подмножество в нём чётко отделено от чистого функционального -- на уровне системы типов.
Любой реальный язык программирования должен как-то взаимодействовать с внешним миром -- ввод/вывод производить. Любые действия ввода/вывода, изменение глобальных переменных (а ввод/вывод можно рассматривать как изменение глобального состояния программы), недетерменированность вроде случайных чисел -- всё это считается действиями ввода/вывода и обозначается как действия ввода/вывода (IO actions).
Что попадёт в эти IO actions -- обратно уже не выберется.
Императивные процедуры могут вызывать чистые функции, но не наоборот -- система типов не позволит.
Так что можно считать, что фактически есть два языка, называемых общим словом "Хаскелл" -- императивный и функциональный.
-
Значит, DddIzer пользовался неправильным определением чистоты, или привел неполное определение. То, что он назвал чистотой (и я вслед за ним) есть в действительности детерминированность.
:Скорее "нестандартным" - ибо стандартное ведет в данном случае к бессмысленному (в контексте данной задачи) словоблудию - которое вы продемонстрировали.. (да и вранье что вы следовали за мной - свое отношение к топику как задачи на тему -нах. сесть и конфетку съесть - я высказал четко и давно,а также отказался от дискуссии на эту тему с вами...)