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 4! 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
Récurrence de base.
code4-1.py
def func(N):
if N == 0:
return 0
return N + func(n-1)
Puisque seule la partie fonction est créée, il n'y a pas d'entrée / sortie.
Ceci est un exemple d'utilisation de code4.1 (N = 5)
code4-2.py
#python a une récurrence limitée (1000 fois, etc., selon l'environnement)
#Changez-le en une valeur suffisamment grande (10 à la 9e puissance cette fois)
import sys
sys.setrecursionlimit(10**9)
def func(N):
#Signaler que vous avez appelé une fonction récursive
print("func({})Appelé".format(N))
#Cas de base
if N == 0:
return 0
#Si ce n'est pas le cas de base, demandez récursivement une réponse
result = N + func(N-1)
print("{}Somme jusqu'à= {}".format(N, result))
return result
func(5)
[Exemple de sortie] Appelé func (5) Appelé func (4) Appelé func (3) Appelé func (2) Appelé func (1) Appelé func (0) Somme jusqu'à 1 = 1 Somme jusqu'à 2 = 3 Somme jusqu'à 3 = 6 Somme jusqu'à 4 = 10 Somme jusqu'à 5 = 15
En tant que méthode, nous augmentons le nombre de limites supérieures récursives. En Python, la limite supérieure récursive est souvent fixée à environ 1000 fois par défaut, donc Je pense qu'il serait bon de le changer lors de l'utilisation de la récurrence chez les pros de la compétition. (Pas nécessaire dans ce cas, mais juste au cas où)
code4-3.py
#Danger! Veuillez le faire à vos risques et périls
def func(N):
if N == 0:
return 0
return N + func(N+1)
Il n'y a aucun doute sur TLE.
C'est une méthode de division mutuelle euclidienne familière.
** Q: Quel est l'engagement maximum pour 51 et 15 ans? ** **
Écrivons-le avec une fonction récursive.
code4-4.py
def GCD(m, n):
#Cas de base
if n == 0:
return m
#Appel récursif
return GCD(n, m % n)
print(GCD(51, 15)) #3 est la sortie
print(GCD(15, 51)) #3 est la sortie
[Exemple de sortie] 3 3
En passant, le montant du calcul est de $ O (log (n)) $. GCD est rapide! !! !! !!
Ceci est également familier. 1 1 2 3 5 8 13 21 34 ...
code4-5.py
def fibo(N):
#Cas de base
if N == 0:
return 0
elif N == 1:
return 1
#Appel récursif
return fibo(N-1) + fibo(N-2)
print(fibo(5))
[Exemple de sortie] 5
Bien que ce ne soit pas dans l'original, j'ai également ajouté une sortie pour vérifier l'opération. Vérifions l'opération détaillée avec le code 4.6 suivant.
Ceci est un exemple d'utilisation concret de code4.5. Une sortie est incluse afin que vous puissiez vérifier l'état interne.
code4-6.py
def fibo(N):
#Signaler que vous avez appelé une fonction récursive
print("fibo({})Appelé".format(N))
#Cas de base
if N == 0:
return 0
elif N == 1:
return 1
#Rechercher et générer des réponses de manière récursive
result = fibo(N-1) + fibo(N-2)
print("{}article= {}".format(N, result))
return result
fibo(6)
[Exemple de sortie] Appelé fibo (6) Appelé fibo (5) Appelé fibo (4) Appelé fibo (3) Appelé fibo (2) Appelé fibo (1) Appelé fibo (0) 2 éléments = 1 Appelé fibo (1) 3 éléments = 2 Appelé fibo (2) Appelé fibo (1) Appelé fibo (0) 2 éléments = 1 4 éléments = 3 Appelé fibo (3) Appelé fibo (2) Appelé fibo (1) Appelé fibo (0) 2 éléments = 1 Appelé fibo (1) 3 éléments = 2 5 éléments = 5 Appelé fibo (4) Appelé fibo (3) Appelé fibo (2) Appelé fibo (1) Appelé fibo (0) 2 éléments = 1 Appelé fibo (1) 3 éléments = 2 Appelé fibo (2) Appelé fibo (1) Appelé fibo (0) 2 éléments = 1 4 éléments = 3 6 éléments = 8
Malgré le nombre relativement petit de N = 6, il existe de nombreux appels de fonction. Le code suivant (code4.8) tente d'améliorer cela.
C'est une tentative de voir ce qui se passe si nous laissons la récurrence une fois et l'implémentons avec une instruction for et un tableau.
code4-7.py
F = [None] * 50
F[0], F[1] = 0, 1
for N in range(2, 50):
F[N] = F[N-1] + F[N-2]
print("{}article: {}".format(N, F[N]))
[Exemple de sortie] 2 éléments: 1 3 éléments: 2 4 éléments: 3 5 éléments: 5 6 éléments: 8 7 éléments: 13 8 éléments: 21 9 objets: 34 10 éléments: 55 11 éléments: 89 12 éléments: 144 13 éléments: 233 14 éléments: 377 15 éléments: 610 16 éléments: 987 17 éléments: 1597 18 éléments: 2584 19 éléments: 4181 20 éléments: 6765 21 éléments: 10946 22 éléments: 17711 23 produits: 28657 24 produits: 46368 25 éléments: 75025 26 éléments: 121393 27 éléments: 196418 28 éléments: 317811 29 éléments: 514229 30 éléments: 832040 31 éléments: 1346269 32 éléments: 2178309 33 éléments: 3524578 34 éléments: 5702887 35 éléments: 9227465 36 éléments: 14930352 37 éléments: 24157817 38 éléments: 39088169 39 éléments: 63245986 40 éléments: 102334155 41 éléments: 165580141 42 éléments: 267914296 43 éléments: 433494437 44 éléments: 701408733 45 éléments: 1134903170 46 éléments: 1836311903 47 éléments: 2971215073 48 éléments: 4807526976 49 éléments: 7778742049
Il peut être implémenté avec un montant de calcul de $ O (N) $.
Si vous utilisez bien les tableaux, vous pouvez ignorer les mêmes calculs et accélérer votre programme. Incorporons cela dans la récurrence (= mémo).
code4-8.py
#fibo[N]Un tableau pour noter le résultat de
memo = [-1] * 50
def fibo(N):
#Cas de base
if N == 0:
return 0
elif N == 1:
return 1
#Vérifier les notes
if memo[N] != -1:
return memo[N]
#Appel récursif en notant la réponse
memo[N] = fibo(N-1) + fibo(N-2)
return memo[N]
fibo(49)
for N in range(2, 50):
print("{}article: {}".format(N, memo[N]))
[Exemple de sortie] 2 éléments: 1 3 éléments: 2 4 éléments: 3 5 éléments: 5 6 éléments: 8 7 éléments: 13 8 éléments: 21 9 objets: 34 10 éléments: 55 11 éléments: 89 12 éléments: 144 13 éléments: 233 14 éléments: 377 15 éléments: 610 16 éléments: 987 17 éléments: 1597 18 éléments: 2584 19 éléments: 4181 20 éléments: 6765 21 éléments: 10946 22 éléments: 17711 23 produits: 28657 24 produits: 46368 25 éléments: 75025 26 éléments: 121393 27 éléments: 196418 28 éléments: 317811 29 éléments: 514229 30 éléments: 832040 31 éléments: 1346269 32 éléments: 2178309 33 éléments: 3524578 34 éléments: 5702887 35 éléments: 9227465 36 éléments: 14930352 37 éléments: 24157817 38 éléments: 39088169 39 éléments: 63245986 40 éléments: 102334155 41 éléments: 165580141 42 éléments: 267914296 43 éléments: 433494437 44 éléments: 701408733 45 éléments: 1134903170 46 éléments: 1836311903 47 éléments: 2971215073 48 éléments: 4807526976 49 éléments: 7778742049
Cela pourrait également être mis en œuvre avec le montant du calcul $ O (N) $.
Résolvez le même problème que le code 3.6 dans le chapitre précédent en utilisant une fonction récursive. Oubliez les mémos une fois et implémentez-les avec un simple récursif.
code4-9.py
def func(i, w, a):
#Cas de base
if i == 0:
if w == 0:
return True
else:
return False
#a[i-1]Si tu ne choisis pas
if func(i-1, w, a):
return True
#a[i-1]Lors du choix
if func(i-1, w-a[i-1], a):
return True
#Si les deux sont faux
return False
N, W = map(int, input().split())
a = list(map(int, input().split()))
if func(N, W, a):
print("Yes")
else:
print("No")
【Exemple d'entrée】 4 10 1 9 100 200 [Exemple de sortie] Yes
Ce code est un montant de calcul $ O (2 ^ N) $. (Voir le livre de Kenchon pour plus de détails)
Si vous êtes intéressé, notons-le aussi! (Problème de fin de chapitre 4.6)
Cliquez ici pour le chapitre 5 (Ajouter dès qu'il est terminé)
Recommended Posts