OberonCore https://forum.oberoncore.ru/ |
|
Базовые паттерны циклов https://forum.oberoncore.ru/viewtopic.php?f=82&t=2257 |
Страница 1 из 4 |
Автор: | Илья Ермаков [ Суббота, 18 Апрель, 2009 00:05 ] |
Заголовок сообщения: | Базовые паттерны циклов |
Ветка подходящая... Давайте зафиксируем для новичков два базовых паттерна циклов. Итак, полный проход - есть некая последовательность... чего угодно. Элементов, шагов, ситуаций... Длина не известна, но известно условие проверки её окончания. Т.е. имеет место вот эта самая "обратная связь" - продвинулись на шаг, проверили, не достигнута ли ещё цель. Схема "полный проход" Код: взять_первую_ситуацию; WHILE ~конец_ситуаций (* т.е. "удалось взять очередную ситуацию" *) DO (* Предусловие: имеем текущую ситуацию, подлежащую обработке *) полезное_действие_в_текущей_ситуации; переход_к_следующей_ситуации END Если видим полный проход в задаче, то сводим его строго к такому шаблону, без фантазий. Пример с потоковым чтением. Правильно организованный интерфейс потокового чтения предоставляет функцию "считать очередной элемент" и признак, который показывает, было ли считывание успешным. Код: reader.Read(elem); WHILE reader.Done() DO ...работаем с elem... reader.Read(elem) END Очевидно, что попыток чтения и должно быть на одну больше, чем оборотов цикла с полезным действием. И "дублирование" как раз по этой причине возникает, и любые попытки его "убрать" не приведут к прояснению ситуации, а только к запутыванию и потере прозрачности. В других случаях начальное действие и переход могут быть разными: Код: it := items; WHILE it # NIL DO ...работаем с it... it := it.next END Действия "взять_начальную", "перейти_к_следующей", не говоря про само полезное действие, могут быть сколь угодно необычными, самое главное - узнать саму семантику полного прохода, и без фантазий написать по шаблону. Схема "линейный поиск" Та же история - последовательность чего угодно... Задача - найти такую ситуацию, которая удовлетворяет условию поиска, или показать, что её нет (достигли конца последовательности). Код: взять_первую_ситуацию; WHILE ~конец_ситуаций & ~( ... условие поиска ..) DO ... возможно, но не очень часто встречается - действие над текущей ситуацией ... взять_следующую_ситуацию END; IF ~конец_ситуаций THEN ... нашли, делаем что надо, с той ситуацией, на которой остановился цикл... ELSE ... не нашли, делаем что-то, если нужно END Важно, чтобы & вычислялся сокращённо (в нормальных языках так и есть), т.к. условие поиска может не иметь смысл в случае конец_ситуаций. Касательно Дракона - там не нужно повторять IF после цикла, там за счёт разделения конъюнкции WHILE на две последовательных проверки получается два параллельных исхода из цикла - "нашли" и "не нашли", на которые и нанизываем дальнейшие действия. Очень выразительно. viewtopic.php?p=21377#p21377 Касательно этого был ещё тут пример - viewtopic.php?f=7&t=1443 Про то, что как только узнали стандартную схему, дальше лучше "без фантазий". Пример с "узнаванием" линейного поиска (Из программки одного моего студента) Имеется граф потока вычислений. Т.е. ориентированный граф без циклов, вершина - это операция, по дугам входят аргументы. Его можно обсчитывать в режиме потока данных (распространяя "волну" от аргументов к результатам), а можно "лениво" (от интересующего нас конечного узла запрашивая рекурсивно назад). Если считаем в первом режиме, то возникает "фронт волны" (или ещё говорят "рабочая стопка", workpile). Так вот, на каждом витке workpile-алгоритма мы ищем в стопке те узлы графа, для которых уже готовы все аргументы. Нужно написать для узла графа функцию ReadyForCalc(node): BOOLEAN. Понимающий студент сразу видит, что это = "для любого непосредственного предка node выполнено defined". Т.е. A anc : anc IN Ancestors(node) : anc.defined, где A - квантор всеобщности, A. Точно так же он знает, что это эквивалентно ~ ( E anc : anc IN Ancestors(node) : ~anc.defined, т.е. "среди предков не существует такого, для которого ~defined". Т.е. чтобы доказать, что "для любого..." нужно построить "опровергающий" линейный поиск обратного условия и вернуть отрицание результата этого поиска. Ну и конкретно это отображается в код (граф хранится на квадратной матрице, так, как его вводят в редакторе - для простоты, чтоб не грузить студента ещё задачей авторазмещения элементов на листе): Код: PROCEDURE ReadyForCalc (g: Flow.Grid; ref: Flow.Ref): BOOLEAN; VAR j: INTEGER; cell: Flow.Cell; BEGIN (* A cell : cell IN Anc(g[ref]) : cell.defined *) (* ~ ( E cell : cell IN Anc(g[ref]) : ~cell.defined *) (* т.е. линейный поиск ячейки с ~cell.defined. RETURN поиск_не_удался *) ASSERT (g[ref.x, ref.y].argCount > 0, 20); cell := g[ref.x, ref.y]; j:= 0; WHILE (j < cell.argCount) & g[cell.args[j].x, cell.args[j].y].defined DO INC(j); END; RETURN j = cell.argCount END ReadyForCalc; Вот эта вот задача - проверка выполнения какого-то условия для всех ситуаций - тоже часто встречается, её надо узнавать и по такой схеме трансформировать в "опровергающий" линейный поиск. Наконец, и сам цикл продвижения волны по графу тоже сводится к шаблонному полному проходу, надо только понять, какая тут последовательность ситуаций. За ситуацию примем набор необсчитанных пока вершин, хранящихся в рабочей стопке (фронте). Т.е. инвариантом цикла будет (* INV: в front находятся ещё не обсчитанные вершины, ~defined *). При этом очевидно, что целесообразно хранить в стопке непосредственно только те вершины, которые имеют шанс стать обсчитанными на очередном витке. Заведём две операции: Calc ищет в стопке те узлы, которые ReadyForCalc и выполняет расчёт их значений. Step ищет в стопке обсчитанные вершины (они там могут оказаться в середине витка цикла, когда инвариант временно нарушен после Calc), выбрасывает их из стопки, а взамен помещает их непосредственных последователей (тех, которые ещё не попали). Имеем полный проход: Код: поместить_в_стопку_начальные_аргументы; Step; WHILE количество_в_стопке > 0 DO Calc; Step END Как всегда, с помощью первой части тела цикла мы продвинулись вперёд, но нарушили соотношение-инвариант, с помощью второй - восстановили инвариант, после чего идёт проверка условия окончания. Всего-то и делов. Поподробнее об инварианте цикла. Инвариант - "рельсы", по которым он едет - что истинно до начала цикла ("поставили на рельсы") и в конце каждого витка. (А раз в конце каждого витка, то и после завершения цикла тоже. Вот ещё одна причина не делать досрочных выходов из цикла. Тогда пишущему и читающему придётся дополнительно убеждаться, что в каждом месте цикла, где он прерывается, инвариант восстановлен.) Вот тут ещё было об инварианте: viewtopic.php?p=21375#p21375 Ну что, неужто такая "жуткая математика"? Простые, естественные рассуждения, ровно настолько формальные, насколько это удобно, чтобы "иметь почву под ногами". |
Автор: | Илья Ермаков [ Суббота, 18 Апрель, 2009 00:08 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Цитата: --- нужно чему-то "теоретическому, алгоритмически правильному" учить студентов (компостировать --- им мозги, отучать думать, приучать автоматически отвечать заученными фразами); Вы издеваетесь, что ли?? Написание кода - это "думать"? Естественное желание любого специалиста, кроме чисто-пальцегнутого-программёра, освободить как можно больше времени для работы над задачей, а строить код просто как "проекцию" общих соображений из головы. Вот и надо учить, как гладко и безошибочно "проецировать". |
Автор: | Axcel [ Суббота, 18 Апрель, 2009 09:41 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Кажется это и есть точка разногласий: 1. Язык программирования средства записи для выполнения продуманного решения Цитата: ... а строить код просто как "проекцию" общих соображений из головы. Вот и надо учить, как гладко и безошибочно "проецировать" 2. Язык как средство (дополнительное) формирования этих общих соображений, - "умственный велосипед". |
Автор: | igor [ Суббота, 18 Апрель, 2009 10:15 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
2 sia: К сожалению, из-за острой нехватки времени, не имею возможности поддержать нашу интересную беседу. Прошу не расценивать это как попытку сбежать от разговора. У нас с Вами много общего. Я так же "носился" на втором курсе с перфокартами. Специальность "Радиотехника". Так же многие мои убеждения "дошли" до меня не через голову, а через руки. Помню как-то один из своих первых проектов я переписывал с нуля не меньше десяти раз. Жуткий привереда. Всё искал выход из очередного "кризиса жанра". И, кстати, нашёл Вот только наши убеждения весьма различны. Многое (но далеко не всё) из того, что я мог бы Вам сказать, Вы найдёте на страницах этого замечательного портала |
Автор: | igor [ Суббота, 18 Апрель, 2009 10:32 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Илья Ермаков писал(а): Ветка подходящая... Давайте зафиксируем для новичков два базовых паттерна циклов. "В рамочку, и на стену!" ... Илья, Вы не поверите! Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына. Несмотря на обилие компьютерной литературы, почитать по самой дисциплине программирования практически нечего ! Подчёркиваю, не по какому-нибудь языку или системе, а именно по самой дисциплине программирования. Имхо, в этой нише образовался такой информационный голод, что любой захудалый учебник будет проглочен вместе с потрохами. Другой такой пример -- книжки по оберонам. Книгу Свердлова я зачитал до дыр. PS Извините за OFFTOP. Наболело, знания приходиться собирать буквально по крупицам. Да ещё сильно фильтровать, потому что пишущих "спецов-умников" много, а истина одна |
Автор: | Info21 [ Суббота, 18 Апрель, 2009 12:30 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
igor писал(а): Илья Ермаков писал(а): Ветка подходящая... Давайте зафиксируем для новичков два базовых паттерна циклов. "В рамочку, и на стену!" ... Илья, Вы не поверите! Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына. http://www.inr.ac.ru/~info21/08.pdf |
Автор: | igor [ Суббота, 18 Апрель, 2009 13:01 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Info21 писал(а): Давно уж заPDFено на стене для юношей: Спасибо! Качнул.http://www.inr.ac.ru/~info21/08.pdf Только сейчас расшарили ? Файл ".../07.pdf", например, не доступен. И другие. |
Автор: | Info21 [ Суббота, 18 Апрель, 2009 13:55 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
igor писал(а): Info21 писал(а): Давно уж заPDFено на стене для юношей: Спасибо! Качнул.http://www.inr.ac.ru/~info21/08.pdf Только сейчас расшарили ? Файл ".../07.pdf", например, не доступен. И другие. Остальное просто не выкладывалось. |
Автор: | QWERTYProgrammer [ Суббота, 18 Апрель, 2009 17:03 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Info21 писал(а): Остальное просто не выкладывалось. И не планируется выложить или опубликовать? |
Автор: | Valery Solovey [ Суббота, 18 Апрель, 2009 17:06 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
igor писал(а): Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына. Это Вы поторопились : ).Цитата: Код: (* Предусловие: имеем текущую ситуацию, подлежащую обработке *) |
Автор: | Alexey_Donskoy [ Суббота, 18 Апрель, 2009 18:21 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Илья Ермаков писал(а): Важно, чтобы & вычислялся сокращённо (в нормальных языках так и есть), т.к. условие поиска может не иметь смысл в случае конец_ситуаций. Не ожидал такого безобразия - делаем неявные предположения о существенных свойствах исполнителя?!
|
Автор: | Info21 [ Суббота, 18 Апрель, 2009 18:23 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
QWERTYProgrammer писал(а): Info21 писал(а): Остальное просто не выкладывалось. И не планируется выложить или опубликовать? |
Автор: | Info21 [ Суббота, 18 Апрель, 2009 20:01 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Alexey_Donskoy писал(а): ... делаем неявные предположения о существенных свойствах исполнителя?! Почему неявные. Очень даже явные. Явные и фундаментальные. Это в чистой математике об областях определения функций (включая предикаты) не принято говорить как о вещах подразумеваемых. А здесь всё явно должно быть.
|
Автор: | stern [ Суббота, 18 Апрель, 2009 20:37 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Info21 писал(а): QWERTYProgrammer писал(а): Info21 писал(а): Остальное просто не выкладывалось. И не планируется выложить или опубликовать?А как это проверить? Я, как физик по убеждению, придерживаюсь такого мнения: только экспериментально. Почему-бы не поставить эксперимент на посетителях данного форума? Собрать мнения, пожелания, оценки. Выскажу еще одно свое мнение: судя по тому, что Вы уже выложили на всеобщее обозрение, Ваши лекции представляют несомненный интерес. |
Автор: | Info21 [ Суббота, 18 Апрель, 2009 21:45 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
stern писал(а): ... несомненный интерес. Спасибо за комплимент. Проблемы две. 1) основная работа.2) Только прошу лично не воспринимать -- у нас же тут открытый форум, и народ всякий засветился, да еще молча приходят (но мы всё равно знаем, кто). Так вот, старые мастера учат, "дураку пол-работы не показывают". Это я к тому, что знаю про явно слабые куски, кои хорошо видны после перевода книжки Вирта (впрочем, в книжке тоже видны слабости), теперь нужно это всё как-то выгладить. 3) Формат лекций и формат книжки -- разные по смыслу и цели. Преобразование достаточно трудоемко, и тут мы возвращаемся к 1) |
Автор: | stern [ Суббота, 18 Апрель, 2009 22:25 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
К умным себя никак не причисляю, поэтому на звание "дурак" не обижаюсь . Если серьезно, то остается только сожалеть. Но это позиция Автора, и ее следует уважать. |
Автор: | Info21 [ Суббота, 18 Апрель, 2009 23:28 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
stern писал(а): ... это позиция ... Всё банальней: поговорка старых мастеров -- как со временем понимаешь -- есть сумма вполне конкретного и достаточно неприятного опыта. А никакая не позиция
|
Автор: | Илья Ермаков [ Воскресенье, 19 Апрель, 2009 11:25 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Valery Solovey писал(а): Цитата: Код: (* Предусловие: имеем текущую ситуацию, подлежащую обработке *) Валерий, обратите внимание, где это стоит. Это предусловие для очередной итерации цикла. Следующее, конечно, из инварианта - но инвариант более широкий - "имеем текущую ситуацию OR (count = 0)" |
Автор: | Валерий Лаптев [ Понедельник, 20 Апрель, 2009 17:36 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Info21 писал(а): stern писал(а): ... несомненный интерес. Спасибо за комплимент. Проблемы две. 1) основная работа.2) Только прошу лично не воспринимать -- у нас же тут открытый форум, и народ всякий засветился, да еще молча приходят (но мы всё равно знаем, кто). Так вот, старые мастера учат, "дураку пол-работы не показывают". Это я к тому, что знаю про явно слабые куски, кои хорошо видны после перевода книжки Вирта (впрочем, в книжке тоже видны слабости), теперь нужно это всё как-то выгладить. 3) Формат лекций и формат книжки -- разные по смыслу и цели. Преобразование достаточно трудоемко, и тут мы возвращаемся к 1) Проблемы три получилось Но номер 3 - это не проблема... Формат книжки совершенно не обязателен. Вполне пойдет и в формате лекций. Очень интересно почитать и посмотреть, как физики подходят к программированию... |
Автор: | Info21 [ Понедельник, 20 Апрель, 2009 19:39 ] |
Заголовок сообщения: | Re: В 101-й раз о грамотной алгоритмизации |
Валерий Лаптев писал(а): Очень интересно почитать и посмотреть, как физики подходят к программированию... Ну вот, совсем страшно стало... Нету там ничего особенного. Никакого доказательного программирования, три упражнения с конъюнкцией на цикл Дейкстры, и всё.
|
Страница 1 из 4 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |