OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 25 Май, 2018 17:37

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Четверг, 19 Июль, 2012 15:43 
Модератор
Аватара пользователя

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

Привожу свой вариант:
Код:
stat[i] имеет смысл количества человек, сдававших i экзаменов
обнуление массива stat
i := 0; j := 1; (* Инвариант: [i, j) - интервал из одинаковых номеров паспортов *)
WHILE (j < len) & (pass[j] = pass[i]) DO
   INC(j)
ELSIF (j < len) & (pass[j] # pass[i]) DO
   INC(stat[j - i]); i := j; j := i + 1
END;
IF i < len THEN (* чтобы алгоритм был применим к пустой последовательности *)
   INC(stat[j - i])
END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 19 Июль, 2012 17:22 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 525
Откуда: Москва
Программа правильная (не тестировал :) ), цикл Дейкстры оправдан.
Инвариант, как всегда, неправильный. Точнее, сильно неполный.
Кроме того, я бы для наглядности ввел термин "площадка".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 19 Июль, 2012 21:11 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 667
Откуда: Псков
Видимо описка
не INC(i), а INC(j) надо


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 19 Июль, 2012 23:47 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Peter Almazov писал(а):
Инвариант, как всегда, неправильный. Точнее, сильно неполный.


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 19 Июль, 2012 23:48 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
albobin писал(а):
Видимо описка
не INC(i), а INC(j) надо

Да, спасибо.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 02:30 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Да, я вот не сразу понял, что для ББ это именно алгоритм... с записью ЦД на О-07... где-то с полминуты пытался въехать, как IF должен сочетаться с ELSIF на КП... :)

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 03:56 

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 557
Ну вот, всегда так с ЦД.

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

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 05:36 

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 557
Видимо описка
не INC(stat[j - i] ,
а INC(stat[j - i]) надо


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 06:33 

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 06:56 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 525
Откуда: Москва
Илья Ермаков писал(а):
Ну, фактически, я назвал ровно такой инвариант, который объясняет смысл переменных... А не инвариант для полной формализации цикла.
Идиотское убеждение (от Info21), что инвариант нужен некоему дяде, причем только в редких, особо торжественных случаях, и только после того, как цикл написан, оставляю без комментариев.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:00 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 667
Откуда: Псков
Эпитеты случаются быть и самоприменимыми :lol:


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:14 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Peter Almazov писал(а):
не ведет к построению правильного цикла.


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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:31 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Peter Almazov писал(а):
Идиотское убеждение (от Info21), что инвариант нужен некоему дяде, причем только в редких, особо торжественных случаях, и только после того, как цикл написан, оставляю без комментариев.


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:35 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
albobin писал(а):
Это по идее надо обеспечивать в охватывающем коде (не вызывать или не выполнять, если не по чему считать). Тогда и последний INC stat будет безусловный.


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:37 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Peter Almazov писал(а):
Предположим, в последовательности с самого начала идут номера паспортов 1,1,1,1,1. В некоем цикле i=2, j=4.
Между [i и j) одинаковые номера паспортов? - Одинаковые.
Устроит ли нас такая трактовка? - Нет, не устоит.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 09:43 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Цитата:
и школярская привычка в программировании использовать одно буквенные идентификаторы, при этом визуально мало различимые ( i , j ), а не слова наполненные смыслом из предметной области,

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

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 10:13 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Вчера минут через 40 трудов и нескольких выходов покурить программист закончил свой вариант. Получилось вот что:

Код:
i := 0;
WHILE i < total DO
  count := 0;
  current := m[i];
  WHILE (i < total) & (current = m[i]) DO
    INC(i);
    INC(count)
  END
  INC(stat[count])
END


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 10:18 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Ну и "на закуску", для сравнения - разворачиваю ЦД в два вложенных цикла:

Код:
i := 0;
WHILE i < len DO
   j := i + 1;
   WHILE (j < len) & (pass[j] = pass[i]) DO
     INC(j)
   END;
   INC(stat[j-i])
   i := j
END


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 12:39 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 667
Откуда: Псков
Исходный ЦД-код очевидным образом преобразуется в:
Код:
i := 0; j := 1;
WHILE (j < len)  DO
   IF  (pass[j] # pass[i])  THEN   INC(stat[j - i]); i := j  END;
   INC(j)
END;
IF i < len THEN  INC(stat[j - i]) END;

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 12:52 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8945
Откуда: Россия, Орёл
Ну да, это получается, по сути, оптимизированная запись ЦД (упаковка двух циклов в один с "щёлкающими" ветками остаётся).


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2018, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB