Выход из цикла или смерть Кощея

[Илья Ермаков]

Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.

Между прочим, три года назад в Новосибирском академгородке я обсуждал ДРАКОН с В. Н. Касьяновым (а затем немного переписывались по этой теме).
Его очень интересует всё, что связано со сводимыми (они же аранжируемые) графами и их применением для анализа свойств программ - он считает, что это недоисследованное и перспективное направление.

[Peter Almazov]

"Не так"?!
Ну, мля, как дворниками пообщался.
Сказано же, тело цикла выполняется лишний раз. Здесь это "i=i+1".
Но тело цикла может быть несколько другим.

Вот пусть оно сначала будет несколько другим, чтобы были веские причины уходить от варианта, который наиболее "прописан" для применения в неотягощённом "марианскими впадинами" случае.

Раскатывать условия из общего условия цикла куда-то в его внутренности - это нужны очень серьёзные агрументы.
Вы в исходном сообщении привели один: операции получения уток-иголок дорогие. Вам и дали решение для этого случая.
Про дороговизну i := i + 1 речи не было.

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

[valexey_u]

Не надо смешивать уважаемых людей с запредельно безграмотной околодраконной публикой.

Между прочим, три года назад в Новосибирском академгородке я обсуждал ДРАКОН с В. Н. Касьяновым (а затем немного переписывались по этой теме).
Его очень интересует всё, что связано со сводимыми (они же аранжируемые) графами и их применением для анализа свойств программ - он считает, что это недоисследованное и перспективное направление.

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

По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис. У него неплохо описана семантика (на порядок лучше драконовых). При этом язык маленький, и анализатор строящий по исходнику нужный граф будет написать просто. Именно поэтому моя сестра например выбрала для своих исследований в качестве первого подопытного кролика именно Оберон (а затем Lua).

А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).

[Peter Almazov]

Если Вы не можете обсуждать вопрос "по существу", без своей личной идиосинкразии, то это Ваша проблема.

Вы правы, я не могу обсуждать вопрос "по существу".
Примерно так же, как врачи не смогут обсуждать "по существу" вопрос "Надо ли мыть руки перед операцией или достаточно помолиться".

[Peter Almazov]

А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).

Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.

[valexey_u]

А дракон.. Дракон хорош для попсовой алгоритмизации (например для рецептов приготовления чего-нибудь съестного).

Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.

Кстати, а чем Дракон принципиально от оной блок-схемы отличается?

[Peter Almazov]

Кстати, а чем Дракон принципиально от оной блок-схемы отличается?

Вот это уже не ко мне   

[Илья Ермаков]

Я даже могу продолжить верную логическую цепочку от valexey_u и здесь тоже добавить "а причем тут дракон?".
Для этого достаточно блок-схемы.

Если Вы не понимаете разницы между графом произвольной запутанности и графом с ограниченной топологией, между рисунком, в котором выбор, "куда дальше повести линию" и "куда положить вот это - справа или слева" - и между строгой конструкцией, которая диктует однозначно размещение на плоскости и является конкретным классом графов, то это - баранья упёртость, Пётр. На этом диагнозе и покончим. Все Ваши рассуждения о ДРАКОНе гроша ломаного не стоят, потому что Вы хотите понимаеть, о чём веду речь я. (А не масса бухгалтеров вокруг ДРАКОНа). То ли намеренно придуриваетесь, то ли от своей идиосинкразии у Вас выключается разумное восприятие ...

[Peter Almazov]

На этом диагнозе и покончим.

Разумно.

Ну а с "правильным постусловием" как?
А то вспоминается Тарас Бульба: "Ну что, сынку, помогли тебе твои ляхи графы?"

[Илья Ермаков]

По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис.

С Обероном всё ясно. Его граф - структурный в классическом понимании, т.е. линейно-блочный (последовательность блоков с одним входом и одним выходом).

А интересна более сводобная топология сводимых графов (в которых у любой вершины есть только одна последовательность ведущих в неё доминаторов). ДРАКОН относится именно к этой топологии. Паронджанов определил её конструктивно (в терминах начального объекта и допустимых над ним операций, а дальше говорится, что "всё множество правильных схем - это всё множество, которое можно получить применением этих операций).
А если определять аксиоматически, то это, оказывается, сводимый граф.

Я же привёл там выше ссылку на статью, где это разбиралось.

[Илья Ермаков]

.... помогли тебе твои...

Эх, и не говорите нет от них никаких доходов, интерес один...

Ну, в таком случае, может, хоть вы напишете "правильное постусловие". А то 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


[valexey_u]

По моему, в качестве отправной точки для подобных изысканий, в качестве первого подопытного кролика, намного лучше подошел бы Оберон-07 - у него есть довольно четко описанный синтаксис.

С Обероном всё ясно. Его граф - структурный в классическом понимании, т.е. линейно-блочный (последовательность блоков с одним входом и одним выходом).

А интересна более сводобная топология сводимых графов (в которых у любой вершины есть только одна последовательность ведущих в неё доминаторов). ДРАКОН относится именно к этой топологии. Паронджанов определил её конструктивно (в терминах начального объекта и допустимых над ним операций, а дальше говорится, что "всё множество правильных схем - это всё множество, которое можно получить применением этих операций).
А если определять аксиоматически, то это, оказывается, сводимый граф.

Я же привёл там выше ссылку на статью, где это разбиралось.

По моему, ты забываешь про вызовы функций. Без них анализ не полон. Сама по себе последовательность statement'ов достаточно скучна и не интересна.

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

[Peter Almazov]

Если я буду составлять этот цикл с нуля, с полными рассуждениями, то буду делать это так.
...

Долго не мог заставить себя прочитать все внимательно до конца. Но все-таки "осилил".

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

[Илья Ермаков]

Тем не менее, могу сказать, что не все безнадежно. (А поначалу показалось, что безнадежно).
Нет, определенно, есть проблеск надежды.

Да ну... Тогда я возьму с полки пиражок и буду ждать разбора от сенсея... Надеюсь, что встречно будет также потрачено время на эту задачу.

[ilovb]

Товарищи, да о чем вы рассуждаете. Обычный линейный поиск.

Илья, вот в этом вашем шаблоне и заключен весь алгоритм:

Код: [Выделить]

i := 0;
WHILE (игла = NIL) & (i # len) DO
искать иглу в i-м cундуке;
INC(i)
END
Все что кроме - это операция на гландах через задницу.