Написать программу, которая считает среднее число шагов в двоичном поиске для массива - 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д