Фибоначчиев поиск в массиве случайных чисел - C++ - Ответ 11693870

@БузинВладимир · Регистрация: 21.08.2017

Author24 — интернет-сервис помощи студентам

Добрый вечер! Столкнулся с заданием по поиску ключей в массиве, и там был указан фибоначчиев поиск. Много читал, пытался понять и в итоге нашел код на Паскале, но разобраться в нём не смог.Подскажите, как переписать с Паскаля на C++, что и как заменить? Я хотел его сделать шаблоном к следующему коду:

C++

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <conio.h>
using namespace std;
 
template <typename R>
void Sort (R *x, int t) {
R tmp;
for(int k = t - 1; k>0; k--) {
for(int i = 0; i<k; i++) {
if(x[i] > x[i+1]) {
tmp = x[i];
x[i] = x[i+1];
x[i+1] = tmp;
}
}
}
}
 
int main() {
int I, n, key;
cout << “Vvedite razmer massiva N:\n”;
cin >> n;
int *MyArr = new int [n];
srand(time(NULL));
for (i = 0; i < n; i++) {
MyArr[i] = rand() % 201;
}
Sort<int>( MyArr, n);
cout << “Kakoj element massiva nuzhno najti?\n”;
cin >> key;
delete []MyArr;
_getch();
return 0;
}

Написать программу, которая:
1) Запрашивает у пользователя размер одномерного массива и ключ для поиска;
2) Формирует массив случайных чисел заданного размера;
3) Осуществляет сортировку обменом получившегося массива;
4) Осуществляет фибоначчиев поиск в отсортированном массиве;
5) Возвращает количество найденных в массиве совпадений с ключом и их порядковые номера.

Решение на языке Pascal:

Pascal

{
j=1;
while (fib[j] < n + 1 )
207
 
j = j + 1;
 
mid=n-fib(j-2)+ 1;
 
f1=fib(j – 2);
 
f2=fib(j – 3);
 
finish=FALSE;
 
while (key != k(mid)) and (finish = FALSE)
 
{
 
if (mid <= 0) || (key > k(mid))
 
{
 
if (f1 == 1)
 
finish=TRUE;
 
else
 
{
 
mid=mid + f2;
 
f1 = f1 –f2;
 
f2 = f2 – f1;
 
}
 
}
 
else
 
{
I
if (f2 == 0)
 
finish=TRUE;
 
else
 
{
 
mid = mid – f2;
 
t = f1 – f2;
 
f1 = f2;
 
f2 = t;
 
}
 
}
`}
if (finish) search = 0;
else
search=mid;
}

Что это за функция fib?

Вернуться к обсуждению:
Фибоначчиев поиск в массиве случайных чисел C++

Следующий ответ

Другие темы раздела
C++ Перестановка четвертей в матрице https://www.cyberforum.ru/ cpp-beginners/ thread2118287.html Необходимо в матрице 6x6 переставить местами четверти как изображено на предпоследнем стоблце	Как производить все обращения к элементам массива с использвованием указателей? C++ #include <time.h> #include <stdio.h> #include <math.h> #include <conio.h> #include <iostream> #include<Windows.h> using namespace std; int main()
C++ Цвета в тексте Как мне можно сделать цвет для отдельного текста? void Draw() { system("cls"); for (int i = 0; i < shir + 1; i++) cout << "#"; cout << endl; for (int i = 0; i < dlin; i++) { for (int j = 0; j < shir; j++) { https://www.cyberforum.ru/ cpp-beginners/ thread2118278.html	C++ Определить седловую точку матрицы (статическая библиотека) https://www.cyberforum.ru/ cpp-beginners/ thread2118273.html Задание : определить седловую точку двумерной матрицы. Если она есть, то все элементы матрицы =0, кроме седловой точки, а если седловой точки нет, то вывести на экран "Нет седловой точки". Использовать статическую библиотеку. Вот мэйн код: #include "stdafx.h" #include <iostream> #include <conio.h> #include <windows.h> #include "header.h" using namespace std;
C++ Проверить истинность выражения Здравствуйте, недавно перешел с Си в С++ Помогите составить программу: "Дано натуральное число n. Проверить справедливость равенства" Пример в вложениях или по ссылке. ************/h7wnmp Заранее огромное спасибо.	C++ Проверить, является ли год високосным #include <iostream> bool is_leap(int year) { if(year % 4 == 0) { return true; } return false; } https://www.cyberforum.ru/ cpp-beginners/ thread2118268.html
C++ Мое видение вызова функции https://www.cyberforum.ru/ cpp-beginners/ thread2118263.html main() { char fun( int&, int); int x, y=11, z; char *s; x=new int (19); s=new char; … }	Удаление повторяющихся слов - deque C++ Привет всем!У меня программа,которая удаляет повторяющиеся слова. Например входные данные: 4 черный белый черный синий Выход: белый синий Но если повторяющихся слов нечетное количество,то одно слово остается в списке. Например вход: 5
C++ Ввод и вывод текста в таблицу с сортировкой 1 столбца https://www.cyberforum.ru/ cpp-beginners/ thread2118257.html Здравствуйте. Помогите, пожалуйста, написать фрагмент кода программы(функции, в которых выполняется условие задачи), в которой будут вводиться 7-10 строк таблицы (пример на фото) и выводиться на экран таблица - сразу после ее ввода и после сортировки ее по значениям в первом столбце. Заранее спасибо.	C++ Построение таблицы значений https://www.cyberforum.ru/ cpp-beginners/ thread2118251.html Помогите построить таблицу значений функции F=-2.3cos((x-7)/y) при -7<=x<=-3 c шагом 1.5; 3<=y<=5 c шагом 0.6. Найти максимальное значение функции среди 1<=F<=2. Пожалуйста, кому не сложно, помогите хоть чем-то.
Как производить все обращения к элементам массива с использвованием указателей? C++ #include "stdafx.h" #include <iostream> #include <cmath> using namespace std; int main() { double x = 1.1, eps = 0.001; double term = x, sum = 0; int i = 1;	C++ Как присвоить переменным значение слова на русском? https://www.cyberforum.ru/ cpp-beginners/ thread2118229.html хочу сделать так: #include <iostream> using namespace std; int main() {

	08.11.2017, 22:06