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

  1. AtCoder Beginner Contest 145 C - Average Length image.png

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

  1. Additionnez les distances des deux combinaisons de points
  2. 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.


  1. AtCoder Beginner Contest 150 C - Count Order image.png

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

  1. Listez l'ordre de 1 à N avec itertools.permutations
  2. Comptez les nombres pour énumérer et enregistrer `` count_P``` et `count_Q``` où P et Q correspondent.
  3. 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

image.png

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

  1. 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.
  2. Créez une fonction `flag_queen_load ()` qui met à jour le tableau lorsqu'une reine est placée à une certaine coordonnée (r, c) .
  3. Après cela, essayez tous les emplacements pour déterminer s'ils peuvent être placés avec succès.
  4. 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
  5. 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```
  6. 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

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)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (024 --027 Recherche de priorité en profondeur)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (001 --004 Toutes les recherches: Toutes les énumérations)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
Résolution avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (053 --055 Méthode de planification dynamique: Autres)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (056 --059 Problème de l'itinéraire le plus court: méthode Dyxtra)
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 5/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 7/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 4/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 1/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 6/22]
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (005 --- 009 Toutes les recherches: Toutes les énumérations pour réduire le nombre de rues en concevant)
Résoudre avec Python [100 questions que les débutants et les intermédiaires devraient résoudre] (034-038 Méthode de planification dynamique: Knapsack DP basic)
Résolvez avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (039 --045 Méthode de planification dynamique: variante Knapsack DP)
Raisonnement causal et recherche causale par Python (pour les débutants)
1er test pratique d'algorithme Résoudre les questions passées avec python
Essayez de mettre en œuvre une recherche complète de la séquence qui apparaît souvent chez les pros de la concurrence avec python
Recherche de bits complète avec Python
2e test pratique de l'algorithme Résoudre les questions précédentes avec python (inachevé)
Résolvez les problèmes de somme partielle avec une recherche complète en Python
À propos de la recherche peu complète qui apparaît souvent chez les professionnels de la concurrence Aux yeux des débutants avec python
Rechercher et télécharger automatiquement des vidéos YouTube avec Python
Créons une application capable de rechercher des images similaires avec Python et Flask Part1
Créons une application capable de rechercher des images similaires avec Python et Flask Part2
[Pour les professionnels de la compétition débutants] J'ai essayé de résoudre 40 questions AOJ "ITP I" avec python
Résolvez des équations différentielles normales simultanées avec Python et SymPy.
Exploration avec Python et Twitter API 1 - Fonction de recherche simple