Lösen Sie mit Python [100 ausgewählte Fragen aus der Vergangenheit, die Anfänger und Fortgeschrittene lösen sollten] (015 --017 Vollständige Suche: Vollständige Suche weiterleiten)
1. Zweck
Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.
Dieser Artikel ist "015 --017 Vollständige Suche: Vollständige Suche weiterleiten".
2. Zusammenfassung
In vielen Fällen kann es gelöst werden, indem `` `itertoolsgut für sequentielle Probleme verwendet wird.permutaionsWanncombinationWannproduct```Ich benutze es sehr oft, deshalb habe ich diesen Bereich durch Ausprobieren verschiedener Beispieldaten gelernt.
3. Hauptgeschichte
015 --017 Vollständige Suche: Vollständige Suche weiterleiten
Antworten
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]
total_distance = 0
count = 0
for start in range(N-1):
for end in range(start+1, N):
start_x, start_y = towns[start]
end_x, end_y = towns[end]
total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
count += 1
# factor = math.factorial(N)Dann
# answer = total_distance * (factor * (N - 1) / count) /Es wird ein Faktor und die Formel kann wie folgt transformiert werden
answer = total_distance * ((N - 1) / count)
print(answer)
Hier gibt es verschiedene Berechnungsmethoden. Um ehrlich zu sein, zähle ich alle Arrangements mit "Permutation" auf, finde die Entfernung in allen und nehme den Durchschnitt. Ich denke, das wird immer noch funktionieren, aber ich habe es als Antwort mit etwas weniger Berechnung versucht. Die Politik ist
- Summieren Sie die Abstände aller beiden Punktkombinationen
- Die Antwort ist diese Summe multipliziert mit "(N -1) / Anzahl der Kombinationen".
ist Die obigen 2 werden von der Ausdruckstransformation abgeleitet, die als Kommentar im Code hinterlassen wurde.
Antworten
import itertools
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
count = 1
for p in itertools.permutations(range(1, N+1)):
if p == P:
count_P = count
if p == Q:
count_Q = count
count += 1
ans = abs(count_P - count_Q)
print(ans)
Glauben Sie, dass Pythons `` `itertools.permutations``` sie in lexikalischer Reihenfolge auflistet (!) Die Politik ist
- Listen Sie die Reihenfolge von 1 bis N mit `` `itertools.permutations``` auf
- Zählen Sie die zu zählenden Zählungen und zeichnen Sie
`count_P``` und`count_Q``` auf, wobei P und Q übereinstimmen. - Die Antwort ist der Unterschied zwischen den beiden
ist.
itertoolsWenn du keine hast, musst du ein bisschen mehr nachdenken, aber es ist praktisch, also habe ich es benutzt, ohne nachzudenken.
017. ALDS_13_A-8 Queen Problem
Antworten
import itertools
import copy
def flag_queen_load(grid, r, c):
for i in range(1, 8):
if 0 <= c+i and c+i < 8:
grid[r][c+i] = -1 #richtig
if 0 <= c-i and c-i < 8:
grid[r][c-i] = -1 #links
if 0 <= r+i and r+i < 8:
grid[r+i][c] = -1 #unter
if 0 <= r-i and r-i < 8:
grid[r-i][c] = -1 #Oben
if 0 <= r-i and r-i < 8 and 0 <= c+i and c+i < 8:
if grid[r-i][c+i] == 9:
continue
grid[r-i][c+i] = -1 #Oben rechts
if 0 <= r+i and r+i < 8 and 0 <= c+i and c+i < 8:
if grid[r+i][c+i] == 9:
continue
grid[r+i][c+i] = -1 #Rechts unten
if 0 <= r+i and r+i < 8 and 0 <= c-i and c-i < 8:
if grid[r+i][c-i] == 9:
continue
grid[r+i][c-i] = -1 #Unten links
if 0 <= r-i and r-i < 8 and 0 <= c-i and c-i < 8:
if grid[r-i][c-i] == 9:
continue
grid[r-i][c-i] = -1 #Oben links
grid[r][c] = 9 #mich selber
return grid
if __name__ == "__main__":
k = int(input())
grid = [[0] * 8 for _ in range(8)]
for _ in range(k):
r, c = map(int, input().split())
grid = flag_queen_load(grid, r, c)
# 0~Versuchen Sie die Nummer 7 durch die Sequenz
#Betrachten Sie für die generierten sequentiellen Spalten den Index als Zeilennummer und das Element als Spaltennummer.
for perm in itertools.permutations(range(8)):
copy_grid = copy.deepcopy(grid) #Verwenden Sie jedes Mal ein neues Raster
count = 0
for row, col in enumerate(perm):
if copy_grid[row][col] == -1:
break
if copy_grid[row][col] == 9:
continue
copy_grid[row][col] = 9
copy_grid = flag_queen_load(copy_grid, row, col)
count += 1
if count == 8 - k: # 8-brechen Sie, wenn Sie k Königinnen setzen
break
#Antwortanzeige
for row in range(8):
for col in range(8):
if copy_grid[row][col] == -1:
print('.', end='')
else:
print('Q', end='')
print()
Ursprünglich habe ich es in Numpy geschrieben, aber kann AOJ Numpy nicht verwenden? Ich konnte es aufgrund eines Fehlers nicht einreichen, daher habe ich es mit einer normalen Liste umgeschrieben. Die Politik ist
- Setzen Sie zuerst das Schachbrett auf "Gitter", setzen Sie die Position, an der sich die Königin befindet, auf 9, der Teil, an dem die Königin angreifen kann, ist -1 und die anderen leeren Teile sind 0.
- Erstellen Sie eine Funktion
`flag_queen_load ()`, die das Board aktualisiert, wenn eine Königin an einer bestimmten Koordinate platziert wird - Versuchen Sie anschließend alle Platzierungen, um festzustellen, ob sie erfolgreich platziert werden können.
- Wenn Sie alle Möglichkeiten ausprobieren, listen Sie die Ordnungsspalten von 0 bis 7 mit ``
itertools.permutations (range (8))`auf und stellen Sie sich die generierten Ordnungsspalten als Zeilennummern für Indizes und Spaltennummern für Elemente vor. Masu - Wenn das Board danach -1 ist, kann es nicht platziert werden, also
break```, und wenn es 9 ist, ist es OK, also`continue``` - Die Antwort ist, wenn Sie eine neue Königin `` `8-k``` mal platzieren können
ist.
Die Funktion `flag_queen_load ()` ist schmutzig, also hätte ich sie etwas sauberer schreiben sollen.
Recommended Posts