М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
avanesyan20011
avanesyan20011
18.06.2022 05:12 •  Информатика

На !
реализуйте алгоритм приближенного бинарного поиска.

входные данные

в первой строке входных данных содержатся числа n и k. во второй строке n чисел первого массива, отсортированного по неубыванию, а в третьей строке – k чисел второго массива. каждое число в обоих массивах по модулю не превосходит 2109.

выходные данные

для каждого из k чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. если таких несколько, выведите меньшее из них.

примеры

входные данные

5 5

1 3 5 7 9

2 4 8 1 6

выходные данные

1

3

7

1

5

👇
Ответ:
Sestare852
Sestare852
18.06.2022

Просто прогоняем бинарный поиск дважды, сначала ищем ближайшее число, не большее нужного, потом не меньшее. Для того, чтобы такие числа были, можно дописать в массив очень большое число и очень маленькое. Затем выбираем из этих двух найденных чисел то, что будет ближе.

Пример реализации:

def bin_search(arr, target, kind="<="):

   assert kind in ["<=", ">="]

   if kind == "<=":

       comp = lambda a, b: a <= b

   else:

       comp = lambda a, b: a < b

   l = 0

   r = len(a) - 1

   while l < r - 1:

       m = (l + r) // 2

       if comp(a[m], target):

           l = m

       else:

           r = m

   if kind == "<=":

       return arr[l]

   else:

       return arr[r]

def nearest(arr, target):

   nearest_le = bin_search(arr, target, "<=")

   nearest_ge = bin_search(arr, target, ">=")

   if nearest_ge - target < target - nearest_le:

       return nearest_ge

   else:

       return nearest_le

_ = input()

a = [int(x) for x in input().split()]

a = [float("-Infinity")] + a + [float("+Infinity")]

for target in map(int, input().split()):

   print(nearest(a, target))

4,6(11 оценок)
Открыть все ответы
Ответ:
kiss123kiss
kiss123kiss
18.06.2022

program HelloWorld;

var a: array of integer;

var N, min, max, i, variable:integer;

begin

   min := 32767;

   max := 0;

   readln(N);

   for i := 0 to N do begin  

       readln(variable);

       if (variable > 0) and (variable mod 2 = 0) and (variable > max) then

           max := variable;

       if (variable > 0) and (variable mod 2 = 0) and (variable < min) then

           min := variable;

   end;

   if (max <> 0) and (min <> 32767) then

       writeln(min, ' ', max)

   else  

       writeln(-1);

end.

4,5(39 оценок)
Ответ:

program HelloWorld;

var a: array of integer;

var N, min, max, i, variable:integer;

begin

   min := 32767;

   max := 0;

   readln(N);

   for i := 0 to N do begin  

       readln(variable);

       if (variable > 0) and (variable mod 2 = 0) and (variable > max) then

           max := variable;

       if (variable > 0) and (variable mod 2 = 0) and (variable < min) then

           min := variable;

   end;

   if (max <> 0) and (min <> 32767) then

       writeln(min, ' ', max)

   else  

       writeln(-1);

end.

4,6(67 оценок)
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ