Написать программу, которая считает среднее число шагов в двоичном поиске для массива - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.

Решение задачи: «Написать программу, которая считает среднее число шагов в двоичном поиске для массива»

textual
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define ELEMENTS (32)
  6. #define ATTEMPTS (1000)
  7. #define MINVALUE (0)
  8. #define MAXVALUE (100)
  9.  
  10. #define bounded_rand(minval, maxval) ( rand() % ((maxval) - (minval) + 1) + (minval) )
  11.  
  12. int * binary_search(const int * array, const size_t count, const int value, size_t * steps) {  
  13.     ++(*steps);
  14.    
  15.     if ( count == 0 )
  16.         return NULL;
  17.     else if ( value == array[count / 2] )
  18.         return (int*)(array + count / 2);
  19.     else if ( value < array[count / 2] )
  20.         return binary_search(array, count / 2, value, steps);
  21.     else
  22.         return binary_search(array + count / 2 + 1, count / 2 - (! (count & 1)), value, steps);
  23. }
  24.  
  25. int cmp(const void * a, const void * b) {
  26.     return *(int*)a - *(int*)b;
  27. }
  28.  
  29. int main(void) {
  30.     int array[ELEMENTS], i;
  31.     size_t allSteps;
  32.    
  33.     srand(time(NULL));
  34.    
  35.     for ( i = 0; i < ELEMENTS; ++i )
  36.         array[i] = bounded_rand(MINVALUE, MAXVALUE);
  37.     qsort(array, ELEMENTS, sizeof(int), cmp);
  38.    
  39.    
  40.     allSteps = 0;
  41.     for ( i = 0; i < ATTEMPTS; ++i ) {
  42.         size_t currentSteps = 0;
  43.         binary_search(array, ELEMENTS, bounded_rand(MINVALUE, MAXVALUE), ¤tSteps);
  44.         allSteps += currentSteps;
  45.     }
  46.    
  47.     printf("Average steps: %.3f\n", (double)allSteps / ATTEMPTS);
  48.    
  49.     /*
  50.     for ( i = 0; i < ELEMENTS; ++i )
  51.         printf("%d ", array[i]);
  52.     printf("\n");
  53.    
  54.     while ( printf("> ") && scanf("%d", &i) == 1 ) {
  55.         int * found;
  56.         allSteps = 0;
  57.         found = binary_search(array, ELEMENTS, i, &allSteps);
  58.         if ( found )
  59.             printf("Found with index %d", found - array);
  60.         else
  61.             printf("Not found");
  62.         printf(" after %d steps.\n", allSteps);
  63.     }
  64.     */
  65.    
  66.     return 0;
  67. }

Объяснение кода листинга программы

  1. Объявлены макросы: ELEMENTS (32) - размер массива ATTEMPTS (1000) - количество попыток поиска MINVALUE (0) - минимальное значение элемента массива MAXVALUE (100) - максимальное значение элемента массива
  2. Выполнена функция main: Инициализирован массив array с помощью функции srand и генератора случайных чисел Массив отсортирован с помощью функции qsort Выполнен цикл ATTEMPTS раз, в котором производится двоичный поиск с помощью функции binary_search и подсчитывается количество шагов Выводится среднее количество шагов поиска Выводится отсортированный массив Выполняется цикл, в котором пользователь может искать элементы в массиве с помощью функции binary_search и получать информацию о количестве шагов поиска и индексе найденного элемента
  3. Определены функции: binary_search - выполняет двоичный поиск в массиве cmp - сравнивает элементы массива
  4. В функции binary_search происходит рекурсивный двоичный поиск элемента в массиве. Вначале увеличивается счетчик шагов (*steps). Если количество элементов в массиве равно 0, то возвращается NULL. Если искомый элемент равен элементу в середине массива, то возвращается указатель на этот элемент. Если искомый элемент меньше элемента в середине массива, то поиск продолжается в левой половине массива. Если искомый элемент больше элемента в середине массива, то поиск продолжается в правой половине массива.
  5. В функции cmp сравниваются элементы массива.
  6. В цикле ATTEMPTS ищется случайное значение в отсортированном массиве с помощью функции binary_search. Для каждого найденного элемента подсчитывается количество шагов поиска и добавляется к общему количеству шагов (allSteps).
  7. Выводится среднее количество шагов поиска.
  8. В цикле пользователь может искать элементы в массиве с помощью функции binary_search. На каждом шаге пользователю предлагается ввести число для поиска или завершить поиск с помощью символа >. Если элемент найден, то выводится информация о количестве шагов поиска и индексе найденного элемента. Если элемент не найден, то выводится сообщение Not found.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.444 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы