привіт. у мене є завдання "Пошук заданих елементів у масиві (послідовний пошук, метод Фібоначчі). Масив не менше 1000 елементів - генерується випадковим чином." що потрібно поправити, аби метод Фібоначчі працював? бо він взагалі не шукає заданий елемент. при цьому, послідовний пошук працює добре.
в компіляторі або виводиться повідомлення "Елемент не знайдено за методом Фібоначчі", або нічого - зависає і не закінчує програму. можливо проблема у виділенні пам'яті?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
int search(int *arr, int size, int k);
int fibonacci(int *arr, int size, int k);
void generate(int *arr, int size);
void writeToFile(int *arr, int size);
int *readFromFile(int size);
//int partition(int *arr, int low, int high);
//void quickSort(int *arr, int low, int high);
int main()
{
setlocale (LC_ALL, "UKR");
system ("chcp 1251");
int size;
printf("Введіть розмір масиву: ");
scanf("%d", &size);
if (size < 1000)
{
printf("Розмір масиву повинен бути більше 1000. Програма завершується.\n");
return 0;
}
int *arr = (int *)malloc(size * sizeof(int));
if (arr == NULL)
{
printf("Помилка виділення пам'яті.\n");
return 0;
}
generate(arr, size);
writeToFile(arr, size);
printf("Масив записано у файл.\n");
arr = readFromFile(size);
if (arr == NULL)
{
printf("Програма не виконана.\n");
return 0;
}
// quickSort(arr, 0, size-1);
printf("Програма працює успішно.\n");
int k;
printf("Введіть значення, яке потрібно знайти: ");
scanf("%d", &k);
// Пошук за допомогою послідовного пошуку
int sIndex = search(arr, size, k);
if (sIndex != -1)
{
printf("Елемент знайдено за послідовним пошуком під порядковим номером: %d\n", sIndex);
}
else
{
printf("Елемент не знайдено за послідовним пошуком.\n");
}
// Пошук за допомогою методу Фібоначчі
int fIndex = fibonacci(arr, size, k);
if (fIndex != -1)
{
printf("Елемент знайдено за методом Фібоначчі під порядковим номером: %d\n", fIndex);
}
else
{
printf("Елемент не знайдено за методом Фібоначчі.\n");
}
free(arr);
return 0;
}
int search(int *arr, int size, int k)
{
int i;
for (i=0; i<size; i++)
{
if (arr[i] == k)
{
return i;
}
}
return -1;
}
int fibonacci(int *arr, int size, int k)
{
if (arr == NULL || size == 0)
{
return -1;
}
if (k < arr[0] || k > arr[size - 1])
{
return -1;
}
int fib2 = 0; // попереднє число Фiбoначчi
int fib1 = 1; // поточне число Фiбoначчi
int temp;
while (fib1 < size-1)
{
temp = fib1;
fib1 = fib1 + fib2;
fib2 = temp;
}
int left_index = 0;
int mid_index = fib1 - 2;
while (fib1 > 1)
{
if (mid_index >= size-1)
{
mid_index = size - 1;
}
switch (k - arr[mid_index])
{
case 0:
return mid_index;
case -1:
mid_index = mid_index - (fib1 - fib2 - 1);
temp = fib1;
fib1 = fib1 - fib2;
fib2 = temp - fib1;
break;
case 1:
left_index = mid_index + 1;
temp = fib1;
fib1 = fib2;
fib2 = temp - fib1;
break;
}
}
if (fib1 == 1 && arr[left_index] == k)
return left_index;
return -1;
}
void generate(int *arr, int size)
{
int i;
srand(time(NULL));
for (i=0; i<size; i++)
{
arr[i] = rand() % size + 1;
}
}
void writeToFile(int *arr, int size)
{
FILE *file = fopen("array.txt", "w");
if (file == NULL)
{
printf("Помилка відкриття файлу для запису.\n");
return;
}
int i;
for (i=0; i<size; i++)
{
fprintf(file, "%d\n", arr[i]);
}
fclose(file);
}
int *readFromFile(int size)
{
FILE *file = fopen("array.txt", "r");
if (file == NULL)
{
printf("Помилка відкриття файлу для читання.\n");
return NULL;
}
int *arr = (int *)malloc(size * sizeof(int));
if (arr == NULL)
{
printf("Помилка виділення пам'яті.\n");
fclose(file);
return NULL;
}
int i;
for (i=0; i<size; i++)
{
if (fscanf(file, "%d", &arr[i]) != 1)
{
printf("Помилка читання з файлу.\n");
free(arr);
fclose(file);
return NULL;
}
}
fclose(file);
return arr;
}
/*int partition(int *arr, int low, int high)
{
int pivot=arr[high];
int i = low - 1;
int j = high + 1;
int temp;
if (low >= high)
{ return high; }
while (1)
{
do
{
i++;
} while (arr[i] < pivot);
do
{
j--;
} while (arr[j] > pivot);
if (i >= j)
return j;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void quickSort(int *arr, int low, int high)
{
int stack[high - low + 1];
int top = -1;
stack[++top] = low;
stack[++top] = high;
while (top >= 0)
{
high = stack[top--];
low = stack[top--];
int pi = partition(arr, low, high);
if (pi - 1 > low)
{
stack[++top] = low;
stack[++top] = pi - 1;
}
if (pi + 1 < high)
{
stack[++top] = pi + 1;
stack[++top] = high;
}
}
}*/P.S.: закоментовано дві функції для сортування масиву. пробувала так, але все одно не працювало