OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2024 09:38

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




Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Среда, 21 Апрель, 2010 15:05 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 20:31
Сообщения: 9
Откуда: Ульяновск
Интересная статья на Хабре: http://habrahabr.ru/blogs/algorithm/91605/#habracut
Вернее, интересна не сама статья, а комментарии к ней.

Первая реакция --- написать двоичный поиск не сложно. Было сразу предложено несколько вариантов реализации. Но, что интересно, среди них нет ни одного 100% верного решения!

После небольшой дискуссии сошлись на том, что программисту знать про двоичный поиск не обязательно :?


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Если кто-нибудь зарегистрирован на Хабре, киньте туда эту ссылку viewtopic.php?p=46182#p46182
Удалено модератором


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

Зарегистрирован: Суббота, 15 Март, 2008 20:00
Сообщения: 297
Откуда: Київ, Україна
Интересно, вот написал, "распространенных ошибок" вроде нет.
Интересно, есть ли ошибки?

Код:
MODULE BinSearch; (** AUTHOR ""; PURPOSE ""; *)
IMPORT KernelLog;
PROCEDURE Search(x:LONGINT; a:ARRAY[*] OF LONGINT):LONGINT;
VAR
 n1,n2,i:LONGINT;
BEGIN
   n1:=0;
   n2:=LEN(a)-1;
   IF n2<0 THEN RETURN -1 END;
   i:=(n2-n1) DIV 2;
   WHILE (x#a[i])&(n1#n2) DO
      IF (x>a[i]) THEN
         IF (i#n1) THEN
            n1:=i;
         ELSE
            n1:=n2
         END;
      ELSE
         n2:=i;
      END;
      i:=(n2-n1) DIV 2+n1;
   END;
   IF (x=a[i]) THEN
      RETURN i;
   ELSE
      RETURN -1;
   END;
END Search;

PROCEDURE Test*;
BEGIN
KernelLog.String("Res= ");KernelLog.Int( Search(0,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(1,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(2,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(3,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(4,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(5,[0,1,2,3,4]), 0); KernelLog.Ln;
KernelLog.String("Res= ");KernelLog.Int( Search(2,[1,2]), 0); KernelLog.Ln;
END Test;

END BinSearch.Test~


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Коллеги, вы бы лучше выучили второй вариант двоичного поиска из Алгоритмов... Вирта. Он и проще, и эффективней. Там ищется не a[i]=x, а такое i, что для всех j<i a[j]<x, и для всех j>=i a[j]>=x. Начало i=0, j=LEN. Охрана цикла i<j. В конце одна доп. проверка, имеет ли место a[i]=x. Тело цикла профессионалы заполнют сами, надеюсь. А остальные прочтут :)


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

Зарегистрирован: Суббота, 15 Март, 2008 20:00
Сообщения: 297
Откуда: Київ, Україна
Info21 писал(а):
Коллеги, вы бы лучше выучили второй вариант двоичного поиска из Алгоритмов... Вирта.

Выучить всегда можно, а тут как кроссворд решить - просто интересно :wink:
PS: а за совет спасибо!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 21 Апрель, 2010 17:29 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Интересно, а в той версии 1962 года, которую Кнут признал корректной, как вычислялся индекс среднего элемента? :roll:


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
bohdant писал(а):
PS: а за совет спасибо!
На самом деле тут штучка гораздо интересней любого кроссворда: подмена конечного условия более слабым.
Обычно с другой стороны мысль идет, причем инерция очень сильна.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 05:36 

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 10:16 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 10:21 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
И по поводу структурного подобия линейному поиску:
там имеет место быть частично упорядоченная по включению система интервалов, потенциально содержащих искомый элемент.
В этой системе единственная "точная нижняя грань".
Поэтому если мы ищем ее, то любой путь по стрелочкам будет корректным.
Чем и обуславливается "фундаментальное структурное подобие".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 16:07 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Это опять анализ. Вы про синтез напишите.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 16:31 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 16:58 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Info21 писал(а):
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.
1. Какая конкретно программа?
2. И как же она была выстроена? Самое главное, кем выстроена?
3. bohdant применил не логику, а гадание на кофейной гуще.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 17:24 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Peter Almazov писал(а):
Info21 писал(а):
Peter Almazov писал(а):
Вы про синтез напишите.
Так программа в книжке была выстроена -- как? :)
Вон и bohdan ту же логику применил.
1. Какая конкретно программа?
Мы вроде с самого начала обсуждаем двоичный поиск.
В простом ЛП ищем, перебирая подряд.
Здесь ищем, беря случайный элемент в сужающихся интервалах, с гарантией сходящихся к цели.
Как только это замечено, сразу пишется цикл.
Следуя шаблону линейного поиска :)
Чё тут синтезировать, когда шаблон уже есть :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 18:12 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Info21 писал(а):
Мы вроде с самого начала обсуждаем двоичный поиск.
В простом ЛП ищем, перебирая подряд.
Здесь ищем, беря случайный элемент в сужающихся интервалах, с гарантией сходящихся к цели.
Как только это замечено, сразу пишется цикл.
Следуя шаблону линейного поиска :)
Чё тут синтезировать, когда шаблон уже есть :)
В общем, все понятно.
Спасибо за ответы.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 18:18 
Аватара пользователя

Зарегистрирован: Суббота, 15 Март, 2008 20:00
Сообщения: 297
Откуда: Київ, Україна
Peter Almazov писал(а):
3. bohdant применил не логику, а гадание на кофейной гуще.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 22 Апрель, 2010 18:45 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Да ладно, не обижайтесь :)
Я вот подредактировал свой пост про двоичный поиск, и послал на habrahabr.ru. Модераторы одобрили публикацию.
Как же все-таки правильно написать двоичный поиск?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 24 Апрель, 2010 12:08 

Зарегистрирован: Суббота, 24 Апрель, 2010 11:48
Сообщения: 2
Написать на бумаге возможно и 10%, но думается при 99% вероятности ошибки.

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

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

Сам факт, достаточно трудного обнаружения ошибки при "новых условиях", говорит о том, что нужно внимательно относиться к тестам.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 24 Апрель, 2010 17:55 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
delphiec писал(а):
Много времени занимает отладка.
Отладка? В этом алгоритме? No comment.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 24 Апрель, 2010 20:34 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
delphiec писал(а):
Написать на бумаге возможно и 10%, но думается при 99% вероятности ошибки.
Много времени занимает отладка.

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


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

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


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

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


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

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