[Python] ABC133B (problème du triangle supérieur droit) [At Coder]

Un endroit où les débutants du programme risquent de trébucher. Double boucle sans duplication. Je définis arbitrairement ce type de problème comme le «problème du triangle rectangle supérieur» w

ABC133B Difficulty:137 Il est difficile de comprendre le problème s'il y a un indice ... Pour le moment, je ne peux pas l'imaginer même si ça s'appelle D dimension, donc je l'imagine en 2 dimensions. En bref ① Calculez toutes les combinaisons de distances entre deux points différents ② Si chaque distance est un entier Si vous cherchez k

① Calculez toutes les combinaisons de distances entre deux points différents

Si vous codez la recherche complète du triangle supérieur droit (5 lignes * 5 colonnes), cela ressemble à ceci

test.py

for i in range(5):
    for j in range(i+1,5):
        #Calcul de distance

i est la 0ème ligne (ligne A), 1ère ligne (ligne B), 2ème ligne (ligne C), 3ème ligne (ligne D), 4ème ligne (ligne E) Lorsque i est 0, j est «range (1,5)» → «1,2,3,4» Lorsque i vaut 1, j est «range (2,5)» → «2,3,4» Quand i est 2, j est range (3,5) → 3,4 Quand i est 3, j est range (4,5) → 4 Quand i vaut 4, j est range (5,5) → none, donc rien n'est traité. ⇨ Fermement ** Vous pouvez rechercher les 10 endroits (4 + 3 + 2 + 1 + 0) du triangle en haut à droite (partie jaune!) **!

Si vous pouvez comprendre cela, quel que soit le problème du triangle rectangle supérieur, "Je n'ai plus peur de rien"

② Si chaque distance est un entier

C'est facile. %1==0 or is_integer Je pense que peu importe lequel. Je ne suis pas bon en anglais, alors j'utilise l'ancien.

①＋② En résumé, ça ressemble à ça

test.py

def LI(): return list(map(int,input().split()))
N,D = LI()
X = [LI() for _ in range(N)]
_ans = 0
for i in range(N):
    for j in range(i+1,N):
        temp = 0
        for k in range(D):
            temp += (X[j][k]-X[i][k])**2
        if temp**0.5%1==0:
            _ans += 1
print(_ans)

Je pense que l'endroit où temp = 0 est décrit deviendra intuitif si vous gérez le nombre de problèmes. La formule de la distance entre les deux points est de se souvenir des mathématiques du premier cycle du secondaire!

Sujet similaire (problème de triple boucle sans duplication du problème de triangle rectangle supérieur)

Je pense que cela approfondira votre compréhension. Nombre de combinaisons AOJ (ITP1_7_B)

Comme ça ~

test.py

def LI(): return list(map(int,input().split()))
while 1:
    n,x = LI()
    if n==x==0:
        break
    _ans = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if i+j+k==x:
                    _ans += 1
    print(_ans)

Ce n'est pas le sujet principal de cet article, mais si vous parlez des extras, k = x-i-j (condition de k: 1 <= k <= n et j <k) En le définissant, vous pouvez le résoudre avec une instruction double for! !! !!

** (Ajouté le 07/05/2020) ** Actuellement, le problème du triple ci-dessus pour la déclaration Écrivez du code en utilisant ʻitertools.combinations`! Cliquez ici pour plus de détails! [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part1 / 22]

** (Ajouté le 26 mai 2020) **

• Supplément Dans la figure ci-dessus

• Recherche complète du triangle supérieur droit
  • itertools.combinations(range(N),2)
• Recherche complète du triangle supérieur droit + zone ombrée
  • itertools.combinations_with_replacement(range(N),2)

Ce sera. ʻItertools.combinations_with_replacement` est une combinaison en double! !! !!

fin!