Minimiser les Zéros Finaux dans une Grille avec Programmation Dynamique
Piège Courant
Une erreur fréquente est de minimiser simultanément les facteurs 2 et 5 durant le parcours. Considérons cette grille :
2
1 125
10 8
Un chemin minimisant le minimum des deux facteurs produirait 3 zéros finaux, tanddis que la solution optimale n'en a que 2.
Solution Optimale
Définissons deux matrices DP :
dp_deux[i][j] : somme min ...
Publié le 29 juillet à 16h03
Calcul de la somme des valeurs de φ pour une séquence d'entiers
Énoncé du problème
Soit une fonction f définie pour tout entier positif n vérifiant :
∑d|n f(d) = n
Étant donnés n entiers a1, a2, …, an, calculer ∑i=1n f(ai).
Méthode de résolution
La fonction f n'est autre que l'indicatrice d'Euler φ. Elle possède les propriétés suivantes :
Si q = nm avec n et m premiers entre eux, alors f(q) = f(n) × f(m).
...
Publié le 21 juin à 06h22