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 2 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 ein Problem, das den Rechenaufwand für eine einzelne for-Anweisung anzeigt. Ich habe auch die Ausgabe hinzugefügt.
code2-1.py
#N vom Eingang empfangen
N = int(input())
count = 0
for i in range(N):
count += 1
#Ausgabeergebnis
print(count)
[Eingabebeispiel] 100 [Ausgabebeispiel] 100
Sogenanntes $ O (N) $!
Diesmal ist es der Berechnungsbetrag für die doppelte for-Anweisung
code2-2.py
N = int(input())
count = 0
for i in range(N):
for j in range(N):
count += 1
print(count)
[Eingabebeispiel] 100 [Ausgabebeispiel] 10000
Sogenannter Berechnungsbetrag $ O (N ^ 2 $)!
code2-3.py
N = int(input())
for i in range(N, 1, -2):
print(i)
[Eingabebeispiel] 10 [Ausgabebeispiel] 10 8 6 4 2
Der Berechnungsbetrag beträgt $ O (N) $.
code2-4.py
def calc_dist(x1, y1, x2, y2):
return ((x1 - x2)**2 + (y1 - y2)**2)**0.5
#Eingangsdaten empfangen
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
x[i], y[i] = map(int, input().split())
#Initialisieren Sie den gewünschten Wert mit einem ausreichend großen Wert
minimum_dist = 10000000.0
#Beginnen Sie mit der Erkundung
for i in range(N):
for j in range(i+1, N):
dist_i_j = calc_dist(x[i], y[i], x[j], y[j])
if dist_i_j < minimum_dist:
minimum_dist = dist_i_j
print(minimum_dist)
[Eingabebeispiel] 4 1 1 2 2 12 66 18 31 [Ausgabebeispiel] 1.4142135623730951
Im obigen Beispiel ist
Klicken Sie hier für Kapitel 3 https://qiita.com/KevinST/items/4d04dc7369880670a63b
Recommended Posts