Написать программу, которая считает среднее число шагов в двоичном поиске для массива - 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;
}

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

  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
Похожие ответы