Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.
Внимание! Некоторое время письма не доходят до аккаунтов MAIL RU GROUP, не доходят на все почтовые ящики mail.ru, inbox.ru, bk.ru. Пишите им жалобы, чтобы быстрее восстановили получение писем, регистрируйтесь через яндекс почту и gmail, туда письма с активизацией доходят.

Вернуться   Форум программистов > Технологии > Общие вопросы по программированию, компьютерным наукам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы
Старый 13.04.2018, 13:09   #1
Archangel_Gavr
Новичок
 
Регистрация: 13.04.2018
Сообщений: 1
Репутация: 10
По умолчанию Фибоначчиев поиск у Кнута

Добрый день!
Помогите, пожалуйста, разобраться с алгоритмом Фибоначчиева поиска в упорядоченном массиве.
Читала Кнута.
Что я понимаю: Данный алгоритм ищет заданный ключ по элементам с индексами, равными числам Фибоначчи. На каждом шаге мы получаем интервал, в котором и может находится искомый ключ. После каждого сравнения мы отступаем от предыдущего значения (с которым сравнивали) на число Фибоначчи. И делаем это до тех пор, пока ключ не будет найден.
А теперь вопросы: У Кнута написано "Для удобства описания предполагается, что N+1 это F(k+1) число Фибоначчи", а для общего случая находится M: M+N+1 = F(k+1). Что это вообще за M и зачем нам необходимо его находить? Почему берется именно F(k+1)?
Далее. Переменная i - это текущее положение. Почему его мы берем именно F(k)-M?
Ну с q и p вроде все понятно.
Так же понятно, что это все можно объяснить с помощью соответствующего дерева Фибоначчи порядка k, но как это сделать я не понимаю. Единственное, что я заметила - значение наибольшего узла в данном дереве порядка k равно F(k+1)-1 (хотя верно ли и это?).
Archangel_Gavr вне форума   Ответить с цитированием
Старый 15.04.2018, 00:49   #2
Dekay
Форумчанин
 
Регистрация: 21.06.2016
Сообщений: 51
Репутация: 99
По умолчанию

Цитата:
Сообщение от Archangel_Gavr Посмотреть сообщение
хотя верно ли и это?
Да.
А объяснение этому - N+1 = F(k+1)
Чуть более понятно.
Массив поиска [0..N]
Рассмотрим правого сына корня (F(k)) его значение будет равно F(k)+F(k-2), а его правого сына будет F(k)+F(k-2)+F(k-4). Значение самого правого листа будет F(k)+F(k-2)+F(k-4)+... = F(k+1)-1, т.е. F(k+1) = F(k)+F(k-2)+F(k-4)+..+F(k mod 2)-1
Доказывать это и не надо, ибо F(k+1) = F(k)+F(k-1)
F(k-1) = F(k-2)+F(k-4)+F(k-6)+..+1-1
Подставляем. Получаем то, что хотели

Суть в том, каждый внешний узел будет отличаться от брата на 1. Всего таких узлов F(k+1). Значит по такому дереву поиска мы сможем найти любой элемент.

Цитата:
Сообщение от Archangel_Gavr Посмотреть сообщение
Что это вообще за M и зачем нам необходимо его находить?
Ради красоты.
Вы можете записать в конец массива тьму значений inf. Или. Поставить еще тьму ифов. Только вот накой? Если можно не пачкать алгоритм, а чутка пошаманить.

Если сложно - забейте. Напишите другой код. Более понятный для вас. С проверками или фиктивными элементами.

И еще. Чтобы ответить Вам - мне пришлось скачать Кнута. Мне пришлось пролистать тьму страниц, чтобы добраться до Фиб поиска, а потом еще тьму, чтобы найти упражнение и ответы к нему.
Помилуйте. Мне не нравится искать. Это скучно. Так что по возможности - шлепайте скрины/фотки и прочее.
Dekay вне форума   Ответить с цитированием
Ответ

Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Схема Кнута хранения разреженных матриц - в Delphi Deathcube Фриланс 1 24.04.2013 19:37
Алгоритм Кнута — Морриса — Пратта. Ошибка!! Паскаль WizzzIDizzzI Помощь студентам 1 25.05.2011 16:46
Кто читал Дональда Кнута? vedro-compota Свободное общение 24 08.06.2010 13:43
Алгоритм Кнута-Морриса-Пратта Crazy_Gamer Помощь студентам 1 17.12.2009 19:27


14:08.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru