OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 25 Август, 2019 06:45

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




Начать новую тему Ответить на тему  [ Сообщений: 148 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8
Автор Сообщение
СообщениеДобавлено: Суббота, 29 Июнь, 2019 03:35 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8170
Откуда: Троицк, Москва
Спасибо за комплимент Ваших замечаний. Прямо сейчас ответить не смогу.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 29 Июнь, 2019 06:28 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3061
Откуда: Астрахань
kemiisto писал(а):
Текст:
Цитата:
Страница 52, Строкa 31
L :=О; R := N;
Замечание: Не понимаю, почему тут R := N, а не R := N - 1.

На предыдущей странице в листинге ADruS18_Поиск стоит R := N-1;
Но и условие в цикле L <= R.
В коде R := m-1;

На странице 52 поставили R := N;
Но и условие поменяли L < R.
В коде тоже R := m;

Все согласованно изменено.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 29 Июнь, 2019 09:47 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8170
Откуда: Троицк, Москва
Спасибо за помощь ))


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 29 Июнь, 2019 12:43 

Зарегистрирован: Воскресенье, 03 Февраль, 2008 12:50
Сообщения: 245
Валерий Лаптев писал(а):
Все согласованно изменено.

Да, спасибо. С этим моментом разобрался. Суть в том, что в этом варианте поиска, как и написано в книге, "ищется не элемент a[m] = х, а граница, отделяющая все элементы, меньшие х, от всех прочих". Тогда для частного случая, когда элемента x в массиве нет, т.е. x превосходит все a[i], действительно необходимо проверить в цикле и последний элемент с индексом N - 1, поэтом R изначально должно быть N. В ином случае этот последний элемент проверен не будет и последующее утверждение, что в случае, "если R = N, то искомого значения в массиве нет" будет неверным.

В конечном итоге полностью вариант из учебника должен выглядит как-то так:
Код:
L := 0;  R := N;
WHILE  L < R  DO
  m := (L+R) DIV 2;
  IF a[m] < x THEN L := m+1 ELSE R := m END
END;

IF R = N THEN
  (* Если R = N, то искомого значения в массиве нет. *)
  (* элемент найден *)
ELSE
  (* В противном случае нужно учесть, что элемент a[R] еще не сравнивался. *)
  IF a[R] = х THEN
    (* элемент найден *)
  ELSE
    (* элемент не найден *)
  END
END


Так вот, глядя на такой код, мне в голове "лезет" немного другой вариант:
Код:
L := 0;  R := N - 1;
WHILE  L < R  DO
  m := (L+R) DIV 2;
  IF a[m] < x THEN L := m+1 ELSE R := m END
END;

IF a[R] = х THEN
  (* элемент найден *)
ELSE
  (* элемент не найден *)
END


Здесь a[R] сравнивается по окончании цикла в любом случае, так как частный случай с отсутствием искомого значение в массиве надо учесть. По сути проверка последнего элемента в этом частном случае перенесена из цикла в условный оператор. Сам условный оператор получается "проще" и R тут уже будет достаточно N - 1, но теряется ... эммм... концептуальная простота что-ли :D алгоритма, т.к. простое словесное описание действий, выполняемых в цикле, данное ранее ("ищется не элемент a[m] = х, а граница, отделяющая все элементы, меньшие х, от всех прочих") здесь уже не работает - в обсуждаемом частном случае до границы мы так и не дойдём. Кроме того, теряется и "фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R", на котором чуть раньше заостряет внимание автор.


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

Зарегистрирован: Воскресенье, 03 Февраль, 2008 12:50
Сообщения: 245
"Подумал". Проверку в варианте из учебника можно "упростить" до:
Код:
IF R < N & a[R] = x THEN
  (* элемент найден *)
ELSE
  (* элемент не найден *)
END


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 30 Июнь, 2019 20:42 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8170
Откуда: Троицк, Москва
kemiisto писал(а):
[
Так вот, глядя на такой код, мне в голове "лезет" немного другой вариант:
[code]L := 0; R := N - 1;
WHILE L < R DO
m := (L+R) DIV 2;
Проверьте случай, когда все элементы массива < x.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 04 Июль, 2019 16:40 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
kemiisto писал(а):
Страница 50, Строки 11-12
Текст:
Цитата:
До и после каждого шага цикла выполняется следующее условие:
(0 ≤ i < N) & (Ak: 0 ≤ k < i : ak # х)
Замечание: Если искомого элемента в массиве нет, то после заключительного шага цикла приведённое условие будет ложным, т.к. i = N. Не должна ли первая часть условия быть (0 ≤ i N)?


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


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

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 806
Откуда: Казань
Инвариант должен быть истинен и после выполнения цикла. А после выполнения цикла i будет равняться N, соответственно инвариант не будет истинен. Поэтому правильный инвариант должен быть:
(0 ≤ i ≤ N) & (Ak: 0 ≤ k < i : ak # х)


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

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


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

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


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

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