Dieser Artikel ist Kenchons Buch, das viele Erklärungen zur wettbewerbsfähigen Programmierung enthält. ** Trainieren Sie Ihre Fähigkeiten zur Problemlösung! Algorithmen und Datenstrukturen（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。
Auf dieser Seite stellen wir den Inhalt von Kapitel 3 vor! Bitte vergib mir, wenn es irgendwelche Fehler gibt.
Auf den folgenden Seiten finden Sie Links zu anderen Kapiteln. [Inhaltsverzeichnis] https://qiita.com/KevinST/items/002676619a583754bf76
Es ist derjenige, der "die Reihenfolge von vorne überprüfen"!
code3-1.py
#Eingaben empfangen
N, v = map(int, input().split())
a = list(map(int, input().split()))
#Lineare Suche
exist = False
for i in range(N):
if a[i] == v:
exist = True
#Ergebnisausgabe
if exist:
print("Yes")
else:
print("No")
[Eingabebeispiel] 5 1 2 3 4 1 11 [Ausgabebeispiel] Yes
Jetzt ist es Zeit, den Index zu erhalten.
code3-2.py
#Eingaben empfangen
N, v = map(int, input().split())
a = list(map(int, input().split()))
##Lineare Suche##
found_id = -1
for i in range(N):
if a[i] == v:
found_id = i
break
print(found_id)
[Eingabebeispiel] 4 2 0 2 -1 11 [Ausgabebeispiel] 1
Für die Nummer "2" a[0]: 0 a[1]: 2 ... Ich werde es suchen. Diesmal ist a [1] = 2, und die Zahl, nach der Sie hier gesucht haben, entspricht a [i]. Hier brechen und ausgeben.
code3-3.py
#Eingaben empfangen
N = int(input())
a = list(map(int, input().split()))
##Lineare Suche##
#Setzen Sie den Anfangswert des Minimalwerts auf "unendlich".
min_value = float("inf")
for i in range(N):
if a[i] < min_value:
min_value = a[i]
print(min_value)
[Eingabebeispiel] 4 0 2 -1 11 [Ausgabebeispiel] -1
Ich konnte den kleinsten Wert "-1" finden. Der Berechnungsbetrag beträgt $ O (N) $.
Wählen Sie ein Element aus Array a und ein Element aus Array b aus und fügen Sie sie hinzu, um eine Zahl zu erstellen. Wählen Sie unter diesen die mit K oder mehr und die kleinste.
code3-4.py
#Eingaben empfangen
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
#Lineare Suche
min_value = float("inf")
for i in range(N):
for j in range(N):
#Wenn die Summe kleiner als K ist, verwerfen Sie sie
if a[i] + b[j] < K:
continue
#Update mindestens
if a[i] + b[j] < min_value:
min_value = a[i] + b[j]
print(min_value)
[Eingabebeispiel] 4 10 1 2 5 6 7 12 16 22 [Ausgabebeispiel] 12
Es ist eine Vorbereitung für die sogenannte Bit-Vollsuche. Ich habe auch Ein- und Ausgänge hinzugefügt, um den Betrieb zu überprüfen.
code3-5.py
#Eingaben empfangen
i = int(input())
bit = int(input(), 2)
#Überprüfen Sie, ob die durch Bit dargestellte Teilmenge das i-te Element enthält
if bit & (1 << i):
print("Yes")
else:
print("No")
[Eingabebeispiel] 1 1010 [Ausgabebeispiel] Yes
Die vollständige Bit-Suche ist eine der vollständigen Suchmethoden und kann alle EIN / AUS-Muster auflisten. Einzelheiten finden Sie in Kencho-sans Buch und im Online-Kommentar.
Für diejenigen, die "Bi, Bit ... Nein, es ist schwierig> <" sagen, können Sie die Python-Funktion verwenden, um alle zu suchen, ohne über Bit nachzudenken. (Siehe "3.6 Ergänzung")
Es ist eine etwas vollständige Suche.
code3-6.py
#Eingaben empfangen
N, W = map(int, input().split())
a = list(map(int, input().split()))
#Bit ist 2^Bewegt sich durch n verschiedene Teilmengen
exist = False
for bit in range(2**N):
#Die Summe der in der Teilmenge enthaltenen Elemente
sum_val = 0
for i in range(N):
#i-tes Element a[i]Ist in der Teilmenge enthalten
if bit & (1 << i):
sum_val += a[i]
#sum_Ob val mit W übereinstimmt
if sum_val == W:
exist = True
if exist:
print("Yes")
else:
pritn("No")
[Eingabebeispiel] 4 10 1 9 100 200 [Ausgabebeispiel] Yes
Betrachten Sie die Teilmenge (1,9). Seine Summe ist 10, also passt es zu W. Die Antwort lautet also "Ja".
bisschen ist es schwer! Für diejenigen, die sagen, haben wir eine andere Version vorbereitet. Als Prozedur
Python ist gut! (Werbung)
code3-6-another_ver.py
from itertools import combinations
N, W = map(int, input().split())
a = list(map(int, input().split()))
exist = False
#Bestimmen Sie die Anzahl der abzurufenden Elemente (num_of_a): 0 bis N.
for num_of_a in range(N+1):
#Von a, alle num_of_Extrahieren Sie Elemente mit einer Extraktionsmethode und speichern Sie sie im variablen Muster
for pattern in combinations(a, num_of_a):
#Summe berechnen
sum_val = sum(list(pattern))
#sum_Ob val mit W übereinstimmt
if sum_val == W:
exist = True
if exist:
print("Yes")
else:
pritn("No")
[Eingabebeispiel] 4 10 1 9 100 200 [Ausgabebeispiel] Yes
Wenn Sie mehr über itertools erfahren möchten, kann die folgende Seite hilfreich sein. Wenn Sie es lesen, werden Sie von der Bequemlichkeit der Python-Standardbibliothek beeindruckt sein! Wow, itertools
Klicken Sie hier für Kapitel 4 https://qiita.com/KevinST/items/f846d57e56242c6e1293
Recommended Posts