Nachbesprechungsaufgaben. Beanpoisk_1

Hallo, liebe Chabrowiten. Eine Artikelserie enthält eine Diskussion der Aufgaben, die in der achten Klasse im Informatikunterricht am Tscheljabinsker Physik- und Mathematik-Lyzeum Nr. 31 gestellt werden. Ein bisschen Geschichte ... Unser Lyzeum ist eine der stärksten Bildungseinrichtungen in Russland. Sie belegt den 5. Platz in der Rangliste der Wettbewerbsfähigkeit von Absolventen und verliert gegen Schulen in Moskau und St. Petersburg. Die Schüler gewinnen regelmäßig Wettbewerbe auf nationaler und internationaler Ebene.
Dieser Artikel enthält keine Theorie und enthält nur Methoden zur Lösung von Problemen. Details zur Bin-Suche werden hier beschrieben.
Kommen wir also zu den Aufgaben. Diese Aufgaben umfassen die Verwendung der binären Suche, einschließlich der bin-Suche nach Antworten. Wie wir wissen, ist die Bin-Suche ein Algorithmus zum Suchen nach Objekten anhand eines bestimmten Attributs in einer Reihe von Objekten. Wir beantragen Listen, die in aufsteigender / absteigender Reihenfolge sortiert sind. Nur 4 Aufgaben, von denen 2 darauf abzielen, den "Algorithmus ohne Rosinen" anzuwenden.

Binäre Suche links und rechts

Bei dieser Aufgabe müssen Sie zuerst die Länge der ersten und zweiten Zeile berücksichtigen und dann jede nächste Zeile in eine Liste schreiben. Nachdem wir jedes Element der zweiten Liste genommen haben, suchen wir nach dem rechten und linken Rand dafür. Möglicherweise stellen Sie fest, dass die Gesamtwerte des linken und des rechten Randes in der linken und rechten Bin-Suche gleich sind, wenn die Nummer nicht in der Liste enthalten ist.

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) 

Ungefähre binäre Suche

Hier ist dieses Puzzle mit einer Wendung! Hier ist es notwendig, die Suche so zu transformieren, dass sie auch für Zahlen durchgeführt wird, die nicht in der Liste für die Suche enthalten sind. Hier suchen wir auch nach der Mitte in der „Grenzliste“. Wenn das Element in der Mitte mit der Zahl verglichen wird, schreiben wir den mittleren Index + 1 (dh die letzte Mitte nicht in die Grenzliste aufnehmen) an den linken Rand (der Index). Andernfalls schreiben wir am rechten Rand den mittleren Index. Wir machen das alles, während der linke Rand kleiner als der rechte ist. Nachdem wir links und rechts gefunden haben, betrachten wir den Fall, in dem die Zahl nicht in der Liste enthalten ist und der Abstand nach links kleiner oder gleich dem nach rechts ist. Daher leiten wir ein [left - 1] ab, andernfalls ein [left].

 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]) 

Quadratwurzel und Quadratquadrat

Tadam! Die Aufgabe der binären Suche nach Antwort. Zunächst verbinden wir aus der Mathematikbibliothek die Funktion sqrt, die die Quadratwurzel berechnet. Danach definieren wir 0 für den linken Rand und 1e10 für den rechten Rand, dh 10 Milliarden, basierend auf den in der Bedingung angegebenen Einschränkungen. Als nächstes suchen wir, wie bei einer typischen Bin-Suche, nach der Mitte, später vergleichen wir. Aber was ist interessant? Hier ist Mitte x in der Gleichung. In Anbetracht dessen bestimmen wir den Wert der Gleichung und vergleichen ihn mit der realen Antwort (d. H. C). Nun, wir verschieben die Grenzen, bis der Unterschied in den Grenzen kleiner oder gleich 10 Milliarden ist. Dies ist die Genauigkeit der Messung. Später multiplizieren wir mit einer Million, runden ab, übersetzen in int und reale Division durch dieselbe Million.

 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) 

Sehr einfache Herausforderung

Es gibt bereits eine Analyse für diese Aufgabe, daher werde ich nur den Code anhängen.

 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) 

Um das Material zu konsolidieren, können Sie hier Probleme lösen.