Написать программу, которая считает среднее число шагов в двоичном поиске для массива - C (СИ)
Формулировка задачи:
Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.
Решение задачи: «Написать программу, которая считает среднее число шагов в двоичном поиске для массива»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ELEMENTS (32)
#define ATTEMPTS (1000)
#define MINVALUE (0)
#define MAXVALUE (100)
#define bounded_rand(minval, maxval) ( rand() % ((maxval) - (minval) + 1) + (minval) )
int * binary_search(const int * array, const size_t count, const int value, size_t * steps) {
++(*steps);
if ( count == 0 )
return NULL;
else if ( value == array[count / 2] )
return (int*)(array + count / 2);
else if ( value < array[count / 2] )
return binary_search(array, count / 2, value, steps);
else
return binary_search(array + count / 2 + 1, count / 2 - (! (count & 1)), value, steps);
}
int cmp(const void * a, const void * b) {
return *(int*)a - *(int*)b;
}
int main(void) {
int array[ELEMENTS], i;
size_t allSteps;
srand(time(NULL));
for ( i = 0; i < ELEMENTS; ++i )
array[i] = bounded_rand(MINVALUE, MAXVALUE);
qsort(array, ELEMENTS, sizeof(int), cmp);
allSteps = 0;
for ( i = 0; i < ATTEMPTS; ++i ) {
size_t currentSteps = 0;
binary_search(array, ELEMENTS, bounded_rand(MINVALUE, MAXVALUE), ¤tSteps);
allSteps += currentSteps;
}
printf("Average steps: %.3f\n", (double)allSteps / ATTEMPTS);
/*
for ( i = 0; i < ELEMENTS; ++i )
printf("%d ", array[i]);
printf("\n");
while ( printf("> ") && scanf("%d", &i) == 1 ) {
int * found;
allSteps = 0;
found = binary_search(array, ELEMENTS, i, &allSteps);
if ( found )
printf("Found with index %d", found - array);
else
printf("Not found");
printf(" after %d steps.\n", allSteps);
}
*/
return 0;
}
Объяснение кода листинга программы
- Объявлены макросы: ELEMENTS (32) - размер массива ATTEMPTS (1000) - количество попыток поиска MINVALUE (0) - минимальное значение элемента массива MAXVALUE (100) - максимальное значение элемента массива
- Выполнена функция main: Инициализирован массив array с помощью функции srand и генератора случайных чисел Массив отсортирован с помощью функции qsort Выполнен цикл ATTEMPTS раз, в котором производится двоичный поиск с помощью функции binary_search и подсчитывается количество шагов Выводится среднее количество шагов поиска Выводится отсортированный массив Выполняется цикл, в котором пользователь может искать элементы в массиве с помощью функции binary_search и получать информацию о количестве шагов поиска и индексе найденного элемента
- Определены функции: binary_search - выполняет двоичный поиск в массиве cmp - сравнивает элементы массива
- В функции binary_search происходит рекурсивный двоичный поиск элемента в массиве. Вначале увеличивается счетчик шагов (*steps). Если количество элементов в массиве равно 0, то возвращается NULL. Если искомый элемент равен элементу в середине массива, то возвращается указатель на этот элемент. Если искомый элемент меньше элемента в середине массива, то поиск продолжается в левой половине массива. Если искомый элемент больше элемента в середине массива, то поиск продолжается в правой половине массива.
- В функции cmp сравниваются элементы массива.
- В цикле ATTEMPTS ищется случайное значение в отсортированном массиве с помощью функции binary_search. Для каждого найденного элемента подсчитывается количество шагов поиска и добавляется к общему количеству шагов (allSteps).
- Выводится среднее количество шагов поиска.
- В цикле пользователь может искать элементы в массиве с помощью функции binary_search.
На каждом шаге пользователю предлагается ввести число для поиска или завершить поиск с помощью символа
>. Если элемент найден, то выводится информация о количестве шагов поиска и индексе найденного элемента. Если элемент не найден, то выводится сообщениеNot found.