Résoudre avec Python [100 anciennes questions sélectionnées que les débutants et les intermédiaires devraient résoudre] (015 --017 Recherche complète: Recherche complète en avant)
1. Objet
Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.
Cet article s'intitule "015 --017 Recherche complète: Recherche complète en avant".
2. Résumé
Dans de nombreux cas, il peut être résolu en utilisant bien itertools pour les problèmes séquentiels.
permutaionsQuandcombinationQuandproductJe l'utilise beaucoup, j'ai donc appris ce domaine en essayant divers exemples de données.
3. Histoire principale
015 --017 Recherche complète: recherche avant complète
Répondre
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)Puis
# answer = total_distance * (factor * (N - 1) / count) /Cela devient un facteur et la formule peut être transformée comme suit
answer = total_distance * ((N - 1) / count)
print(answer)
Il existe différentes méthodes de calcul ici. Pour être honnête, j'énumère tous les arrangements avec `` permutation '', je trouve la distance en tout, et je prends la moyenne. Je pense que cela fonctionnera toujours, mais je l'ai essayé comme réponse avec un peu moins de calcul. La politique est
- Additionnez les distances des deux combinaisons de points
- La réponse est cette somme multipliée par `` (N -1) / nombre de combinaisons ''.
est Le 2 ci-dessus est dérivé de la transformation d'expression laissée en commentaire dans le code.
Répondre
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)
Croyez que les itertools.permutations de python les listeront dans l'ordre lexical (!) Je vais l'écrire honnêtement.
La politique est
- Listez l'ordre de 1 à N avec
itertools.permutations - Comptez les nombres pour énumérer et enregistrer ``
count_P``` et`count_Q``` où P et Q correspondent. - La réponse est la différence entre les deux
est.
itertoolsSi vous n'en avez pas, vous devrez réfléchir un peu plus, mais c'est pratique, alors je l'ai utilisé sans réfléchir.
017. ALDS_13_A-8 Queen Problem
Répondre
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 #droite
if 0 <= c-i and c-i < 8:
grid[r][c-i] = -1 #la gauche
if 0 <= r+i and r+i < 8:
grid[r+i][c] = -1 #en dessous de
if 0 <= r-i and r-i < 8:
grid[r-i][c] = -1 #Vers le haut
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 #En haut à droite
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 #En bas à droite
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 #En bas à gauche
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 #en haut à gauche
grid[r][c] = 9 #moi même
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~Essayez le numéro 7 à travers la séquence
#Pour la séquence générée, considérez l'indice comme le numéro de ligne et l'élément comme le numéro de colonne.
for perm in itertools.permutations(range(8)):
copy_grid = copy.deepcopy(grid) #Utilisez une nouvelle grille à chaque fois
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-casse si tu mets k reines
break
#Affichage des réponses
for row in range(8):
for col in range(8):
if copy_grid[row][col] == -1:
print('.', end='')
else:
print('Q', end='')
print()
À l'origine, je l'ai écrit dans Numpy, mais AOJ ne peut-il pas utiliser Numpy? Je n'ai pas pu le soumettre en raison d'une erreur, je l'ai donc réécrit avec une liste normale. La politique est
- Tout d'abord, réglez l'échiquier sur `` grille '', définissez la position où se trouve la reine sur 9, la partie où la reine peut attaquer est -1 et les autres parties vierges sont 0.
- Créez une fonction
`flag_queen_load ()`qui met à jour le tableau lorsqu'une reine est placée à une certaine coordonnée - Après cela, essayez tous les emplacements pour déterminer s'ils peuvent être placés avec succès.
- En essayant toutes les méthodes, listez les colonnes d'ordre de 0 à 7 avec ```itertools.permutations (range (8)) `` `, et considérez les colonnes d'ordre générées comme des numéros de ligne pour les indices et des numéros de colonne pour les éléments. Masu
- Après cela, si le tableau est -1, il ne peut pas être placé, donc ``
break```, et s'il est 9, c'est OK, donc`continue``` - La réponse est quand vous pouvez placer une nouvelle reine `` 8-k``` fois
est.
La fonction `` flag_queen_load () '' est sale, donc j'aurais dû l'écrire un peu plus propre.
Recommended Posts