Автор Тема: ещё про цикл дейкстры  (Прочитано 28147 раз)

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #30 : Июль 21, 2012, 08:10:15 am »
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.
Жуть какая то -вроде  классическая задача на применение сортировки подсчетом...- вместо того, что бы почитать нормальные книги (не Сиськина с Вертом) -очередные пляски вокруг идола (ЦД)...

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #31 : Июль 22, 2012, 04:46:56 pm »
Цитата: Илья Ермаков
При расчёте статистики по результатам ЕГЭ в регионе у нас в ОРЦОКО пришлось кое-что дописывать, т.к. федеральное ПО ужасное и не считает всё, что нужно.
Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена.
Программист сортирует экспортированные из системы результаты экзаменов в Excel по полю "номер паспорта" и дальше сохраняет в CSV одну только эту колонку. Т.е. имеется последовательность строк с номерами паспортов, где каждый номер повторяется (рядом) столько раз, сколько человек сдавал экзаменов.
Программист сейчас ваяет на ББ процедурку, которая посчитает статистику.
Я тоже тут накидал алгоритм. Не напрягая мозги, получился сразу цикл Дейкстры. Тестировать не тестировал, написал на бумажке.
Правда, программист не хочет его брать, говорит, что не понимает  Колдует уже час над вложенными циклами, пытаясь, к тому же, это сделать прямо над TextMappers.Scanner.
(жирным шрифтом выделено мной).
В который раз одно и то же на оберонкоре... задачу ставить/понимать не хотим, но сразу предлагаем решение "не напрягая мозги" и получаем... цикл Дейкстры... с ошибками и без тестирования...
"Всё это было бы смешно, когда бы не было, так грустно"...
1. И не смущает, что нет постановки задачи, просто декларируется: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"... Кому это нужно?.. Для чего это нужно?.. Какая статистика вообще востребована?.. Ну, вот, Илье потребовалось "это", а кому-то "это" и ещё "вот это"... а кому-то... важен средний балл по математике... или биологии, или средний балл по всем предметам тех, кто сдавал математику и биологию.
2. И не смущает, что при такой постановке задачи "софт" получается "ужасным и не полным"... Он реально не может быть другим... потому что, придёт ещё один "илья" со своим видением и допишет ещё 20-40 строк с ужасным циклом Дейкстры, который в очередной раз никто не поймёт...
3. И не смущает, что писать этот самый цикл Дейкстры берутся... "не напрягая мозги"... А мозгам, вообще говоря, полезно, когда их напрягают... примерно также, как мышцам... Мышцы напрягают, когда работают физически, а мозг - когда умственно... Собственно, мозг - это некая "интеллектуальная мышца"... :) И вот если мозги напрячь, то... получим несколько простых, но полезных идей...
  • Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных). Применительно к данной задаче, надо отсортировать список (массив) ссылок на данные паспорта. Внешнее окружение переменчиво...
  • Не надо запутывать логику обработки данных, чем проще логические конструкции, тем проще в них разобраться, тем эффективнее код. Применительно к данному случаю, оптимальным будет вариант с вложенными циклами:
i := 0;
while (i < cntItems) do begin
        cur_pass := pass[i];
        k := 0;
        while (i < cntItems) and (cur_pass = pass[i]) do begin
                inc(k);     // k - количество сданных экзаменов учащимся с данным паспортом
                inc(i);
        end;
        inc(stat[k]);    // stat[k] массив, где хранятся количества сдавших k-ое количество экзаменов (размерность от 0 до Количество экзаменов, размеры элементов массива (положительное целое) должны вмещать количество сдававших)
end;

А что реально смущает, так это то... что они ещё и учат...

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #32 : Июль 22, 2012, 05:19:17 pm »
Не знаю чему они учат...но минимальными знаниями по алгоритмике преподаватель владеть (ИМХО) ОБЯЗАН...
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к
...
for i:=1 to Max do inc(res[exams[i]])

что  есть сортировка подсчетом в ЧИСТОМ виде....

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #33 : Июль 22, 2012, 07:35:58 pm »
Гхм. А почему нет? Алгоритм не укладывается в тривиальный цикл. Запутаем читателя еще больше с помощью ЦД?
Да я не против решения с процедурой. Как ты совершенно верно заметил, поборем нестандартность декомпозицией :) Но в арсенале полезно иметь и то, и то.
Всё больше убеждаюсь, что "вытаскивание" на один уровень всех условий, которые иначе были бы во вложенных IF-ах и циклах - очень полезный метод при построении алгоритма. Чисто структурная сложность алгоритма становится ниже - не думаем о последовательности проверок, циклов, о вложенности - а просто регулярно описываем все ситуации.

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #34 : Июль 22, 2012, 07:41:48 pm »


Мы не разрабатываем ПО ЕГЭ. Вообще, львиная доля работы сейчас в той организации, куда меня пригласили на должность зам. директора, - внедрение и организация использования в масштабах региона таких систем, как, например, автоматизированная система школ.
Претензии к "ущербности" ПО статистики - к Федеральному центру тестирования.
Остальные рассуждения "а зачем нужна цифра" хороши, когда эту цифру от вас не требует в режиме "надо уже вчера", например, аппарат губернатора. А официальное ПО её дать не может.

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #35 : Июль 22, 2012, 07:47:55 pm »
Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных).
Для задачи однократно посчитать и как можно быстрее самое правильное решение - это отсортировать CSV прямо в Excel... А программист занимается в период ЕГЭ вообще не программированием, а "любовью" с ЕГЭ-шной системой статистики.

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #36 : Июль 22, 2012, 07:52:00 pm »
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к

У нас нет "данных о количестве экзаменов".
У нас есть экспорт всех результатов всех участников по всем экзаменам. Т.е. определить количество экзаменов, сданных участником, можно, подсчитав, сколько строк в экспорте с его номером паспорта.
Так что Вы куда-то не в ту степь.

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #37 : Июль 22, 2012, 07:58:49 pm »
У alexus-а опять диагностируем манию величия.
Сам он, имея богатый опыт и сильные идеи, так никого им и не научил.. И, видимо, не научит. Гораздо приятнее ходить по форумам и весям и намекать всем про то, что он эти идеи имеет и что никто вокруг ничего не понимает.
Хотя залезает он на такой уровень абстракций, что все его рассуждения просто не получается воспринимать как "одновариантные". Т.е. легко представляется другая картина мира, такая же красивая, как и его. Работу же на уровне обобщения пониже он презирает и поливает г-ном, это все уже знают :)

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #38 : Июль 22, 2012, 08:02:07 pm »

Так что Вы куда-то не в ту степь.
Вту степь..я вообще не знаю в каком виде у вас данные и поэтому наложил условие на них - чтобы удовлетворить ему
достаточно добавить еще один цикл...-который  определяется ВАШИМИ данными..

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #39 : Июль 22, 2012, 08:19:02 pm »
Не надо полагаться на то, что данные из внешнего источника будут представлены в нужной последовательности или группировке, или отфильтрованы так, как требуется для данной задачи (не ленитесь преобразовывать... но не сами данные, а текущее представление о данных).
Для задачи однократно посчитать и как можно быстрее самое правильное решение - это отсортировать CSV прямо в Excel... А программист занимается в период ЕГЭ вообще не программированием, а "любовью" с ЕГЭ-шной системой статистики.
Кстати, да. Когда мне доводится обрабатывать массивы данных и строить по ним статистику, то частенько я не пишу специализированную прогу, и даже матлаб не задействую, а просто всю эту статистику считаю и визуализирую в excel'e. Подозреваю что и эту задачу в excel'e вполне можно решить.

А особо excel'e-продвинутые пишут прогу в оном excel'e, чтобы оно автоматом все считало, без ручных манипуляций.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #40 : Июль 22, 2012, 08:29:13 pm »
 ;) И..в каком месте здесь цикл Дейкстры?

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #41 : Июль 22, 2012, 09:06:15 pm »
;) И..в каком месте здесь цикл Дейкстры?
А фиг знает. В данной задаче использовать конструкции которые привносят тьюринг-полноту явно не оправдано (ибо черевато ошибками).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #42 : Июль 22, 2012, 09:23:33 pm »
Не знаю чему они учат...но минимальными знаниями по алгоритмике преподаватель владеть (ИМХО) ОБЯЗАН...
Что касается задачи....пусть данные о количестве экзаменов содержатся в массиве  exams[1..Max], пусть решение будет хранится
в массиве res[0..9]  инициализированном нулями  тогда алгоритм (Паскаль) сводится к
...
for i:=1 to Max do inc(res[exams[i]])

что  есть сортировка подсчетом в ЧИСТОМ виде....
Всё хорошо... только это какая-то другая задача... В исходной "постановке" было сказано: "Нужно посчитать количество выпускников, сдававших, соответственно, 1, 2, 3... экзамена"...

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #43 : Июль 22, 2012, 09:32:57 pm »


Мы не разрабатываем ПО ЕГЭ.
Это радует...

Вообще, львиная доля работы сейчас в той организации, куда меня пригласили на должность зам. директора, - внедрение и организация использования в масштабах региона таких систем, как, например, автоматизированная система школ.
Региону... мои сочувствия... При таком подходе к делу... не позавидуешь ему. (о подходе к делу сказано ниже)

Претензии к "ущербности" ПО статистики - к Федеральному центру тестирования.
Само собой...

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

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #44 : Июль 22, 2012, 09:45:31 pm »
У alexus-а опять диагностируем манию величия
Ну, кого что заботит... Правда забавно, когда у других диагностируют "манию величия", говоря от своего имени... во множественном числе...
Лучше бы сказали, Ваша Скромность, задачка правильно решена аль нет?.. Нужен ли пресловутый цикл Дейкстры... или без него решение проще и нагляднее? (Только мозги напрягите...)

Сам он, имея богатый опыт и сильные идеи, так никого им и не научил..
Это видимо опять от скромности... если Ермакова не научил, значит никого... ну-ну...

И, видимо, не научит.
А зачем?.. Кто хочет, тот научится... Не педагог я, Ваша Скромность.

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

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