Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

Восстановить пароль
Повторная активизация 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


20:00.


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

RusProfile.ru


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