OberonCore

При расчёте статистики по результатам ЕГЭ в регионе у нас в ОРЦОКО пришлось кое-что дописывать, т.к. федеральное ПО ужасное и не считает всё, что нужно.
Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена.
Программист сортирует экспортированные из системы результаты экзаменов в Excel по полю "номер паспорта" и дальше сохраняет в CSV одну только эту колонку. Т.е. имеется последовательность строк с номерами паспортов, где каждый номер повторяется (рядом) столько раз, сколько человек сдавал экзаменов.
Программист сейчас ваяет на ББ процедурку, которая посчитает статистику.
Я тоже тут накидал алгоритм. Не напрягая мозги, получился сразу цикл Дейкстры. Тестировать не тестировал, написал на бумажке.
Правда, программист не хочет его брать, говорит, что не понимает Колдует уже час над вложенными циклами, пытаясь, к тому же, это сделать прямо над TextMappers.Scanner.

Привожу свой вариант:

Программа правильная (не тестировал ), цикл Дейкстры оправдан.
Инвариант, как всегда, неправильный. Точнее, сильно неполный.
Кроме того, я бы для наглядности ввел термин "площадка".

Видимо описка
не INC(i), а INC(j) надо

Ну, фактически, я назвал ровно такой инвариант, который объясняет смысл переменных... А не инвариант для полной формализации цикла.

Да, спасибо.

Да, я вот не сразу понял, что для ББ это именно алгоритм... с записью ЦД на О-07... где-то с полминуты пытался въехать, как IF должен сочетаться с ELSIF на КП...

Кстати, в теле IF описка - круглая скобка инкремента не закрыта.

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

У программиста, видимо, получится по принципу того, с чего начинался этот пример - т.е. с дополнительными индексными переменными и операциями над ними.

Ну вот, всегда так с ЦД.

И инвариант не тот,

и школярская привычка в программировании использовать одно буквенные идентификаторы, при этом визуально мало различимые ( i , j ), а не слова наполненные смыслом из предметной области,

и ошибку признаем, но алгоритм не правим,

и запись алгоритма неизвестно на каком языке, "Правда, программист не хочет его брать, говорит, что не понимает",

и следуя принципу максимальной простоты, т.е. автомата Калашникова и применив декомпозицию необходимость в ЦД исчезнет.

Видимо описка
не INC(stat[j - i] ,
а INC(stat[j - i]) надо

Присоединяюсь к тому, что в данном случае ЦД особо и ничего не даёт, проход ведь до конца массива. IMHO наглядней даже без него, в теле тогда будет только IF без веток ELSE.
Несколько напрягает приспособление реализации алгоритма к случаю с пустым массивом.Это по идее надо обеспечивать в охватывающем коде (не вызывать или не выполнять, если не по чему считать). Тогда и последний INC stat будет безусловный.

Идиотское убеждение (от Info21), что инвариант нужен некоему дяде, причем только в редких, особо торжественных случаях, и только после того, как цикл написан, оставляю без комментариев.

Я говорю о том, что запись
(* Инвариант: [i, j) - интервал из одинаковых номеров паспортов *)
не ведет к построению правильного цикла. Предположим, в последовательности с самого начала идут номера паспортов 1,1,1,1,1. В некоем цикле i=2, j=4.
Между [i и j) одинаковые номера паспортов? - Одинаковые.
Устроит ли нас такая трактовка? - Нет, не устоит.

Шаг в правильном направлении: "в i содержится индекс начала последней площадки".

Эпитеты случаются быть и самоприменимыми

Какая разница, каким способом построить правильный цикл?
Идея Info21 относительно ЦД в том, что ЦД позволяет многие циклы вывести из категории "требует полностью формального вывода" в категорию "очевидно и правильно строится путём анализа семантики задачи".
Второй вариант более желателен, тогда как первый нужно применять только, если невозможен второй (с этим обычно не соглашаются математики и спорят с физиками и инженерами).

Напоминаю, что доказать - это не значит провести какие-то "священнодействия", а это значит предоставить проверяемую вещь в такой форме, в которой в её правильности может убедиться любой желающий.

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

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

Я придерживаюсь такого принципа:
WHILE должен работать не 1 и более раз, а 0 и более раз...
Т.е. "охранять" WHILE - только в крайних случаях...
В этой задаче, конечно, возникает некая шероховатость, что приходится охранять действие после WHILE.

Да, конечно, термин "площадка" стоит ввести и вписать в комментарий инвариант точнее. Не опуская очевидную, но достаточно ценную часть его, что i - это начало площадки.

Смысловые идентификаторы использую для внешних сущностей, локальные переменные имеет смысл называть короче, чтобы они выделялись.
Смысл их должен быть как можно более очевиден из самой процедуры (и инварианта в комментарии, если нужно). Процедура - обычно не более 10-20 строк....
Перепишите для сравнения с вместо i и j с именами currentAreaBeg и currentAreaEnd и сравните читаемость.


Алгоритм там правильный, опечатка "признанная" тоже была исправлена.


Примените, покажите. Убедиться в том, что два вложенных и тесно связанных цикла работают правильно, будет, думаю, труднее.

Вчера минут через 40 трудов и нескольких выходов покурить программист закончил свой вариант. Получилось вот что:



В общем, тоже разборчиво, но "подозрительно": два цикла манипулируют единственной переменной i и т. д.

Ну и "на закуску", для сравнения - разворачиваю ЦД в два вложенных цикла:



Если сравнивать ЦД и последний вариант (помня, что последний легко написался уже после ЦД), то плюсом ЦД является то, что он требует "полноты анализа ситуаций". Т.е. сразу перечисляешь на одном уровне и все возможные действия, и условия, при которых эти действия активизируются. Не думая о том, как между собой взаимодействуют вложенные циклы.
Но с точки зрения читателя вариант, преобразованный во вложенные, может быть попонятней. С другой стороны, вопрос, хотим ли мы сохранять в коде понятность хода мыслей? Иногда смотришь на понятный алгоритм, но понимаешь, что скрыт объём работы при его построении...
+ фактор развиваемости: если что-то понадобится менять, усложнится задача, то ЦД гораздо проще развивать...
Можно, конечно, класть начальный ЦД в комментарий (в фолд), а писать преобразованный вариант.

Исходный ЦД-код очевидным образом преобразуется в:

Не знаю правильно ли ';' расставлены , но это не беда

Ну да, это получается, по сути, оптимизированная запись ЦД (упаковка двух циклов в один с "щёлкающими" ветками остаётся).