|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
13.04.2018, 12:09 | #1 |
Новичок
Джуниор
Регистрация: 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 (хотя верно ли и это?). |
14.04.2018, 23:49 | #2 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Да.
А объяснение этому - 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). Значит по такому дереву поиска мы сможем найти любой элемент. Ради красоты. Вы можете записать в конец массива тьму значений inf. Или. Поставить еще тьму ифов. Только вот накой? Если можно не пачкать алгоритм, а чутка пошаманить. Если сложно - забейте. Напишите другой код. Более понятный для вас. С проверками или фиктивными элементами. И еще. Чтобы ответить Вам - мне пришлось скачать Кнута. Мне пришлось пролистать тьму страниц, чтобы добраться до Фиб поиска, а потом еще тьму, чтобы найти упражнение и ответы к нему. Помилуйте. Мне не нравится искать. Это скучно. Так что по возможности - шлепайте скрины/фотки и прочее. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Схема Кнута хранения разреженных матриц - в 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 |