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

Ответы 1

  • const  n=32;var  a:array[1..n] of integer;  i,j,k,p,left,right,center:integer;begin  { заполнить массив данными }  Randomize;  for i:=1 to n do a[i]:=Random(101);  { отсортировать массив во возрастанию - пузырьковый метод }  for i := 1 to n-1 do    for j := 1 to n-i do      if a[j] > a[j+1] then      begin k := a[j]; a[j] := a[j+1]; a[j+1] := k end;  { тысяча поисков случайных чисел }  k:=0;  for j:=1 to 1000 do  begin    p:=Random(101);    { собственно, двоичный поиск }    left:=1; right:=n;    while left<right do    begin      Inc(k);      if (a[left]=p) or (a[right]=p) then left:=right { нашли }      else begin        center:=(left+right) div 2;        if a[center]=p then left:=right { нашли }        else          if a[center]<p then left:=center+1          else right:=center      end    end  end;  Writeln('Среднее число поисков равно ',k/1000:4:2)end.Тестовое решение:Среднее число поисков равно 4.61
  • Добавить свой ответ

Войти через Google

или

Забыли пароль?

У меня нет аккаунта, я хочу Зарегистрироваться

How much to ban the user?
1 hour 1 day 100 years