introduction

Cet article est le livre de Kenchon, qui contient de nombreuses explications sur la programmation compétitive, ** Entraînez vos compétences en résolution de problèmes! Algorithmes et structures de données（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

Sur cette page, nous présenterons le contenu du chapitre 2! Veuillez me pardonner s'il y a des bugs.

Consultez les pages suivantes pour obtenir des liens vers d'autres chapitres. [Table des matières] https://qiita.com/KevinST/items/002676619a583754bf76

code2.1 Montant de calcul de simple pour relevé

C'est un problème qui montre le montant du calcul pour une seule instruction for. J'ai également ajouté la sortie.

`code2-1.py`


#Recevoir N de l'entrée
N = int(input())
count = 0

for i in range(N):
    count += 1

#Résultat de sortie
print(count)

[Exemple d'entrée] 100 [Exemple de sortie] 100

Ce que l'on appelle $ O (N) $!

code2.2 Montant de calcul du double pour relevé

Cette fois, c'est le montant du calcul du double pour la déclaration

`code2-2.py`


N = int(input())
count = 0
for i in range(N):
    for j in range(N):
        count += 1
print(count)

[Exemple d'entrée] 100 [Exemple de sortie] 10000

Montant du calcul dit O $ (N ^ 2 $)!

code2.3 Énumération paire

`code2-3.py`


N = int(input())
for i in range(N, 1, -2):
    print(i)

[Exemple d'entrée] 10 [Exemple de sortie] 10 8 6 4 2

Le montant du calcul est de O $ (N) $.

code2.4 Toutes les listes de paires de points récentes

`code2-4.py`


def calc_dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

#Recevoir les données d'entrée
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

#Initialisez la valeur souhaitée avec une valeur suffisamment grande
minimum_dist = 10000000.0

#Commencer l'exploration
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)

[Exemple d'entrée] 4 1 1 2 2 12 66 18 31 [Exemple de sortie] 1.4142135623730951

Dans l'exemple ci-dessus, --La paire de points récents est (1,1) (2,2) --La distance est $ \ sqrt2 $ --Le montant du calcul est de O $ (N ^ 2) $ est.

Cliquez ici pour le chapitre 3 https://qiita.com/KevinST/items/4d04dc7369880670a63b

[Livre Kenchon à Python] -Chapitre 2- "Entraînez vos compétences en résolution de problèmes! Algorithmes et structures de données" J'ai réécrit le code posté en Python!

introduction

code2.1 Montant de calcul de simple pour relevé

code2-1.py