Question

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

Answer 1

Посмотрите код во вложении

Answer 2

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

program BinarySearchSteps;

const
  ARRAY_SIZE = 32;
  RANGE = 100;
  NUMBER_OF_TESTS = 1000;

type
  TArray = array[1..ARRAY_SIZE] of Integer;

var
  SearchArray: TArray;
  TotalSteps: Integer;
  i, j, Steps: Integer;

// Процедура для сортировки массива
procedure QuickSort(var A: TArray; Left, Right: Integer);
var
  I, J, Pivot, Temp: Integer;
begin
  if Left < Right then
  begin
    Pivot := A[(Left + Right) div 2];
    I := Left;
    J := Right;
    while I <= J do
    begin
      while A[I] < Pivot do
        Inc(I);
      while A[J] > Pivot do
        Dec(J);
      if I <= J then
      begin
        Temp := A[I];
        A[I] := A[J];
        A[J] := Temp;
        Inc(I);
        Dec(J);
      end;
    end;
    QuickSort(A, Left, J);
    QuickSort(A, I, Right);
  end;
end;

// Функция для двоичного поиска
function BinarySearch(const A: TArray; Left, Right, Value: Integer): Integer;
var
  Mid: Integer;
begin
  Result := 0;
  while Left <= Right do
  begin
    Inc(Result);
    Mid := (Left + Right) div 2;
    if A[Mid] = Value then
      Exit(Result)
    else if A[Mid] < Value then
      Left := Mid + 1
    else
      Right := Mid - 1;
  end;
end;

begin
  Randomize;

TotalSteps := 0;

// Проведение тестов
  for i := 1 to NUMBER_OF_TESTS do
  begin
    // Заполнение массива случайными числами
    for j := 1 to ARRAY_SIZE do
      SearchArray[j] := Random(RANGE + 1);

// Сортировка массива
    QuickSort(SearchArray, 1, ARRAY_SIZE);

// Выбор случайного элемента для поиска
    Steps := BinarySearch(SearchArray, 1, ARRAY_SIZE, Random(RANGE + 1));
    TotalSteps := TotalSteps + Steps;
  end;

// Вычисление среднего числа шагов
  WriteLn('Среднее число шагов при двоичном поиске:', TotalSteps / NUMBER_OF_TESTS:0:2);
end.

Этот код создает массив случайных чисел, сортирует его и затем выполняет 1000 поисковых запросов с использованием двоичного поиска для случайных значений в этом диапазоне. Результатом программы будет среднее число шагов, требуемых для поиска случайного числа в массиве методом двоичного поиска.