Bonjour, cher Khabrovites. Une série d'articles contient une discussion sur les tâches qui sont données en 8e année lors des cours d'informatique au lycée de physique et de mathématiques de Chelyabinsk n ° 31. Un peu d'histoire ... Notre lycée est l'un des établissements d'enseignement les plus solides de Russie, qui occupe la 5e place du classement sur la compétitivité des diplômés, s'inclinant devant les écoles de Moscou et de Saint-Pétersbourg. Les élèves gagnent régulièrement des compétitions aux niveaux national et international.
Cet article est dépourvu de théorie, il ne contient que des méthodes pour résoudre les problèmes. Les détails sur la recherche de bacs sont décrits ici.
Passons donc aux tâches. Ces tâches impliquent l'utilisation de la recherche binaire, y compris la recherche de réponses dans le bac. Comme nous le savons, la recherche bin est un algorithme de recherche d'objets par un attribut donné dans un ensemble d'objets. Nous demandons des listes triées par ordre croissant / décroissant. Seulement 4 tâches, dont 2 visent à appliquer «l'algorithme sans raisins secs» .
Dans cette tâche, vous devez d'abord considérer les longueurs des première et deuxième lignes, puis écrire chaque ligne suivante dans une liste. Après avoir pris chaque élément de la deuxième liste et recherché la bordure droite et gauche. Vous pouvez remarquer que si le nombre ne figure pas dans la liste, les valeurs totales de la bordure gauche et de la bordure droite dans la recherche de bacs gauche et droit sont égales.
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)
Voici ce puzzle avec une touche! Ici, il est nécessaire de transformer la recherche afin qu'elle soit effectuée même pour les numéros qui ne figurent pas dans la liste de recherche. Ici, nous recherchons également le milieu dans la "liste des limites", puis l'élément qui au milieu est comparé au nombre, s'il est inférieur à celui-ci, nous écrivons l'index du milieu + 1 (c'est-à-dire, n'incluons pas le milieu passé dans la liste des limites) à la bordure de gauche (qui est l'index), sinon, dans la bordure droite, nous écrivons l'index du milieu. Nous faisons tout cela alors que la bordure gauche est plus petite que la droite. Après avoir trouvé gauche et droite, nous considérons le cas où le nombre n'est pas dans la liste et la distance à gauche est inférieure ou égale à celle de droite. Par conséquent, nous déduisons un [gauche - 1], sinon un [gauche].
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])
Tadam! La tâche de la recherche binaire par réponse. Pour commencer, à partir de la bibliothèque mathématique, nous connectons la fonction sqrt, qui calcule la racine carrée, après quoi nous définissons 0 pour la bordure gauche et 1e10 pour la bordure droite, soit 10 milliards, en fonction des restrictions spécifiées dans la condition. Ensuite, comme dans une recherche de casier typique, nous recherchons le milieu, puis nous comparons. Mais qu'est-ce qui est intéressant? Ici, le milieu est x dans l'équation. Compte tenu de cela, nous déterminons la valeur de l'équation et la comparons avec la vraie réponse (c'est-à-dire C). Eh bien, nous déplaçons les limites, jusqu'à ce que la différence de limites soit inférieure ou égale à 10 milliards, c'est la précision de la mesure. Plus tard, nous multiplions par un million, arrondissons, traduisons en division int et réelle par le même million.
from math import sqrt c = float(input()) left = 0 right = 1e10
Il y a déjà une analyse pour cette tâche, donc je ne joindrai que le code.
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)
Pour consolider le matériel, vous pouvez résoudre les problèmes à partir d'ici.