Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 28.10.2017
Сообщений: 6
1

Фибоначчиев поиск наименьшего индекса заданного элемента (Pascal -> C++)

25.11.2017, 01:03. Просмотров 1688. Ответов 4
Метки нет (Все метки)

При выполнении лаб. работы возникли сложности, решила поискать в интернете пример кода, нашла только упрощенную версию, но как-то не правильно перевожу ее на С++, не изучала паскаль. Помогите, пожалуйста.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.11.2017, 01:03
Ответы с готовыми решениями:

Поиск индекса самого наименьшего элемента в массиве
Нужно написать шаблонную функцию, которая будет возвращать индекс самого наименьшего элемента в...

Поиск индекса наименьшего элемента одномерного массива
Найти и напечатать индекс наименьшего элемента одномерного массива Р размерности М. Из разных...

Поиск индекса заданного элемента в отсортированном массиве
1. Заполнить статический массив значениями 90, 76, 54, 23, 56, 12, 48. Результат в виде таблицы...

Быстрый поиск индекса заданного элемента в упорядоченном массиве
Пусть отсортированный по возрастанию массив из n элементов a. Требуется максимально быстро найти...

4
6912 / 5977 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
25.11.2017, 11:51 2
Где программа?
0
0 / 0 / 0
Регистрация: 28.10.2017
Сообщений: 6
25.11.2017, 12:22  [ТС] 3
если вы про не получившийся перевод, то вот
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
void  main()  
{
    setlocale(LC_ALL,"Rus");
    int Search;
    int  key; //искомый ключ
    int n; //Количество элементов в массиве
    int j,i;
    int Mid; // Индекс внутреннего элемента    
    int F1,F2,t; 
    bool Finish; 
    cout<<"Размер  массива  >  ";  cin>>n;
    int  *mas=  new  int[n];  //динамический  массив
    for  (int  i=0;  i<=n;  i++)
        mas[i]=rand()%100;  //заполнение  массива  случайными  числами
    sortV(n,  mas);//сортировка  массива
    for  (int  i=1;  i<=n;  i++)
        cout<<mas[i]<<"  "<<endl;  //вывод  массива  
    cout<<"Искомый  элемент  >  ";
    cin>>key;  //ввод  искомого  числа     W
    j=1;  
    while(Fib(j)<n+1)
        j=j+1; 
    Mid=n-Fib(j-2)+1; 
    F1=Fib(j-2); 
    F2=Fib(j-3); 
    Finish=false; 
    while((key!=mas[Mid])&&(Finish==false))
    {
        if((Mid<=0) || (key>mas[Mid]))
        {
            if(F1=1)
                Finish=true; 
            else 
            Mid=Mid+F2;
            F1=F1-F2;
            F2=F2-F1;
        }
        else
        {
            if(F2==0) 
                Finish=true;
            else
            {
                Mid=Mid-F2; 
                t=F1-F2; 
                F1=F2; 
                F2=t;   
            }
        }
        if(Finish)
            Search=0;
        else 
            Search=Mid;
        cout<<"Индекс искомого элемента в массиве "<<Search<<endl;
    } 
    
 
    cout<<endl;
    system("pause");
}
Добавлено через 16 минут
Я понимаю, там полный бред у меня получился, но не знаю как по другому исправить
0
6912 / 5977 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
25.11.2017, 12:47 4
Лучший ответ Сообщение было отмечено AlexRadi как решение

Решение

Если это твоя задача, то откуда там случайные числа? Массив должен быть упорядочен изначально.
Вот этот вариант посмотри: Фибоначчиев поиск
Утверждают, что работает, только под Builder сделано. Надо ввод добавить.
0
0 / 0 / 0
Регистрация: 28.10.2017
Сообщений: 6
25.11.2017, 13:19  [ТС] 5
Массив отсортирован, я просто функцию сюда эту не написала. В 15 строке идет сортировка. Но код сейчас посмотрю, который Вы скинули, спасибо

Добавлено через 12 минут
Как надо переделала, все работает, спасибо большое!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.11.2017, 13:19

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Поиск минимального значения элемента и определение порядкового номера наименьшего элемента
Дана непустая последовательность различных натуральных чисел. Определить порядковый номер...

Поиск минимального значения элемента и определение порядкового номера наименьшего элемента
Необходимо написать программу, формирующую рандомный одномерный массив, а после определяющую...

Поиск индекса элемента
приветствую! помогите пожалуйста! Напишите функцию elemIndices :: Eq a =&gt; a -&gt; -&gt; , которая...

Нахождение индекса элемента ближайшего по значению от заданного с переменными условиями
Здравствуйте уважаемые участники, не раз помогали, надеюсь и в этот раз получится, ибо сам пару...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.