OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 15:23

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




Начать новую тему Ответить на тему  [ Сообщений: 122 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
Автор Сообщение
СообщениеДобавлено: Суббота, 02 Май, 2009 20:55 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Валерий Лаптев писал(а):
Ну, такой простой вариант, естественно, понятен. Но как-то Дейкстры тут не видать - обычный программистский цикл.
Ваш пример тривиально выражается через обычный цикл, цикла Дейкстры тут нет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 02 Май, 2009 21:16 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Valery Solovey писал(а):
Я не считаю, что Илья правильно использует этот цикл. Зачем оно надо, если тело выполняется только один раз? Какой же это цикл?

Подождите, в смысле - только один раз? Цикл повторяет попеременно то одну, то другую ветку.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 02 Май, 2009 21:20 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Сергей Губанов писал(а):
Валерий Лаптев писал(а):
Ну, такой простой вариант, естественно, понятен. Но как-то Дейкстры тут не видать - обычный программистский цикл.
Ваш пример тривиально выражается через обычный цикл, цикла Дейкстры тут нет.


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

Сергей, про Ваш вариант "с обычным циклом" я выше сказал, что лично меня в нём смущает: конструкция IF внутри него играет роль только на последнем витке. Т.е. она не используется в процессе цикла, а просто "подсекает" его окончание, как особый случай. В варианте же с ЦД такого особого случая не возникает, всё гладко.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 02 Май, 2009 21:30 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Валерий Лаптев писал(а):
Между прочим, в процессе отладки в цикле выяснился еще один нюанс.
Код:
while (true)
{       RM = mem[RA];            // выбрать слово
       RA = (RA + 1) % N;         // изменение адреса - по модулю 1024
      RC = RM.cmd.first;         // выбрать команду first
      run();                         // выполнить команду
      [b]if (Jump) continue;   // если переход, то не выполнять вторую команду [/b]
      if (Error || stop) break;   // если команда stop или ошибка
      RC = RM.cmd.second;         // выбрать команду second
      run();                  // выполнить команду
      if (Error || stop) break;   // если команда stop или ошибка
}

Как это учесть в цикле Дейкстры, который Илья Ермаков написал?


Может, смену позиции команды зашить в тот же читающий интерфейс? И тогда:

Код:
GetCommand(cmd); (* ASSERT(cmd # empty) *)
WHILE (cmd # empty) & (cmd # stop) & (cmd # jump) DO
  Execute(cmd, error); cmd := empty
ELSIF (cmd # empty) & (cmd = jump) DO
  SetCmdPos(newPos); GetCommand(cmd)
ELSIF (cmd = empty) & (error = no_error) DO
  GetCommand(cmd)
END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 03 Май, 2009 06:50 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Вот решение:
Код:
first = true;
while (НЕ stop И НЕ Error) do
  if first then
    RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;      // изменение адреса - по модулю 1024
    RC = RM.cmd.first;      // выбрать команду first
  else
    RC = RM.cmd.second;      // выбрать команду second
  endif;
  run();            // выполнить команду
  first = НЕ first ИЛИ ЭтоJump(RC);
end;

Цикл дейкстры (охраны в заголовке) приведет к дублированию кода:
Код:
first = true;
while НЕ stop И НЕ Error И first do
    RM = mem[RA];         // выбрать слово
    RA = (RA + 1) % N;      // изменение адреса - по модулю 1024
    RC = RM.cmd.first;      // выбрать команду first
    run();            // выполнить команду
    first = false ИЛИ ЭтоJump(RC);
elseif НЕ stop И НЕ Error И НЕ first do
    RC = RM.cmd.second;      // выбрать команду second
    run();            // выполнить команду
    first = true;
end;

Но главное в цикле – всё-таки инвариант, о котором здесь никто не вспоминает.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 03 Май, 2009 13:20 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Илья Ермаков писал(а):
Сергей, про Ваш вариант "с обычным циклом" я выше сказал, что лично меня в нём смущает
Представьте что составная инструкция состоит не из двух частей, а, например, из четырёх:
Код:
REPEAT
  ВыбратьСоставнуюИнструкцию;
  ЗагрузитьПервуюЧасть;
  Выполнить;
  IF надо_выполнять_вторую_часть THEN
    ЗагрузитьВторуюЧасть;
    Выполнить;
    IF надо_выполнять_третью_часть THEN
      ЗагрузитьТретьюЧасть;
      Выполнить;
      IF надо_выполнять_четвёртую_часть THEN
        ЗагрузитьЧетвёртуюЧасть;
        Выполнить
      END
    END
  END
UNTIL останов OR ошибка;

Условия стоящие под IF-ами могут быть самыми разнообразными, в том числе не иметь отношения к условию остановки цикла.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 03 Май, 2009 18:56 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Сергей Губанов писал(а):
Условия стоящие под IF-ами могут быть самыми разнообразными, в том числе не иметь отношения к условию остановки цикла.

Да, вот тут-то и существенная разница.
Если IF-ы не имеют отношения к условию остановки, то это - цикл с фильтрацией по какому-то условию внутри.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 03 Май, 2009 22:50 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
> ...А если IF дублирует...

По Вашему получается, что малая деформация условий заключенных под IF-ами приводит к изменению топологии...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 11:54 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Илья Ермаков писал(а):
Valery Solovey писал(а):
Я не считаю, что Илья правильно использует этот цикл. Зачем оно надо, если тело выполняется только один раз? Какой же это цикл?

Подождите, в смысле - только один раз? Цикл повторяет попеременно то одну, то другую ветку.
Смысл в том, что цикл нужен для повторяющихся действий. А у Вас ветка-цикл выполняется один раз и переходит к выполнению другой ветки-цикла, которая тоже выполняется один раз, снова переход к другой ветке. И так всё время!

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 13:10 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Видимо понимаете не правильно.
Попробуйте себе представить.
Вы пишите программу и выполнение дальнейшего куска должно произойти только по достижении определённого условия. В таком случае мы напишем:
Код:
xxx:
yyy: IF <условие не достигнуто> THEN GOTO xxx

Между xxx и yyy происходят какие то действия, в зависимости от состояния некоторой переменной
Код:
xxx: IF <есть ещё команда> THEN GOTO ссс
aaa: <выбрать следующую пару команд>
bbb: IF <команда КОНЕЦ> THEN yyy
ccc: <исполнить команду>
ddd: <выбрать следующую команду из пары>
yyy IF <условие не достигнуто> THEN GOTO xxx

Таким образом мы будем повторять некоторую последовательность действий, пока не встретим команду <КОНЕЦ>.
Как это ещё назвать, кроме как цикл?

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

Если бы мы точно знали сколько каких действий необходимо для достижения заданного условия, мы конечно же могли бы обойтись без цикла, но мы этого не знаем.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 13:35 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Madzi писал(а):
Попробуйте себе представить...
Вы описываете работу обычного цикла. И это я нормально понимаю. Вопросы у меня по циклу Дейкстры.
Madzi писал(а):
Поэтому логично, описать работу имеющегося КА с помощью цикла Дейкстры.
Я не вижу в Ваших рассуждениях предпосылки для такого заключения. Недостаточно информации. Это понятно, что цикл будет работать как КА, но зачем оно надо? Если пойти дальше, то таким способом можно и от IF-ов всюду избавиться: везде ставить WHILE.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 13:39 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Valery Solovey писал(а):
Если пойти дальше, то таким способом можно и от IF-ов всюду избавиться: везде ставить WHILE.
Точно! Именно это и было зачем-то сделано: вместо IF написали ещё одну ветку "WHILE" в которой изменили значение дополнительно введённого флага, чтобы данная ветка "WHILE" выполнилась всего один раз. Зачем такой огород?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 14:01 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Valery Solovey писал(а):
Это понятно, что цикл будет работать как КА, но зачем оно надо? Если пойти дальше, то таким способом можно и от IF-ов всюду избавиться: везде ставить WHILE.

1. Работу микросхем логичнее моделировать КА (коими они по сути и являются).
2. Формальный аппарат для КА развит не в пример лучше.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 14:48 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Сергей Губанов писал(а):
Точно! Именно это и было зачем-то сделано: вместо IF написали ещё одну ветку "WHILE" в которой изменили значение дополнительно введённого флага, чтобы данная ветка "WHILE" выполнилась всего один раз. Зачем такой огород?

Чтобы не было разночтений, уточните, пж, какой код имеется в виду.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 16:13 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Код Ильи Ермакова с циклом Дейкстры.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 17:01 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Прошу прощения за назойливость. Илья Ермаков приводил два примера кода:
Илья Ермаков писал(а):
Код:
GetCommand(cmd); (* ASSERT(cmd # empty) *)
WHILE (cmd # empty) & (cmd # stop) DO
  Execute(cmd, error); cmd := empty
ELSIF (cmd = empty) & (error = no_error) DO
  GetCommand(cmd)
END

Илья Ермаков писал(а):
Код:
GetCommand(cmd); (* ASSERT(cmd # empty) *)
WHILE (cmd # empty) & (cmd # stop) & (cmd # jump) DO
  Execute(cmd, error); cmd := empty
ELSIF (cmd # empty) & (cmd = jump) DO
  SetCmdPos(newPos); GetCommand(cmd)
ELSIF (cmd = empty) & (error = no_error) DO
  GetCommand(cmd)
END
Просьба пояснить, где находится "ветка WHILE, которая выполняется всего один раз"
Сергей Губанов писал(а):
...вместо IF написали ещё одну ветку "WHILE" в которой изменили значение дополнительно введённого флага, чтобы данная ветка "WHILE" выполнилась всего один раз.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 19:30 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Правильнее будет сказать "ветка WHILE, цикл которой выполняется всего один раз". Так, наверное, понятнее.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 19:51 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Valery Solovey писал(а):
Правильнее будет сказать "ветка WHILE, цикл которой выполняется всего один раз". Так, наверное, понятнее.
Где в коде такая ветка-то? Ткните пальцем, наконец.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 20:41 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Каждая строка за исключением END - ветка

Код:
WHILE (cmd # empty) & (cmd # stop) DO Execute(cmd, error); cmd := empty
ELSIF (cmd = empty) & (error = no_error) DO GetCommand(cmd)
END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 04 Май, 2009 20:54 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Там ветки выполняются попеременно.


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

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


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

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


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

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