Question

напишите программу, которая считает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне 0...100. Для поиска используйте 1000 случайных чисел в том же диапазоне. ЯЗЫК PYTHON, ОБЯЗАТЕЛЬНО КОММЕНТАРИЙ НА КАЖДУЮ СТРОЧКУ КОДА, ДАЮ 60 БАЛЛОВ

Answer 1

Ответ:

# подключаем модуль, чтобы использовать случайные числа

from random import *

 

a = [0]*32   # Создание списка

for i in range (0, 32):

   a[i] = randint(1, 101)  # заполнение случайными числами

   

a.sort() # сортировка

print(a) # вывод на экран

b = int(input('Введите число для поиска : '))   # ввод числа для поиска

 

mid = len(a) // 2  # определяем средний элемент списка

low = 0            # определяем верхнюю границу списка

high = len(a) - 1  # определяем верхнюю границу списка

step = 0           # обнуляем счётчик шагов

 

while a[mid] != b and low <= high:  # в цикле пока не нашли искомый элемент

   if b > a[mid]:  # если искомый элемент > среднего элемента в диапазоне

       low = mid + 1  # то нижнюю границу выставим в середину диапазона

   else:           # если искомый элемент <= среднего элемента в диапазоне

       high = mid - 1 # то верхнюю границу выставим в середину диапазона

   mid = (low + high) // 2  # считаем новый средний элемент диапазона

   step += 1  # увеличиваем счётчик на 1

 

if low > high:

   print('Нет числа')

else:

   print('Количество шагов = ', step)

   print('Индекс = ', mid)

Answer 2

Конечно, вот программа на Python, которая рассчитывает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне от 0 до 100, используя 1000 случайных чисел:

pythonCopy code
import random

def binary_search(arr, target):
    """Функция для двоичного поиска элемента в отсортированном массиве."""
    left, right = 0, len(arr) - 1
    steps = 0

    while left <= right:
        mid = left + (right - left) // 2
        steps += 1  # Увеличиваем количество шагов при каждой итерации

        if arr[mid] == target:
            return steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return steps  # Возвращаем количество шагов, если элемент не найден

def calculate_average_steps():
    """Рассчитываем среднее количество шагов для двоичного поиска."""
    total_steps = 0
    num_trials = 1000
    array_size = 32
    value_range = (0, 100)

    for _ in range(num_trials):
        # Генерируем случайный отсортированный массив из 32 элементов
        arr = sorted(random.sample(range(value_range[0], value_range[1] + 1), array_size))
        # Генерируем случайное число, которое будем искать
        target = random.randint(value_range[0], value_range[1])
        # Вызываем двоичный поиск и суммируем количество шагов
        total_steps += binary_search(arr, target)

    # Рассчитываем среднее количество шагов
    average_steps = total_steps / num_trials
    return average_steps

# Вызываем функцию для рассчета среднего количества шагов
average_steps = calculate_average_steps()
print(f"Среднее количество шагов для двоичного поиска: {average_steps}")

Эта программа сначала определяет функцию для двоичного поиска в отсортированном массиве. Затем она создает массивы, запускает двоичный поиск для 1000 случайных чисел и считает общее количество шагов. На последнем этапе программа рассчитывает среднее количество шагов и выводит его.