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

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

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 23.05.2010, 23:15   #1
Chica Bond
Пользователь
 
Регистрация: 15.03.2010
Сообщений: 31
По умолчанию Помогите реализовать алгоритм Фибоначчиева поиска

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

Последний раз редактировалось Вадим Мошев; 18.04.2015 в 20:38.
Chica Bond вне форума Ответить с цитированием
Старый 23.05.2010, 23:39   #2
profi
Участник клуба Подтвердите свой е-майл
 
Регистрация: 19.11.2007
Сообщений: 1,022
По умолчанию

Набери в поиске по форуму "фибоначи" и найдешь дофига тем с готовыми программами .
profi вне форума Ответить с цитированием
Старый 23.05.2010, 23:46   #3
Chica Bond
Пользователь
 
Регистрация: 15.03.2010
Сообщений: 31
По умолчанию

Цитата:
Сообщение от profi Посмотреть сообщение
Набери в поиске по форуму "фибоначи" и найдешь дофига тем с готовыми программами .
эм... единственное пока что что я нашла это просто алгоритм))) вот он:
1. Шаг 1. Задаются начальные границы отрезка a,b и число итераций n, рассчитывают начальные точки деления: x1 = a+(b-a)*F{n-2}/F{n}, x2 = a+(b-a)*F{n-1}/F{n} и значения в них целевой функции: y1=f(x1), y2=f(x2).
2. Шаг 2. n=n-1.
* Если y1>y2, то a=x1, x1=x2, x2=b-(x1-a),y1=y2,y2=f(x2).
* Иначе b=x2,x2=x1,x1=a+(b-x2),y2=y1,y1=f(x1).
3. Шаг 3.
* Если n=1, то x=x1=x2 и останов.
* Иначе возврат к шагу 2.

но тут мне не понятно что за точки деления и целевые функции...
Chica Bond вне форума Ответить с цитированием
Старый 23.05.2010, 23:54   #4
profi
Участник клуба Подтвердите свой е-майл
 
Регистрация: 19.11.2007
Сообщений: 1,022
По умолчанию

Ищи давай, просмотри ссылки на первой странице поиска. Там есть готовые программы, или уже и лень готовое даже искать?

Последний раз редактировалось profi; 23.05.2010 в 23:59.
profi вне форума Ответить с цитированием
Старый 24.05.2010, 00:08   #5
Chica Bond
Пользователь
 
Регистрация: 15.03.2010
Сообщений: 31
По умолчанию

Цитата:
Сообщение от profi Посмотреть сообщение
Ищи давай, просмотри ссылки на первой странице поиска. Там есть готовые программы, или уже и лень готовое даже искать?
нету... честно)) да и врядли есть этот алгоритм на с++... единственное что наверное есть, это как искать числа Фибоначчи... а мне нужен алгоритм Фибоначчиева поиска.... вот алгоритм нашла, терь нужно его понять, чтоб на с++ написать...=))
Chica Bond вне форума Ответить с цитированием
Старый 24.05.2010, 00:16   #6
profi
Участник клуба Подтвердите свой е-майл
 
Регистрация: 19.11.2007
Сообщений: 1,022
По умолчанию

Ппц полный. Вот http://programmersforum.ru/showthrea...0%F7%E8&page=2 пост №19.
profi вне форума Ответить с цитированием
Старый 24.05.2010, 00:22   #7
Chica Bond
Пользователь
 
Регистрация: 15.03.2010
Сообщений: 31
По умолчанию

мда. спасибо конечно, но я вроде бы упоминала что мне не нужно искать числа Фибоначчи. мне нужен алгоритм поиска методом Фибоначчи. задача которую мне нужно решить с помощью этого метода такая:
дан словарь, упорядоченный по возрастанию и содержащий по одному слову в строке. нужно найти в нём заданное слово с помощью фибоначчиева поиска. при этом запрещается считывать в память более одного слова одновременно.
Chica Bond вне форума Ответить с цитированием
Старый 24.05.2010, 10:57   #8
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Поиск Фибоначчи описан у Кнута том 3 раздел 6.2.1. подраздел "Поиск Фибоначчи".
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 24.05.2010, 12:33   #9
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

а вот и код. Правда на Паскале, но рабочий.
Код:
PROGRAM Find_5;
{ Фибоначчиев поиск наименьшего индекса заданного элемента }
{ одномерного "случайного" строго упорядоченного по возрас- }
{ танию числового массива (рекурсивный вариант) }
const N=8; { Количество элементов в массиве }
type Massiv=Array [1..N] of Integer;
var A : Massiv; { Массив, отсортированный по возрастанию }
Key : Integer; { Искомый элемент }
Search: 0..N; { Индекс найденного элемента }
{ 0, если элемент не найден }
Mid : Integer; { Индекс внутреннего элемента }
j,i : Integer;
F1,F2,t: Integer;
Finish : Boolean;
{ ------------------------------------ }
FUNCTION F_i_b (N: Integer): Integer;
var F1,F2: Integer;
BEGIN
	If (N=0) OR (N=1) then F_i_b:=N else If N>=2 then
	begin
		F1:=F_i_b (N-1);
		F2:=F_i_b (N-2);
		F_i_b:=F1+F2
	end
END;
{ --- }
BEGIN
	Write('Введите массив, отсортированный строго по возрастанию: ');
	For i:=1 to N do Read(A[i]);
	Write('Искомый элемент: ');
	Read(Key); j:=1;
	While F_i_b(j)<N+1 do j:=j+1;
	Mid:=N-F_i_b(j-2)+1;
	F1:=F_i_b(j-2);
	F2:=F_i_b(j-3);
	Finish:=FALSE;
	While (Key<>A[Mid]) AND (Finish=FALSE) do If (Mid<=0) OR (Key>A[Mid]) then If F1=1 then Finish:=TRUE else
	begin
		Mid:=Mid+F2;
		F1:=F1-F2;
		F2:=F2-F1
	end
	else If F2=0 then Finish:=TRUE else
	begin
		Mid:=Mid-F2;
		t:=F1-F2;
		F1:=F2;
		F2:=t
	end;
	If Finish then Search:=0 else Search:=Mid;
	WriteLn('Индекс искомого элемента в массиве: ',Search)
END.
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 25.05.2010, 19:23   #10
Chica Bond
Пользователь
 
Регистрация: 15.03.2010
Сообщений: 31
По умолчанию

спасибо огромное!!!)) буду пробовать разбираться))
Chica Bond вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск - ? Evgenii БД в Delphi 11 22.07.2009 19:41
Поиск в БД Karinka БД в Delphi 9 07.12.2008 16:25
Поиск в бд KAKTYC SQL, базы данных 3 25.07.2008 13:21
ПОИСК FIIR БД в Delphi 3 16.06.2008 16:06
Поиск Volkogriz Общие вопросы Delphi 5 22.04.2008 10:59