Oberon space
General Category => Общий раздел => Тема начата: Peter Almazov от Сентябрь 09, 2012, 03:04:59 pm
-
Пароль к посту http://oberspace.dyndns.org/index.php/topic,253.msg6318.html#msg6318 : "ZRL/|EqEr<x<<Y" без кавычек.
Содержимое файла для удобства:
Инвариант для цикла Info21: в просмотренной области нет последовательности 00 и переменная oneZero имеет значение: последний элемент просмотренной области есть 0.
Инвариант для цикла в последнем решении Александр Шостак: в переменной ChainLen лежит длина хвоста просмотренной области, состоящего из нулей.
В конце файла добавлен мусор, т.к. крошечный размер файла – сама по себе информация.
Если кто-нибудь ожидал увидеть полстраницы математических значков, то будет сильно огорчен.
Тексты программ для удобства:
Info21, http://forum.oberoncore.ru/viewtopic.php?p=72961#p72961
i := 0;
oneZero := FALSE; (*oneZero = перед i стоит нуль*)
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i);
ELSIF (i < LEN(a)) & (a[i] # 0) DO
oneZero := FALSE;
INC(i);
END;
Александр Шостак, http://forum.oberoncore.ru/viewtopic.php?p=72958#p72958
CONST
CHAIN_LEN = 7;
CHAIN_BYTE = 0;
ChainLen := 0;
i := 0;
WHILE (i < LEN(a)) & (ChainLen < CHAIN_LEN) DO
IF a[i] = CHAIN_BYTE THEN
INC(ChainLen);
ELSE
ChainLen := 0;
END;
INC(i);
END;
Мой комментарий:
Info21 разъяснил нам про инвариант, что "он там тривиальный до бессодержательности.
Именно поэтому и не понадобился. (http://forum.oberoncore.ru/viewtopic.php?p=72977#p72977)"
Так вот, в решении Александр Шостак инвариант почти такой же тривиальный (дополнение чуть ниже), но он ДРУГОЙ. Разные инварианты – разные программы. Углубляться дальше не буду.
А моя ошибка вот в чем: инвариант для решения Александр Шостак не полон. Ниоткуда не следует, что найденный кусок будет первым от начала массива. Я заметил, да было уже поздно. Желающие могут попробовать сформулировать недостающую часть.
Кстати, я помню, что, по-моему, albobin записал решение Info21 по человечески, без всяких ЦД. Именно так оно бы и выглядело, если бы рождалось осмысленно. Но не нашел этого куска, неужели опять удалили?
-
а что это за язык то:
while ... do
...
elsif .... do
...
end;
-
Сэкономил на цитировании, забыл что тема может быть закрытой. У Info21 в начале
"Чтобы не казалось, что мой вариант сложнее, перепишу на Обероне-07, где ЦД есть явно:"
-
а что это за язык то:
while ... do
...
elsif .... do
...
end;
В принципе похоже на Оберон-07, вот только ключевые слова почему-то в нижнем регистре...
-
а это уже я поленился - у Петра в сообщении они были в нормально регистре :)
-
Инвариант для цикла Info21: в просмотренной области нет последовательности 00 и переменная oneZero имеет значение: последний элемент просмотренной области есть 0.
Хмм, т.е. после окончания работы цикла инвариант не выполняется?
-
Вообще, в той же "Дисциплине программирования" Дейкстра не стеснялся использовать ветвления и даже подциклы внутри главного цикла.
И если уж на то пошло, если делать этот цикл и правда по Дейкстре (с недетерменированным порядком вычисления охраняемых выражений), то должно быть так:
i, found := 0, false;
do i < len(a) - 1 and not found ->
x, y := a[i], a[i+1];
if x = 0 and y = 0 -> found := true
[] x ≠ 0 or y ≠ 0 -> i := i + 1
fi
odПолистал я Дейкстрову книшку и уверен, что этот вариант самый что ни на есть "по Дейкстре" ))
Вариант, правда, не очень эффективный, но зато простейший и очевидный.
И похож на мой вариант на хаскелле:
find00 xs = find xs 0
where
find (0:0:_) n = Just n
find (_:xs) n = find xs (n+1)
find [] _ = Nothing
-
И если уж на то пошло, если делать этот цикл и правда по Дейкстре (с недетерменированным порядком вычисления охраняемых выражений)
По поводу недетерменированности -- цитата из Дейкстры:
(http://oberspace.dyndns.org/index.php?action=dlattach;topic=297.0;attach=154)
-
Инвариант для цикла Info21: в просмотренной области нет последовательности 00 и переменная oneZero имеет значение: последний элемент просмотренной области есть 0.
Хмм, т.е. после окончания работы цикла инвариант не выполняется?
Выполняется. Если расписывать аккуратно, то просмотренная область - это элементы с индексами j: 0<=j<i.
Но я этого обычно не делаю.
-
Вообще, в той же "Дисциплине программирования" Дейкстра не стеснялся использовать ветвления и даже подциклы внутри главного цикла.
И если уж на то пошло, если делать этот цикл и правда по Дейкстре (с недетерменированным порядком вычисления охраняемых выражений), то должно быть так:
i, found := 0, false;
do i < len(a) - 1 and not found ->
x, y := a[i], a[i+1];
if x = 0 and y = 0 -> found := true
[] x ≠ 0 or y ≠ 0 -> i := i + 1
fi
odПолистал я Дейкстрову книшку и уверен, что этот вариант самый что ни на есть "по Дейкстре" ))
Вариант, правда, не очень эффективный, но зато простейший и очевидный.
Действительно, это первое, что приходит в голову (мне, во всяком случае). Но, конечно не так, а вот так:
i:= 0;
do
i < len(a) - 1 and (a[i] <>0 or a[i+1]<>0) -> i:=i+1;
odОчень неэффективно и не расширяемо на более длинную цепочку нулей.
Первый вопрос который я задал vlad'у в той теме был об этом варианте: "Что значит "правильным". Лишнее сравнение в случае массива - это правильно?" http://oberspace.dyndns.org/index.php/topic,253.msg6087.html#msg6087
Geniepro, осталось сформулировать инвариант для этого цикла...
-
Geniepro, осталось сформулировать инвариант для этого цикла...
Зачем формулировать инварианты заведомо правильных циклов? Делать ради самого делания? о_О
-
Действительно, это первое, что приходит в голову (мне, во всяком случае). Но, конечно не так, а вот так:
i:= 0;
do
i < len(a) - 1 and (a[i] <>0 or a[i+1]<>0) -> i:=i+1;
od
Тогда надо добавить в конце строчку:
found := i < len(a)
если хотим получить ещё и признак того, нашли эти два нуля или нет...
-
Тогда надо добавить в конце строчку:
found := i < len(a)
если хотим получить ещё и признак того, нашли эти два нуля или нет...
точнее
found := i < len(a) - 1
Вот, без тестирования ошибку уже найти труднее, чем в моём варианте )))
-
Инвариант для цикла Info21: в просмотренной области нет последовательности 00 и переменная oneZero имеет значение: последний элемент просмотренной области есть 0.
Инвариант с2-мя изъянами неточности, на что уже указал qp в http://oberspace.dyndns.org/index.php/topic,331.msg8786.html#msg8786 (http://oberspace.dyndns.org/index.php/topic,331.msg8786.html#msg8786)
В такой формулировке инвариант не выполняется по выходу из цикла в случае нахождения 00.
Кстати, я помню, что, по-моему, albobin записал решение Info21 по человечески, без всяких ЦД. Именно так оно бы и выглядело, если бы рождалось осмысленно. Но не нашел этого куска, неужели опять удалили?
Нет, я ничего не переписывал. Было когда-то дело, но там был цикл , кажется Ильи Ермакова (могу ошибаться), с полным перебором.
-
Инвариант для цикла Info21: в просмотренной области нет последовательности 00 и переменная oneZero имеет значение: последний элемент просмотренной области есть 0.
Хмм, т.е. после окончания работы цикла инвариант не выполняется?
Выполняется. Если расписывать аккуратно, то просмотренная область - это элементы с индексами j: 0<=j<i.
Но я этого обычно не делаю.
Как бы не расписывали, найти 00 можно только в просмотренной области :)
-
Как бы не расписывали, найти 00 можно только в просмотренной области :)
Нет. Элемент a[ i ] в начале цикла не входит в просмотренную область. Мы "заглядываем вперед", и, если там 0 и oneZero=истина, то отваливаем. После этого имеем: один 0 на конце просмотренной области и один 0 впереди.
Название oneZero дурацкое, по сути надо lastCharIsZero.
-
Как бы не расписывали, найти 00 можно только в просмотренной области :)
Нет. Элемент a[ i ] в начале цикла не входит в просмотренную область. Мы "заглядываем вперед", и, если там 0 и oneZero=истина, то отваливаем. После этого имеем: один 0 на конце просмотренной области и один 0 впереди.
Название oneZero дурацкое, по сути надо lastCharIsZero.
Эпитеты не помогут. Вы ошиблись - пора признаться :)
-
Для особо бестолковых: нарисуте массив по клеточкам, в конце добавьте два 0, снизу между ними нарисуйте стрелку вверх. Это и будет граница просмотренной области. И в ней нет 00.
-
Для особо бестолковых: нарисуте массив по клеточкам, в конце добавьте два 0, снизу между ними нарисуйте стрелку вверх. Это и будет граница просмотренной области. И в ней нет 00.
Сколько угодно можете себя убеждать :)
-
:) Петр , а теперь скажите
будут ли инвариантами цикла (в вашем куске кода)
i < LEN(a)
-100 < i <= LEN(a)
-100 <= i <= LEN(a)+100
-
А чего пожадничали, взяли бы все множество истинных утверждений.
Ответ подразумевает нудное описание, в чем тут засада. Я не готов его дать.
Более того, в ближайшие полторы недели перейду, в лучшем случае, в режим ReadOnly.
-
Эх, столько было пафоса, и такой эпичный слив )))
-
Эх, столько было пафоса, и такой эпичный слив )))
В жизни всякое случается, Geniepro ;), от таки вещей никто не застрахован.. тем больше вы на себя берете, тем больше вероятность конфуза.... весь вопрос в том, что дальше.. лично я стараюсь делать так , что бы каждый подобный конфуз делал меня сильнее..
-
А чего пожадничали, взяли бы все множество истинных утверждений.
А разве инвариант цикла не есть логическое выражение выполняющееся перед выполнением цикла и после каждой ее итерации ? ;D ;D ;D :)
Свое отношение к этому виду танцев с бубном я уже высказывал - но может быть вы таки сможете коротко и ясно пояснить причину конфуза и сделать некоторые выводы?
-
Для особо бестолковых: нарисуте массив по клеточкам, в конце добавьте два 0, снизу между ними нарисуйте стрелку вверх. Это и будет граница просмотренной области. И в ней нет 00.
Сколько угодно можете себя убеждать :)
Для особо бестолковых на месте П.А. я бы так объяснил точный смысл слова просмотренный применительно к этому циклу. Типа смотрим диафильм про массив. Показался элемент, смотрим. Не ноль - рот спокойно закрыт, ноль- рот в предвкушении радостного удивления округло приоткрывается. Надоело смотреть или невтерпёж - моргнули - всё, на экране следующая картинка, старая просмотрена. Не ноль - рот прикрыли, ну а если опять ноль - то глаза радостно округло выпучиваются и в таком состоянии и столбенеем для истории. Вот и получается, что последний ноль хоть и на виду, а не просмотрен. :)
Ну, а ежели конец безрадостный, то самое больше - остаться с приоткрытым ртом, но с грустными глазами.
-
"выполняющееся перед выполнением цикла и после каждой ее итерации " - сорри,коряво сказано ,правильно ИСТИННОЕ перед выполнением цикла и после каждой его итерации, и зря в обвиняете меня в скудоумии - я без проблем могу состряпать такое выражение, что без знания матанализа ни х не разберешься... ;)
-
Эх, попробовал я таки сделать этот инвариант и понял, что в императивных языках, да ещё и с массивами и циклами, эти ваши инварианты гораздо труднее делать, чем на ФЯ со списками да рекурсиями. По крайней мере, для подобных задачек...
Вот функциональная программа на псевдокоде:
Прим.
list<TYPE> -- это тип "список с элементами типа TYPE", head и tail -- функции, возвращающие, соответственно, первый элемент списка и его хвост.
option<TYPE> -- это тип, который может иметь значение none, что означает "нет значения", или some<X>, что означает "есть значение X типа TYPE"
function find00 (xs: list<int>) : option<int>
function find (xs: list<int>, i: int) : int
begin
{ (список пуст и тогда искомая последовательность не найдена)
или (искомая последовательность находится в первых двух элементах списка)
или (искомая последовательность находится в хвосте списка)
}
if xs = nil then return none
else if head(xs) = 0 and head(tail(xs)) = 0 then return some<i>
else return find (tail(xs), i+1)
end;
begin
return find (xs, 0)
endУсловие завершения для функции find, как видно, такое:
"(список пуст и тогда искомая последовательность не найдена)
или (искомая последовательность находится в первых двух элементах списка)
или (искомая последовательность находится в хвосте списка)"
Теперь вольный перевод этой программы на императивный язык с циклами и массивами:
Прим. Нумерация элементов массива идёт с 1, а не с 0
i := 1;
{ инв: (i > len(a)-1, а значит массив не содержит искомую последовательность)
or (элементы a[i] и a[i+1] содержит искомую последовательность)
or (искомая последовательность находится в части массива c позиции i+1 по len(a)-1)
}
while i < len(a) and (a[i] ≠ 0 or a[i+1] ≠ 0) do
{ инв }
i := i + 1
end;
{ ((i = len(a)) or (a[i] = 0 and a[i+1] = 0)) and инв }Ну и инвариант, соответственно, такой:
"(i > len(a)-1, а значит массив не содержит искомую последовательность)
или (элементы a[i] и a[i+1] содержит искомую последовательность)
или (искомая последовательность находится в части массива c позиции i+1 по len(a)-1)"
Ужасно, должен вам сказать. Я этот ваш инвариант цикла осилил только после того, как описал словами условие завершения рекурсивной функции со списком...
ЗЫ. Опциональные типы option в ML-языках или Maybe в хаскелле гораздо безопаснее, чем null или всякие коды -1 в традиционных императивных языках...
-
Ну и инвариант, соответственно, такой:
"(i > len(a)-1, а значит массив не содержит искомую последовательность)
или (элементы a[i] и a[i+1] содержит искомую последовательность)
или (искомая последовательность находится в части массива c позиции i+1 по len(a)-1)"
Эта чортова нумерация массивов с нуля и все эти +1 -1 только путают ((
Должно быть так (если принять нумерацию с 1):
"(i > len(a)-1, а значит массив не содержит искомую последовательность)
или (элементы a[i] и a[i+1] содержит искомую последовательность)
(искомая последовательность находится в части массива c позиции i+1 по len(a))"
или, если принять нумерацию с 0, то так:
"(i > len(a)-2, а значит массив не содержит искомую последовательность)
или (элементы a[i] и a[i+1] содержит искомую последовательность)
или (искомая последовательность находится в части массива c позиции i+1 по len(a)-1)"
-
Эта чортова нумерация массивов с нуля и все эти +1 -1 только путают ((
Угу последние 3 года я заставляю студентов использовать массивы индексируемые с нуля... но на прошлой неделе пришлось пописать скриптики для статьи на Луа - там усе с единицы блин какой кайф...
-
что касается вашего виденья, Петр - по ссылке которую вы не постеснялись здесь дать - я привел там вам еще пару инвариантов (по определению) и попросил прокомментировать их
- у вас КИШКА ТОНКА ОКАЗАЛАСЬ - ответ сводился "рассуждения долгие и нудные , у меня нет времени на это", кроме того, Албобин нашел у вас ошибку (это свидетельство что эта метода даже вам(ее адепту) не помогла ее избежать- если это так то НАХ. данная методика? и не е.-те другим мозги...
Сколько пафоса. Может, не надо было сразу так, большими буквами-то.
Можно было и помягше: "Тема все еще представляет интерес". А то я исхожу из худшего – что надоел уже всем повторением одно и того же.
Вопросы про инварианты от Dizer и про мифическую ошибку или "неточность" имеют, в сущности, один и тот же корень.
Рассмотим случай, когда в последовательности есть 00 и мы-таки это нашли в процессе выполнения цикла. Видимо, в голове не укладывается, почему после выполнения цикла истинен инвариант, в который входят слова "в просмотренной части последовательности нет 00". Прежде чем объяснять в четвертый раз, у меня большая просьба к albobin (на других надежды нет), попробуйте сформулировать инвариант для этого цикла (http://oberspace.dyndns.org/index.php/topic,331.msg8792.html#msg8792).
i:= 0;
do
i < len(a) - 1 and (a[i] <>0 or a[i+1]<>0) -> i:=i+1;
od
Может, и объяснять ничего не придется.
-
"в просмотренной части последовательности нет 00". Прежде чем объяснять в четвертый раз, у меня большая просьба к albobin (на других надежды нет) ... Может, и объяснять ничего не придется.
По поводу "просмотренной части последовательности". Придирка ведь носит несколько стёбовый характер. Конечно все понимают, что говоря о "просмотренном" имеют ввиду множество всех переменных цикла при которых был вход в тело цикла. Но c другой стороны, не "посмотремши" на элемент массива, сложновато использовать его значение в логических условиях. :)
PS.
Извините великодушно, но выполнить просьбу не могу - высочайшего уровня скромность не позволяет :)
-
Прежде чем объяснять в четвертый раз, у меня большая просьба к albobin (на других надежды нет), попробуйте сформулировать инвариант для этого цикла (http://oberspace.dyndns.org/index.php/topic,331.msg8792.html#msg8792).
i:= 0;
do
i < len(a) - 1 and (a[i] <>0 or a[i+1]<>0) -> i:=i+1;
od
Может, и объяснять ничего не придется.
Так я же вроде сформулировал: http://oberspace.dyndns.org/index.php/topic,331.msg8824.html#msg8824
Или у меня там где-то ашыпка?
-
Конечно все понимают, что говоря о "просмотренном" имеют ввиду множество всех переменных цикла при которых был вход в тело цикла.
Я не знаю, что все понимают и имеют ввиду.
Пока я вижу, что никто ни х@$% не понимает (кроме Info21).
Инвариант этого цикла: "в просмотренной части последовательности нет 00".
Вот это (http://forum.oberoncore.ru/viewtopic.php?p=72980#p72980) кто писал, двойник что-ли:
Для циклов поиска, наверное самый естественный инвариант - это отсутствие "искаемого" в текущем просмотренном:)
PS.
Под "просмотренным" понимается "до текущей точки(исключительно)"
-
что касается вашего виденья, Петр - по ссылке которую вы не постеснялись здесь дать - я привел там вам еще пару инвариантов (по определению) и попросил прокомментировать их
- у вас КИШКА ТОНКА ОКАЗАЛАСЬ - ответ сводился "рассуждения долгие и нудные , у меня нет времени на это", кроме того, Албобин нашел у вас ошибку (это свидетельство что эта метода даже вам(ее адепту) не помогла ее избежать- если это так то НАХ. данная методика? и не е.-те другим мозги...
Сколько пафоса. Может, не надо было сразу так, большими буквами-то.
Можно было и помягше: "Тема все еще представляет интерес". А то я исхожу из худшего – что надоел уже всем повторением одно и того же.
Вопросы про инварианты от Dizer и про мифическую ошибку или "неточность" имеют, в сущности, один и тот же корень.
Рассмотим случай, когда в последовательности есть 00 и мы-таки это нашли в процессе выполнения цикла. Видимо, в голове не укладывается, почему после выполнения цикла истинен инвариант, в который входят слова "в просмотренной части последовательности нет 00". Прежде чем объяснять в четвертый раз, у меня большая просьба к albobin (на других надежды нет), попробуйте сформулировать инвариант для этого цикла (http://oberspace.dyndns.org/index.php/topic,331.msg8792.html#msg8792).
i:= 0;
do
i < len(a) - 1 and (a[i] <>0 or a[i+1]<>0) -> i:=i+1;
od
Может, и объяснять ничего не придется.
;D ;D ;D ;D ;) Пафоса ,Петр до х.. у вас (когда - затевали этот балаган, и если вы обвиняете коровят и в незнании топика - будьте добры показать свою квалификацию, а то есть ОЧЕНЬ большая вероятность обокакаться как недавно Инфо21 обратившись с прямым вызовом к участникам этого форума...)- а вот знаний ответить четко на поставленный вопрос (как мой , так и Ильи) - ни х.. - и этот ответ лишний раз подтверждает это...
-
Не спешите, интересно, что albobin напишет.
-
;) А, я Петр и не спешу... а что касается ИНТЕРЕСА к теме - так помилуйте проводимые циклически вычисления являются НЕОТЕМЛЕМОЙ частью большинства алгоритмов, и как следствие - умение ПРАВИЛЬНО выписывать циклы - практически эквивалентно правильному решению задач - так что это ИНТЕРЕСНО если у вас есть что-то ПОЛЕЗНОЕ сказать по этому поводу(пока вы не демонстрируете даже потенциальную способность сделать это). Что касается вашего покорного слуги - то он (я) честно признался , что делает ошибки... в том числе и в циклах , и достаточно много времени потратил на то что бы разобраться в их природе.. а так же методах уменьшения вероятности их возникновения... а мой род деятельности позволяет применить непосредственно на студентах оные методы и оценить их эффективность.. - и панацеи в этой методе я НЕ ВИЖУ
-
Не спешите, интересно, что albobin напишет.
А можно объяснить такой ниграмытной быдле как я, какой собственно профит от этих "формальных" методов в императивных языках общего назначения?
-
Не спешите, интересно, что albobin напишет.
А можно объяснить такой ниграмытной быдле как я, какой собственно профит от этих "формальных" методов в императивных языках общего назначения?
Это я так понимаю ... вопрос к Петру ? :D
-
Это я так понимаю ... вопрос к Петру ? :D
Да, конечно. Я ведь именно его процитировал.
Но если кто-то другой, познавший дзен, мне толково объяснит, то я не погнушаюсь.
-
Вот это (http://forum.oberoncore.ru/viewtopic.php?p=72980#p72980) кто писал, двойник что-ли:
Для циклов поиска, наверное самый естественный инвариант - это отсутствие "искаемого" в текущем просмотренном:)
PS.
Под "просмотренным" понимается "до текущей точки(исключительно)"
Нет не двойник.
Всё так и есть, если в общем рассматривать инвариант циклов поиска, но есть ещё же и частные конкретные случаи в которых этот инвариант принимает другие формы выражения той же самой сути.
Рискую поумничать, но выражу своё или скорее всего где то прочитанное и переваренное или перевранное в мозгах представление о сути цикла поиска.
Есть некий предикат определённый на некотором конечном множестве последовательных целых чисел. Поиск определяем как простой перебор чисел по возрастанию до того момента когда предикат примет значение истины.
Вышли за пределы - ничего не найдено.
Вот и инвариант цикла как раз и будет : значение предиката ложь при всех значениях до текущего.
Главное что есть последовательный перебор и отсутствие препятствий к достижению конца последовательности кроме как ограничения не нарушать инвариант. Вот и всё.
-
Одни забывают про инвариант, другие про охрану. Не надо ничего перевирать, читайте первоисточники или, накрайняк, это http://oberspace.dyndns.org/index.php/topic,253.msg6224.html#msg6224
Надо просто усвоить, что после выполнения цикла будет истинным выражение
Инвариант И (НЕ охрана цикла)
Для цикла Дейкстры –
Инвариант И (конъюнкция отрицаний охран)
После упомянутого выше цикла будет истинно:
("в просмотренной части последовательности нет 00") И ((i вышло за границы) ИЛИ (впереди стоят два нуля))
Первым делом после цикла (допустим, нашли 00) мы разбираемяся с i, как верно заметил Geniepro здесь http://oberspace.dyndns.org/index.php/topic,331.msg8796.html#msg8796
Не вышло i за границы, значит верно, что:
("в просмотренной части последовательности нет 00") И (впереди стоят два нуля)
Мы гарантируем, что нашли первые от начала 00, о чем многие забывают.
После цикла Info21 и разбирательства с i останется:
(в просмотренной области нет последовательности 00 и последний элемент просмотренной области есть 0) И (впереди стоит 0).
Прошу заметить, что здесь нет никакой (страшной) математики, единственное, что надо знать твердо - это законы де Моргана.
-
Теперь по поводу инвариантов от Dizer. Я не зря спросил про множество всех истинных утверждений, все они будут инвариантами цикла.
Процитирую Гриса, стр. 149:
У цикла имеется много инвариантов. Например, предикат x*0=0 является инвариантом любого цикла, так как он всегда истинен. Но инварианты, удовлетворяющие условиям теоремы (11.6), способствуют пониманию цикла и поэтому важны.
Слово "теорема" пугает народ (и меня тоже, да). Там речь идет ровно о том, что я написал в начале: после выполнения цикла будет истинным выражение
Инвариант И (НЕ охрана цикла)
Поэтому толку от инвариантов типа "Волга впадает в Каспийское море" будет маловато.
-
Теперь по поводу инвариантов от Dizer. Я не зря спросил про множество всех истинных утверждений, все они будут инвариантами цикла.
Процитирую Гриса, стр. 149:
У цикла имеется много инвариантов. Например, предикат x*0=0 является инвариантом любого цикла, так как он всегда истинен. Но инварианты, удовлетворяющие условиям теоремы (11.6), способствуют пониманию цикла и поэтому важны.
Слово "теорема" пугает народ (и меня тоже, да). Там речь идет ровно о том, что я написал в начале: после выполнения цикла будет истинным выражение
Инвариант И (НЕ охрана цикла)
Поэтому толку от инвариантов типа "Волга впадает в Каспийское море" будет маловато.
ну ладно , хоть Гриса приплели.... хотя я дал вам не тривиальный инвариант... а мог бы дать и более сложную комбинацию элементарных (и не очень) функций от параметров входящих в цикл.. И ОНИ БЫЛИ БЫ ТАКЖЕ ЕГО НЕ ТРИВИАЛЬНЫМИ ИНВАРИАНТАМИ - ПОЭТОМУ ваши закидоны о "правильности" инварианта ничего не стоят без ТОЧНОГО и КОНСТРУКТИВНОГО определения тех из них по которым можно определить цикл, И ГЛАВНОЕ - ЭФФЕКТИВНОГО способа ИХ КОНСТРУИРОВАНИЯ в общем случае. Вот когда дадите его - тогда и будем сравнивать эффективность этой методы... Да и насчет цитаты ;) :D - вам не кажется что Григс - в отличие от вас и коровят использует НА ПОРЯДОК более расплывчато неопределенные высказывания - "способствуют пониманию цикла и поэтому важны" ? с чего бы это? - может потому, что он , в отличие от вас понимает, что данная метода не ПАНАЦЕЯ?
-
Вот и всё.
Нет не всё. Подумавши ещё немного, ворочаясь от бессонницы ( в другое время как-то нужды нет) , пришёл к выводу, что в том, что здесь обсуждается и в том, что и я написал в предыдущем послании, насчёт инварианта в той формулровке цикла поиска, есть изъян - хрень масло-маслянная.
А правда вся в том, что говорил info21 в http://forum.oberoncore.ru/viewtopic.php?f=82&t=3770&start=20#p72977 (http://forum.oberoncore.ru/viewtopic.php?f=82&t=3770&start=20#p72977) инвариант тут "тривиальный до бессодержательности"
Вот есть массив a[] длины N , нужно найти первый нулевой элемент
i:=0; while (i<N)&(a[i]<>0) do i:=i+1 end
Более правильная формулировка задачи такая: найти минимальное значение i при котором предикат a[i]=0 будет иметь значение истина. Для решения этой задачи мы выбираем такой способ упорядочения проверяемых элементов массива при котором каждый следующий i больше предыдущего и ни один i из диапазона от 0 до N-1 не должен быть пропущен, а это есть то, что следующее значение i должно быть больше предыдущего на единицу, а начальное значение должно быть 0. Вот здесь и настоящий "тривиальный" инвариант.
i+1=i+1
:)
-
Теперь по поводу инвариантов от Dizer. Я не зря спросил про множество всех истинных утверждений, все они будут инвариантами цикла.
...
Поэтому толку от инвариантов типа "Волга впадает в Каспийское море" будет маловато.
Инвариант цикла должен подсказывать логику работы цикла.
Утверждения вроде "2*2=4" или "Волга впадает в Каспийское море" никак не подсказывают нам свойств цикла, а значит и не являются инвариантами цикла.
Да, эти утверждения являются инвариантами, но не цикла...
-
Теперь по поводу инвариантов от Dizer. Я не зря спросил про множество всех истинных утверждений, все они будут инвариантами цикла.
...
Поэтому толку от инвариантов типа "Волга впадает в Каспийское море" будет маловато.
Инвариант цикла должен подсказывать логику работы цикла.
Утверждения вроде "2*2=4" или "Волга впадает в Каспийское море" никак не подсказывают нам свойств цикла, а значит и не являются инвариантами цикла.
Да, эти утверждения являются инвариантами, но не цикла...
:) Никто никому не должен - есть четкое определение инварианта (по которому можно определить является ли ПРОИЗВОЛЬНОЕ логическое выражение оным), есть примеры примененя методы- в основной своей массе на таких циклах где формулировка инвариантов скорее в тягость, есть ОСТОРОЖНЫЕ высказывания МЭТРОВ (Дейкстры, Грисома) по данной методе- а есть танцульки вокруг "идола" в коровне , в основе которой манипуляция с естественным желанием человека получить все с наименьшими затратами, ну :D. и есть Петр Алмазов...
-
Вариант от info21 (псевдоцикл Дейкстры)
i := 0;
oneZero := FALSE; (*oneZero = перед i стоит нуль*)
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i);
ELSIF (i < LEN(a)) & (a[i] # 0) DO
oneZero := FALSE;
INC(i);
END;плох тем, что оставляет неверное представление о настоящем цикле Дейкстры.
Вообще я попробовал сделать этот алгоритм в виде цикла Дейкстры, но что-то сомневаюсь, что из этого выйдет что-то путное -- ну не подходит этот алгоритм для ЦД. Вот что реально из себя представляет алгоритм, представленный info21:
i := 0;
found := FALSE; (* found = (a[i-1] = 0) & (a[i] = 0) *)
WHILE (i < LEN(a)) & ~found DO
WHILE (i < LEN(a)) & a[i] # 0 DO INC(i) END;
IF (i < LEN(a)) & a[i] # 0 THEN INC(i)
ELSE found := TRUE
END;
END;
-
Вот что реально из себя представляет алгоритм, представленный info21:
i := 0;
found := FALSE; (* found = (a[i-1] = 0) & (a[i] = 0) *)
WHILE (i < LEN(a)) & ~found DO
WHILE (i < LEN(a)) & a[i] # 0 DO INC(i) END;
IF (i < LEN(a)) & a[i] # 0 THEN INC(i)
ELSE found := TRUE
END;
END;
Да ну?
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
-
Вот что реально из себя представляет алгоритм, представленный info21:
Таки ошибся, вот правильный вариант:
i := 0;
found := FALSE; (* found = (a[i-1] = 0) & (a[i] = 0) *)
WHILE (i < LEN(a)) & ~found DO
WHILE (i < LEN(a)) & a[i] # 0 DO INC(i) END;
INC(i);
IF (i < LEN(a)) THEN
IF a[i] = 0 THEN found := TRUE
ELSE INC(i)
END
END
END;
-
Да ну?
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
Ваш вариант по сути аналогичен этому:
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END;
-
Да ну?
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
Ваш вариант по сути аналогичен этому:
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END;
Это не мой вариант - это суть варианта от info21
-
Это не мой вариант - это суть варианта от info21
Логически да, но вычислительная сложность всё-таки разная.
-
А можно объяснить такой ниграмытной быдле как я, какой собственно профит от этих "формальных" методов в императивных языках общего назначения?
Вот здесь http://oberspace.dyndns.org/index.php/topic,261.msg6309.html#msg6309 я уже предлагал всем желающим сделать 2 упражнения.
Отношение к ним может быть разное.
Некто может сказать:
"Что за херня? Я не могу уверенно, быстро и без ошибок написать цикл длиной порядка 10 строк, при том, что общая идея мне ясна. Не мудак ли я?
Хочу перезжать подобные задачи как трактор."
Другой может сказать:
"Все это – х@$#я"
"Программист с такими циклами не встретится" (c) И.Е.Ермаков
"Я посмотрю в справочнике"
"Я использую библиотечную сортировку"
"Я покрою все тестами"
и т. п.
Тут уж каждый сам выбирает :)
-
А можно объяснить такой ниграмытной быдле как я, какой собственно профит от этих "формальных" методов в императивных языках общего назначения?
Вот здесь http://oberspace.dyndns.org/index.php/topic,261.msg6309.html#msg6309 я уже предлагал всем желающим сделать 2 упражнения.
Отношение к ним может быть разное.
Некто может сказать:
"Что за херня? Я не могу уверенно, быстро и без ошибок написать цикл длиной порядка 10 строк, при том, что общая идея мне ясна. Не мудак ли я?
Хочу перезжать подобные задачи как трактор."
Другой может сказать:
"Все это – х@$#я"
"Программист с такими циклами не встретится" (c) И.Е.Ермаков
"Я посмотрю в справочнике"
"Я использую библиотечную сортировку"
"Я покрою все тестами"
и т. п.
Тут уж каждый сам выбирает :)
может ... может да , может нет.... может быть, может не быть... а где ответ то на вопрос==частное мнение "познавшего дзен" ? :D ;)
-
Это не мой вариант - это суть варианта от info21
Логически да, но вычислительная сложность всё-таки разная.
То есть Ваш вариант того,
что реально из себя представляет алгоритм, представленный info21:
i := 0;
found := FALSE; (* found = (a[i-1] = 0) & (a[i] = 0) *)
WHILE (i < LEN(a)) & ~found DO
WHILE (i < LEN(a)) & a[i] # 0 DO INC(i) END;
INC(i);
IF (i < LEN(a)) THEN
IF a[i] = 0 THEN found := TRUE
ELSE INC(i)
END
END
END;остаётся в силе ? :)
-
То есть Ваш вариант того,
что реально из себя представляет алгоритм, представленный info21:
...
остаётся в силе ? :)
Думаю, да. Хотя он и выглядит страшно без синтаксического сахара, использованного info21, но и логически, и по выч. сложности он аналогичен варианту info21...
-
Тревожно как-то от таких аналогий :-[
-
Тревожно как-то от таких аналогий :-[
В Обероне-07 операторWHILE cond1 DO s1
ELSIF cond2 DO s2
ELSIF cond3 DO s3
...
ELSIF condN DO sN
ENDэквивалентен конструкцииLOOP
WHILE cond1 DO s1 END;
IF cond2 THEN s2
ELSIF cond3 THEN s3
...
ELSIF condN THEN sN
ELSE EXIT
END
END
Берём алгоритм info21i := 0;
oneZero := FALSE;
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i)
ELSIF (i < LEN(a)) & (a[i] # 0) DO
oneZero := FALSE;
INC(i)
END;и преобразуем его по этой схеме в:i := 0;
oneZero := FALSE;
LOOP
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i)
END;
IF (i < LEN(a)) & (a[i] # 0) THEN
oneZero := FALSE;
INC(i)
ELSE
EXIT
END
ENDДалее избавляемся от выхода из середины:i := 0;
oneZero := FALSE;
b := TRUE;
WHILE b
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i)
END;
IF (i < LEN(a)) & (a[i] # 0) THEN
oneZero := FALSE;
INC(i)
ELSE
b := FALSE
END
ENDизбавляемся от лишнего флажка oneZero:i := 0;
not_found := TRUE;
WHILE (i < LEN(a)) & not_found
WHILE (i < LEN(a)) & (a[i] # 0) DO
INC(i)
END;
INC(i);
IF (i < LEN(a)) THEN
IF a[i] # 0 THEN
INC(i)
ELSE
not_found := FALSE
END
END
ENDВыбирайте, какой Вам больше по душе...
-
Тревожно как-то от таких аналогий :-[
В Обероне-07 операторWHILE cond1 DO s1
ELSIF cond2 DO s2
ELSIF cond3 DO s3
...
ELSIF condN DO sN
ENDэквивалентен конструкцииLOOP
WHILE cond1 DO s1 END;
IF cond2 THEN s2
ELSIF cond3 THEN s3
...
ELSIF condN THEN sN
ELSE EXIT
END
END
Не понял... почему такой?
Зачем там while?
LOOP
IF cond1 THEN s1
ELSIF cond2 THEN s2
ELSIF cond3 THEN s3
...
ELSIF condN THEN sN
ELSE EXIT
END
END
-
Не понял... почему такой?
Зачем там while?
Это простейшая оптимизация.
Пока условие cond1 истинно, выполняться в цикле будет s1.
С другими охранными выражениями такой оптимизации сделать не получится...
Я имею в виду, что в такой вид этот псевдо-ЦД переводят компиляторы сей и компилятор Оберона-07М от Рифата...
-
В цикде Дейкстры, вроде как, каждая ветка (охрана) открывает (если условие истинно) точку входа (и только одну, даже если истинны несколько охран) для следующей итерации.
-
Выбирайте, какой Вам больше по душе...
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
:)
-
Надо просто усвоить, что после выполнения цикла будет истинным выражение
Инвариант И (НЕ охрана цикла)
Для цикла Дейкстры –
Инвариант И (конъюнкция отрицаний охран)
И это все? ???
А кто пишет циклы иначе? Или вся соль в том, чтобы инвариант и охрана обязательно явно были в условии цикла?
-
До меня только недавно дошло, что термин "просмотренная область" может сильно сбивать с толку. Гораздо уместнее было бы "обработанная область".
Хотя я дал формальное определение, но с точки зрения русского языка получается туфта: имеем "просмотренную область" и рядом один или два элемента, которые мы просмотрели и увидели равны они 0 или нет.
С термином "обработанная область" такой коллизии не возникло бы.
Приношу свои извинения.
-
В цикле Дейкстры, вроде как, каждая ветка (охрана) открывает (если условие истинно) точку входа (и только одну, даже если истинны несколько охран) для следующей итерации.
При этом порядок выполнения веток ЦД не детерминирован.
Но речь-то не про цикл Дейкстры, а про оператор WHILE-ELSIF-END в Обероне-07. В этом обероновском псевдо-ЦД порядок веток определён -- сверху вниз...
-
Выбирайте, какой Вам больше по душе...
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
:)
Но почему же не
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END; ???
-
Выбирайте, какой Вам больше по душе...
WHILE (i < LEN(a)) & (~oneZero OR a[i] # 0) DO oneZero := a[i] = 0; INC(i) END;
:)
Но почему же не
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END; ???
1.потому что речь идет о варианте от info21, значит
2.потому что та строка, что Вы предлагаете не эквивалентна исходному циклу. (В исходном - или вышли за пределы или i указывает на конец 00, а в здесь - на начало)
3.потому что мне по душе больше условие i<LEN(a) . Вышли за пределы - значит не нашли в пределах.
-
Но почему же не
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END; ???
1.потому что речь идет о конкретном варианте от info21
2.потому что та строка, что Вы предлагаете не эквивалентна исходному циклу. (В исходном - или вышли за пределы или i указывает на конец 00, а в здесь - на начало)
3.потому что мне по душе больше условие i<LEN(a) . Вышли за пределы - значит не нашли в пределах.
-
Но почему же не
WHILE (i < LEN(a)-1) & (a[i] # 0 OR a[i+1] # 0) DO INC(i) END; ???
1.потому что речь идет о конкретном варианте от info21
2.потому что та строка, что Вы предлагаете не эквивалентна исходному циклу. (В исходном - или вышли за пределы или i указывает на конец 00, а в здесь - на начало)
3.потому что мне по душе больше условие i<LEN(a) . Вышли за пределы - значит не нашли в пределах.
Зато мой вариант более наглядно показывает суть того, что делает этот цикл ))
-
Или вся соль в том, чтобы инвариант и охрана обязательно явно были в условии цикла?
Типа переписываю это:
http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133 (http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133)
так:
Процедура КнопкаВыполнитьНажатие(Кнопка)
Массив = Новый Массив;
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(0);
Граница = Массив.ВГраница();
ТекущийИндекс = 0;
Пока ТекущийИндекс < Граница И НЕ (Массив[ТекущийИндекс] = 0 И Массив[ТекущийИндекс + 1] = 0) Цикл
ТекущийИндекс = ТекущийИндекс + 1;
КонецЦикла;
Если ТекущийИндекс < Граница И Массив[ТекущийИндекс] = 0 И Массив[ТекущийИндекс + 1] = 0 Тогда
Сообщить(ТекущийИндекс);
Иначе
Сообщить("Хрен");
КонецЕсли;
КонецПроцедуры
... и все становится по науке?
-
... и все становится по науке?
неплохо ... сказано ;D
-
Зато мой вариант более наглядно показывает суть того, что делает этот цикл ))
Тогда уж так чтоб не придираться :)
i:=2; WHILE (i < LEN(a) & (a[i-1] # 0 OR a[i] # 0)) DO INC(i) END; j
одну скобку ) я тоже пропустил
-
Типа переписываю это:
http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133 (http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133)
так:
...
... и все становится по науке?
Если в 1С нумерация элементов массива идёт с 0 до (Массив.ВГраница()-1), то видимо надо сделать так:
Граница = Массив.ВГраница() - 1;
-
Зато мой вариант более наглядно показывает суть того, что делает этот цикл ))
Тогда уж так чтоб не придираться :)
i:=2; WHILE (i < LEN(a) & (a[i-1] # 0 OR a[i] # 0)) DO INC(i) END;
Если нумерация элементов массива идёт с нуля, то такой вариант не обнаружит два нуля в самом начале массива -- первый элемент массива вообще не будет просмотрен.
-
Зато мой вариант более наглядно показывает суть того, что делает этот цикл ))
Тогда уж так чтоб не придираться :)
i:=2; WHILE (i < LEN(a) & (a[i-1] # 0 OR a[i] # 0)) DO INC(i) END;
Если нумерация элементов массива идёт с нуля, то такой вариант не обнаружит два нуля в самом начале массива -- первый элемент массива вообще не будет просмотрен.
Да, конечно i:=1; ...
Я имел ввиду 2-й элемент массива
Привык, понимаете, с единицы считать :)
-
Типа переписываю это:
http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133 (http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133)
так:
...
... и все становится по науке?
Если в 1С нумерация элементов массива идёт с 0 до (Массив.ВГраница()-1), то видимо надо сделать так:
Граница = Массив.ВГраница() - 1;
В 1с Массив.ВГраница() = Массив.Количество() - 1
-
Озарённый новым пониманием инварианта, "изложенного" в http://oberspace.dyndns.org/index.php/topic,331.msg9234.html#msg9234 (http://oberspace.dyndns.org/index.php/topic,331.msg9234.html#msg9234) .
Вот http://forum.oberoncore.ru/viewtopic.php?p=72961#p72986 (http://forum.oberoncore.ru/viewtopic.php?p=72961#p72986)
как дополнение или даже как главный ответ. QWERTYProgrammer всех уделал :)
-
Озарённый новым пониманием инварианта, "изложенного" в http://oberspace.dyndns.org/index.php/topic,331.msg9234.html#msg9234 (http://oberspace.dyndns.org/index.php/topic,331.msg9234.html#msg9234) .
Вот http://forum.oberoncore.ru/viewtopic.php?p=72961#p72986 (http://forum.oberoncore.ru/viewtopic.php?p=72961#p72986)
как дополнение или даже как главный ответ. QWERTYProgrammer всех уделал :)
Наверно таки http://forum.oberoncore.ru/viewtopic.php?p=72961#p72986
(урлы не обязательно тэгами "[url]" обвешивать, движог форума сам распознает урл как урл-гиперссылку)
-
Озарённый новым пониманием инварианта, "изложенного"
Кстати, а что это мы прицепились к инвариантам именно цикла? Почему бы не поговорить о инварианте функций/процедур. Это не менее важная тема.
-
Кстати, а что это мы прицепились к инвариантам именно цикла?
Название темы не позволяет :)
-
Кстати, а что это мы прицепились к инвариантам именно цикла? Почему бы не поговорить о инварианте функций/процедур. Это не менее важная тема.
Инварианты функций/процедур? А что это? о_О
Насколько я знаю, инварианты имеются у циклов и у объектов (в ООП).
А у функций и процедур, видимо, должны быть контракты? Что на входе, что на выходе, за какое время производится работа/вычисление...
-
А вот вам ещё вариантик:
i := 0;
mb_found := FALSE;
found := FALSE; (* found = (a[i-1] = 0) и (a[i] = 0) *)
WHILE i < LEN(a) & ~found DO
IF a[i] = 0 THEN
IF mb_found THEN found := TRUE ELSE mb_found := TRUE END
ELSE
i := i+1
END
END
-
Кстати, а что это мы прицепились к инвариантам именно цикла? Почему бы не поговорить о инварианте функций/процедур. Это не менее важная тема.
Инварианты функций/процедур? А что это? о_О
Насколько я знаю, инварианты имеются у циклов и у объектов (в ООП).
А у функций и процедур, видимо, должны быть контракты? Что на входе, что на выходе, за какое время производится работа/вычисление...
Нет. Еще нужны инварианты. Если инвариант нарушен (в процессе работы. не важно из за действий внутри самой процедуры, или из за внешнех факторов), то нет никакого смысла продолжать выполнение процедуры.
-
А вот вам ещё вариантик:...
010
Первый нуль - mb_found = true, затем единица, затем срабатывает успех, что не верно. mb_found сбрасывать нужно.
Напомнило:
...
WHILE (i < LEN(a)) & (ChainLen < CHAIN_LEN) DO
IF a[i] = CHAIN_BYTE THEN
INC(ChainLen);
ELSE
ChainLen := 0;
END;
INC(i);
END;
...
-
"Что за херня? Я не могу уверенно, быстро и без ошибок написать цикл длиной порядка 10 строк, при том, что общая идея мне ясна. Не мудак ли я?
Хочу перезжать подобные задачи как трактор."
При этом в твоем решении "сопоставление с образцом" есть всего один маленький цикл, а всю грязную работу делает рекурсия ;)
-
Религиозные войны... бессмысленные и беспощадные.
Циклы существуют не сами по-себе, цикл ради цикла - еще более бессмысленная вещь. Если мы навешали десятиэтажные условия в качестве охраны и при нарушении охраны вышли из цикла, а потом еще навешали те же самые десятиэтажные условия для проверки того, чего же мы там нациклили, чтобы выполнить какие-то действия, требуемые при достижении тех или иных условий, то ясное дело, что не только Гондурас в огне, но и в Королевстве Датском не все в порядке. Ясное дело, если все эти десять этажей были нужны только чтобы плюсануть переменную, то это одно, но, циклы нужны для более прозаических вещей - для выполнения более полезных действий, зависящих от тех или иных состояний(условий), которые могут меняться в процессе работы.
Приверженцам десятиэтажных охран и семиэтажных проверок после цикла предлагаю по такому принципу даже не 10 этажей покрасить, а всего лишь один забор. Тогда наступает понимание, что если у нас над циклом 10 этажей условий, то мы неверно построили алгоритм и необходимо повторно провести декомпозицию...
Ясное дело, что если мы построили цикл с 10-ти этажной охраной, цикл, который сам себе условие", то это только от того, что думать мы не хотим, прогонять алгоритм в голове не желаем, ведь собрать все условия в одной точке намного проще, правда и полезной работы при этом цикл выполнит существенно меньше.
-
что думать мы не хотим, прогонять алгоритм в голове не желаем, ведь собрать все условия в одной точке намного проще, правда и полезной работы при этом цикл выполнит существенно меньше.
Если писать всегда верный код, то не имеет значения как ужасно он выглядит. А если в коде есть ошибка и её надо найти, то неплохо бы писать так, чтобы искать было проще.
Например, есть процедура из 25 строк. У неё в середине цикл на 12 строк. Мы прочли код до начала цикла, и в нём ошибки не было. Дальше мы читаем заголовок цикла. Нередко (но не возьмусь утверждать, что в подавляющем количестве случаев) информации в заголовке будет достаточно, чтобы понять: ошибка внутри цикла или за его пределами.
Это важно, потому что гонять код внутри головы обычно затратнее, чем писать его. У меня даже бывало такое, что цикл изначально написан правильно, но я при его прогоне через голову "обнаруживал" в нём ошибку. Начинал исправлять, а оно не исправляется. Через некоторое время приходило осознание того, что ошибки в нём не было, и приходилось возвращаться назад и продолжать поиски.
Я тоже против огромных условий у цикла. Тоже за продуманную декомпозицию. Но я против искусственного уменьшения и размазывания условия работы цикла по его телу.
-
Религиозные войны... бессмысленные и беспощадные.
Ну нет.. ЛЮБАЯ стычка делает нас сильнее, если не убивает , конечно...
-
Инварианты функций/процедур? А что это? о_О
Насколько я знаю, инварианты имеются у циклов и у объектов (в ООП).
А у функций и процедур, видимо, должны быть контракты? Что на входе, что на выходе, за какое время производится работа/вычисление...
ну ну ... :) это то, что позволяет "новые" решения (классы решений) в общем случае... в любимом вами опусе от Дейксты (если я не ошибаюсь) показан пример "нестандартной" реализации алгоритма Евклида на основе подобного подхода...
-
Если писать всегда верный код, то не имеет значения как ужасно он выглядит. А если в коде есть ошибка и её надо найти, то неплохо бы писать так, чтобы искать было проще.
Всегда верный код пишется не всегда ) На его правильность может повлиять даже фаза Луны.
Но я хочу сказать всего лишь: "Циклы разные нужны, циклы разные важны".
При их конструировании нужно учитывать множество факторов, и уже исходя из их оценки выбирать тот или иной подход. Ни один из подходов не является "православным", "кошерным", "единственно возможным" и "истинно правильным". Это просто подход, и ничего более...
-
Но я хочу сказать всего лишь: "Циклы разные нужны, циклы разные важны".
При их конструировании нужно учитывать множество факторов, и уже исходя из их оценки выбирать тот или иной подход. Ни один из подходов не является "православным", "кошерным", "единственно возможным" и "истинно правильным". Это просто подход, и ничего более...
Так то оно так, но пока есть ЦЕНА ошибки... интерес к методам позволяющим уменьшить их вероятность будет наблюдаться (в этом смысле Петр может не беспокоится о "популярности" подобных топиков :) ). Ну а если он является фаном "метода инвариантов" - то возможно он когда нибудь и предложит конкурентноспособную методу (хотя бы для ОПРЕДЕЛЕННОГО класса задач...)
-
Приверженцам десятиэтажных охран и семиэтажных проверок после цикла предлагаю по такому принципу даже не 10 этажей покрасить, а всего лишь один забор. Тогда наступает понимание, что если у нас над циклом 10 этажей условий, то мы неверно построили алгоритм и необходимо повторно провести декомпозицию...
Kemet, чем писать всякие фантазии про 10 этажей (почему не 20, кстати?), приводите примеры.
То же относится к Dizer'у.
-
То же относится к Dizer'у.
А причем тут Dizer - эту кашу заварили вы... заварив ее - нормально не ответили ни на один вопрос.. а все ваши ремарки - напоминают мне реакцию школоты решившего по учебнику
пару задач, вообразившего себя богом, поучающего других - причем, с большей степенью апломба... и какие тут фантацизии :D - для подтверждения вышесказанного вполне ДОСТАТОЧНО собрать вместе ВСЕ ваши высказывания в этом топике :D
-
Инвариант для цикла в последнем решении Александр Шостак: в переменной ChainLen лежит длина хвоста просмотренной области, состоящего из нулей.
А моя ошибка вот в чем: инвариант для решения Александр Шостак не полон. Ниоткуда не следует, что найденный кусок будет первым от начала массива. Я заметил, да было уже поздно. Желающие могут попробовать сформулировать недостающую часть.
Какой-то неказистый инвариант получается для решения Александра Шостака. Поскольку в отличие от решения info21 цикл не завершается при "заглядывании вперед", то инвариант должен звучать как-то так:
в просмотренной на предпоследней итерации области нет последовательности CHAIN_LEN нулей и в переменной ChainLen лежит длина хвоста просмотренной на последней итерации области, состоящего из нулей.
Или есть более элегантные варианты?
-
Я так сформулировал: в обработанной :) области содержится не более одного куска нулей длиной CHAIN_LEN и в переменной ChainLen лежит длина хвоста просмотренной области, состоящего из нулей.
-
Я предпочитаю не увлекаться формализмом, использовать оправдавшие себя шаблоны вроде линейного поиска, но всё же попробую по шагам в википедии доказать вариант инварианта:
Подготовка:
CONST
CHAIN_LEN = 2;
CHAIN_BYTE = 0;
ChainLen := 0;
i := 0;
WHILE (i < LEN(a)) & (ChainLen < CHAIN_LEN) DO
IF a[i] = CHAIN_BYTE THEN
INC(ChainLen);
ELSE
ChainLen := 0;
END;
INC(i);
END;
GetChainLen - вспомогательная функция, принимающая подмассив и возвращающая длину непрерывной цепочки нулей в нём от конца к началу. Несуществующие индексы игнорируются.
Инвариант:
i <= LEN(a) // Из заголовка цикла
ChainLen <= CHAIN_LEN // Из заголовка цикла
GetChainLen(a[i - 2.. i - 1]) = ChainLen
1. Доказывается, что выражение инварианта истинно перед началом цикла.
Минимальная длина массива - 0. Максимальная: > 0. i = 0. i <= LEN(a).
ChainLen = 0. CHAIN_LEN = 2. 0 <= 2.
GetChainLen(a[-2..-1]) = 0. 0 <= 2.
2. Доказывается, что выражение инварианта сохраняет свою истинность после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении цикла инвариант будет выполняться.
Переменная i увеличивается на 1 безусловно. Первая часть охраны цикла останавливает повторы при i = LEN(a). Следовательно, i <= LEN(a) верно после каждой итерации.
Переменная ChainLen может расти вверх максимум на 1 за каждую итерацию. Вторая часть охраны цикла гарантирует равенство ChainLen <= CHAIN_LEN. Скачок с 0 до 3 таким образом невозможен.
Если текущий символ не нулевой, то ChainLen обнуляется. GetChainLen анализирует длину цепочки с хвоста и тоже вернёт 0.
Если текущий символ нулевой, то ChainLen растёт на единицу. Точно также поступает при анализе длины и GetChainLen.
Переменная i в конце итерации указывает на следующий за текущим символ. Следовательно,
GetChainLen(a[i - 2.. i - 1]) = ChainLen выполняется.
3. Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
Хотим получить ChainLen = 2 при успехе. Тогда i - 2 есть начало цепочки. При неудаче ChainLen < 2, а i = LEN(a).
4. Доказывается (возможно — без применения инварианта), что цикл завершится, то есть условие завершения рано или поздно будет выполнено.
Безусловное увеличение i на 1 после каждой итерации при положительной длине массива гарантирует конечное время выполнения и завершение. Вторая охрана цикла (ChainLen < CHAIN_LEN) гарантирует выход, когда цепочка наберёт критическую длину.
5. Истинность утверждений, доказанных на предыдущих этапах, однозначно свидетельствует о том, что цикл выполнится за конечное время и даст желаемый результат.
Аминь.
Если серьёзно, то схема линейного поиска остаётся в силе. Просто условие окончания не примитивное сравнение элемента с искомым, а длина непрерывной цепочки, которая считается через несложное IF-ELSE.
-
Я так сформулировал: в обработанной :) области содержится не более одного куска нулей длиной CHAIN_LEN и в переменной ChainLen лежит длина хвоста просмотренной области, состоящего из нулей.
Да, так пожалуй лучше.