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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #75 : Июль 26, 2012, 05:59:17 pm »
Так сопоставьте сначала, напишите цикл, нумерующий эти номера.

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

5409135678
5409135678
5406995567
5406995567
5406995567
5406995567
5406995567
5406995579
5406995579
5406995579

(это фрагмент экспорта, говорящий о том, что один человек сдал 4 экзамена, другой - 5, третий - 3).

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #76 : Июль 26, 2012, 06:04:34 pm »
Вообще, отношение к ЦД такое же, какое долгое время была у русскоязычных программёров к SWITCH-методу Шалыто. Сколько Абрамыча по форумам поливали, что "ничего там нет, это нахрен не нужно, это банально, это тупо, мы и так код пишем прекрасно без всяких автоматов" и проч.
Хотя совершенно очевидно, что это метод, который позволяет во многих ситуациях регуляризовать решение задачи. Как можно запрограммировать состояние объекта и его изменение через раздельные переменные (булевы признаки и проч.) - и всегда будут и случаи, и сторонники, когда это будет, вроде, нагляднее. С другой стороны, проводились сравнения для сложных задач, что программист, нахреначивший кучу логических признаков и их изменения в разных местах, допускал много ошибок и долго отлаживался, а программист, вводящий одну переменную состояния и анализировавший регулярным образом все случаи, успешно решал задачу.

Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #77 : Июль 26, 2012, 07:06:36 pm »
Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.
В арсенале нужно иметь действительно самые разные штуки. И ЦД и goto и рекурсию и много иных разных. Достаточно глупо превозносить какую-то одну методику над другими.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #78 : Июль 26, 2012, 07:08:18 pm »
Кстати, вот есть еще несправедливо забытый всеми цикл-паук, который по сути является дальнейшим развитием ЦД (там больше контроля).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #79 : Июль 26, 2012, 08:31:39 pm »
Вообще, отношение к ЦД такое же, какое долгое время была у русскоязычных программёров к SWITCH-методу Шалыто. Сколько Абрамыча по форумам поливали, что "ничего там нет, это нахрен не нужно, это банально, это тупо, мы и так код пишем прекрасно без всяких автоматов" и проч.
Весьма своеобразные аналогии...

Хотя совершенно очевидно, что это метод, который позволяет во многих ситуациях регуляризовать решение задачи. Как можно запрограммировать состояние объекта и его изменение через раздельные переменные (булевы признаки и проч.) - и всегда будут и случаи, и сторонники, когда это будет, вроде, нагляднее. С другой стороны, проводились сравнения для сложных задач, что программист, нахреначивший кучу логических признаков и их изменения в разных местах, допускал много ошибок и долго отлаживался, а программист, вводящий одну переменную состояния и анализировавший регулярным образом все случаи, успешно решал задачу.
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?.. Говорить о состояниях будем после... тема вполне интересная, и совсем не такая однозначная, как Вы описываете... Для примера состояние узла зависит от состояния деталей... Сколько переменных вводить будем?..

Так и ЦД позволяет по-другому подойти к построению алгоритма, вытащив на один уровень то, что расслоено обычно по нескольким. Иметь в арсенале такую штуку очень полезно.
А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #80 : Июль 26, 2012, 10:23:06 pm »
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?..
Строить без цикла Дейкстры умеем, резонно желание попробовать и оценить с ЦД. Горячие крики "это не читабельно" я пока услышал только от деятелей (типа Тышова на нашем форуме), для которых понятия предусловия, инварианта пустой звук, а программа - просто последовательность действий, которую надо "гонять в уме", а не анализировать логически. Другие отзываются более сдержанно, на уровне "ну и что мы выигрываем". Если мы имеем сравнимый по результату, но другой метод решения, то вполне оправдано и дальше его пробовать. Просто потому, что он другой и может скрывать в себе интересные выгоды.

А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...
Принцип диалектики - отрицание отрицания. Я тоже за отрубание. Именно поэтому считаю для себя неопасным попробовать и обратное, в нужной и полезной форме. Что непозволено тому, кто не умеет структурировать, то позволено тому, кто умеет.
Логический аппарат, например (в том числе автоматический - типа систем Model-Cheking) ориентирован на рассмотрение регуляризованных конструкций, а не "расслоенных" в соответствии с исходной семантикой задачи. Т.е. могут быть какие-то интересные выгоды.
Очевидно, что понять, какой именно вычислительный процесс порождается ЦД может быть проще, чем понять, какой процесс порождается конструкцией вложенности 4-5.

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #81 : Июль 26, 2012, 11:05:13 pm »
Так сопоставьте сначала, напишите цикл, нумерующий эти номера.

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

5409135678
5409135678
5406995567
5406995567
5406995567
5406995567
5406995567
5406995579
5406995579
5406995579

(это фрагмент экспорта, говорящий о том, что один человек сдал 4 экзамена, другой - 5, третий - 3).
Не тупите  -  минимум (1 цикл).

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #82 : Июль 26, 2012, 11:47:06 pm »
Если вас интересует конкретика,то посмотрите решение Alexus'a -мое будет практически таким же (единственное- вместо внутреннего
цикла я в таких случаях использую условный оператор - на мой взгляд, гораздо легче воспринимается).

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #83 : Июль 27, 2012, 01:59:10 am »
таки приведу его в терминах Alexus'а
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
        if cur_pass <> pass[i] then begin
           inc(stat[k]);   
           k := 0;
        end;
                inc(k);   
        end;
  inc(stat[k]); 

DIzer

  • Гость
Re: ещё про цикл дейкстры
« Ответ #84 : Июль 27, 2012, 02:22:57 am »
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
     if cur_pass <> pass[i] then begin
        inc(stat[k]);   
        k := 0; cur_pass := pass[i];
     end;
     inc(k);   
     end;
  inc(stat[k]);

 
« Последнее редактирование: Июль 27, 2012, 02:24:59 am от DIzer »

alexus

  • Гость
Re: ещё про цикл дейкстры
« Ответ #85 : Июль 27, 2012, 06:27:27 am »
Примеров можно приводить много и за то, и за это... Но вот здесь был вполне конкретный пример... Сравнить решения (с циклом Дейкстры и без него) - трудно?..
Строить без цикла Дейкстры умеем, резонно желание попробовать и оценить с ЦД. Горячие крики "это не читабельно" я пока услышал только от деятелей (типа Тышова на нашем форуме), для которых понятия предусловия, инварианта пустой звук, а программа - просто последовательность действий, которую надо "гонять в уме", а не анализировать логически. Другие отзываются более сдержанно, на уровне "ну и что мы выигрываем". Если мы имеем сравнимый по результату, но другой метод решения, то вполне оправдано и дальше его пробовать. Просто потому, что он другой и может скрывать в себе интересные выгоды.
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE. Вводить конструкцию подобную циклу Дейкстры - явно избыточно и опасно для начинающих (см. про сваливание логик различных уровней в одну кучу). Применительно к Дейкстре... столько бороться с GoTo, чтобы вернуться к тому же "спагетти"... с другой стороны... неразумно.

Цитата: alexus
А вот за такое "вытаскивание" руки надо отрубать... по самые плечи... но постепенно, по сантиметрику... в месяц... чтоб больше неповадно было...
Принцип диалектики - отрицание отрицания. Я тоже за отрубание. Именно поэтому считаю для себя неопасным попробовать и обратное, в нужной и полезной форме.
Что здесь "нужного", а тем более "полезного"?.. Это бесполезно и даже вредно, о чём свидетельствует Ваш же пример...

Что непозволено тому, кто не умеет структурировать, то позволено тому, кто умеет.
... или думает, что умеет... Кто проведёт грань между умеющими и не умеющими?.. Тестирование (ЕГЭ в миниатюре)?..

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

albobin

  • Full Member
  • ***
  • Сообщений: 198
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #86 : Июль 27, 2012, 07:54:31 am »
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE.
  И даже без EXIT или специальной переменной для катапультирования ? :)

albobin

  • Full Member
  • ***
  • Сообщений: 198
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #87 : Июль 27, 2012, 08:07:41 am »
Маркетолог бы тут сразу вкурил, что дело в названии и предложил бы сменить на "Цикл Лао-цзы"  :)

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #88 : Июль 27, 2012, 10:44:14 am »
assert(cntItems>0);
 cur_pass := pass[1]; k := 1;
 for i:=2 to cntItems do begin
        if cur_pass <> pass then begin
           inc(stat[k]);   
           k := 0;
        end;
                inc(k);   
        end;
  inc(stat[k]); 

Это уже не первые ваши "2 строчки".
Тогда уж вариант вот этот:
http://forum.oberoncore.ru/viewtopic.php?p=73513#p73513
Заметьте, что albobin получил его чисто преобразованием (выносом "за скобки") исходного ЦД. Что ещё раз подчёркивает его фундаментальность.

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

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Re: ещё про цикл дейкстры
« Ответ #89 : Июль 27, 2012, 10:50:48 am »
Цикл Дейкстры - частный случай, который легко восполняется простыми IF ... THEN ... ELSE. Вводить конструкцию подобную циклу Дейкстры - явно избыточно и опасно для начинающих (см. про сваливание логик различных уровней в одну кучу).

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