Debriefing tareas. Beanpoisk_1

Hola queridos Khabrovites. Una serie de artículos contiene una discusión de las tareas que se imparten en el octavo grado en las clases de ciencias de la computación en el Liceo de Física y Matemáticas de Cheliábinsk No. 31. Un poco de historia ... Nuestro liceo es una de las instituciones educativas más sólidas de Rusia, que ocupa el quinto lugar en el ranking de competitividad de los graduados, perdiendo en las escuelas de Moscú y San Petersburgo. Los alumnos regularmente ganan competiciones a nivel nacional e internacional.
Este artículo carece de teoría; contiene solo métodos para resolver problemas. Los detalles sobre la búsqueda de contenedores se describen aquí.
Entonces, pasemos a las tareas. Estas tareas implican el uso de búsqueda binaria, incluida la búsqueda de respuestas en el contenedor. Como sabemos, la búsqueda de bin es un algoritmo para buscar objetos por un atributo dado en un conjunto de objetos. Solicitamos listas ordenadas en orden ascendente / descendente. Solo 4 tareas, 2 de las cuales están destinadas a aplicar el "algoritmo sin pasas" .

Búsqueda binaria izquierda y derecha

En esta tarea, primero debe considerar las longitudes de las líneas primera y segunda, luego escribir cada línea siguiente en una lista. Después tomamos cada elemento de la segunda lista y buscamos el borde derecho e izquierdo. Puede observar que si el número no está en la lista, los valores totales del borde izquierdo y el borde derecho en la búsqueda de bin izquierda y derecha son iguales.

n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = -1 right = len(a) # ,     while right - left > 1: middle = (right + left) // 2 if a[middle] < x: left = middle else: right = middle left_1 = -1 right_1 = len(a) # ,     while right_1 - left_1 > 1: middle = (right_1 + left_1) // 2 if a[middle] <= x: left_1 = middle else: right_1 = middle if left == left_1 and right == right_1: print(0) #     ,     continue if right == left_1: print(right + 1, right + 1) else: print(right + 1, left_1 + 1) 

Búsqueda binaria aproximada

¡Aquí está este rompecabezas con un giro! Aquí es necesario transformar la búsqueda para que se realice incluso para los números que no están en la lista para la búsqueda. Aquí también buscamos el medio en la "lista de límites", luego el elemento que en el medio se compara con el número, si es menor, escribimos el índice medio + 1 (es decir, no incluya el último medio en la lista de límites) en el borde izquierdo (que es el índice), de lo contrario, en el borde derecho escribimos el índice del medio. Hacemos todo esto mientras el borde izquierdo es más pequeño que el derecho. Después de encontrar izquierda y derecha, consideramos el caso cuando el número no está en la lista y la distancia a la izquierda es menor o igual que a la derecha. Por lo tanto, deducimos una [izquierda - 1], de lo contrario una [izquierda].

 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = 0 right = n - 1 while left < right: middle = (left + right) // 2 if a[middle] < x: left = middle + 1 else: right = middle if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x): print(a[left - 1]) else: print(a[left]) 

Raíz cuadrada y cuadrada cuadrada

Tadam! La tarea de búsqueda binaria por respuesta. Para comenzar, desde la biblioteca matemática conectamos la función sqrt, que calcula la raíz cuadrada, después de lo cual definimos 0 para el borde izquierdo y 1e10 para el borde derecho, es decir, 10 mil millones, según las restricciones especificadas en la condición. Luego, como en una búsqueda de bin típica, estamos buscando el medio, luego lo comparamos. Pero que es interesante? Aquí el medio es x en la ecuación. En vista de esto, determinamos el valor de la ecuación y la comparamos con la respuesta real (es decir, C). Bueno, movemos los límites, hasta que la diferencia en los límites sea menor o igual a 10 mil millones, esta es la precisión de la medición. Más tarde multiplicamos por un millón, redondeamos, traducimos en división int y real por el mismo millón.

 from math import sqrt c = float(input()) left = 0 right = 1e10#1 c 10-  while right - left > 10e-10:#10   1 middle = (left + right) / 2 if middle * middle + sqrt(middle) >= c: right = middle else: left = middle #  10e6, ,   int,   10e6 print(int(round(left*10e6))/10e6) 

Desafío muy fácil

Ya hay un análisis para esta tarea, por lo que solo adjuntaré el código.

 n, x, y = map(int, input().split()) min1 = min(x, y) if n == 1: print(min1) else: left = 0 right = n * (x + y - min1 + 1) while right - left > 1: middle = (right + left) // 2 if n - 1 <= middle // x + middle // y: right = middle else: left = middle print(min1 + left + 1) 

Para consolidar el material, puede resolver problemas desde aquí.