Информатика, опубликовано 08.03.2019 15:20
Паскаль - массивы. написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. для поиска использовать 1000 случайных чисел в этом же интервале.
Ответ оставил: Гость
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
Ответ оставил: Гость
Информатика, опубликовано 09.01.2019 16:01
Информатика, опубликовано 09.01.2019 16:01
Информатика, опубликовано 09.01.2019 16:01
Информатика, опубликовано 09.01.2019 16:01