Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

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

Добрый день!
Помогите, пожалуйста, разобраться с алгоритмом Фибоначчиева поиска в упорядоченном массиве.
Читала Кнута.
Что я понимаю: Данный алгоритм ищет заданный ключ по элементам с индексами, равными числам Фибоначчи. На каждом шаге мы получаем интервал, в котором и может находится искомый ключ. После каждого сравнения мы отступаем от предыдущего значения (с которым сравнивали) на число Фибоначчи. И делаем это до тех пор, пока ключ не будет найден.
А теперь вопросы: У Кнута написано "Для удобства описания предполагается, что 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 вне форума Ответить с цитированием
Старый 14.04.2018, 23:49   #2
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Цитата:
Сообщение от 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 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Схема Кнута хранения разреженных матриц - в 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 18:27