Discussion :

[Jolimousi]

Bonjour,

Ce problème a pour thème la suite de Syracuse ...
https://projecteuler.net/

Il faut trouver l'entier inférieur à 10 puissance 12 (!) qui a la plus grande durée de vol...

Je débute en Python (et en n'importe quel langage d'ailleurs...) et j'ai écrit un script simple qui devrait résoudre le problème...sauf que d'après mes estimations mon programme devrait tourner environ 1 an avant de donner la réponse !

Je n'ai aucune idée de ce qu'il faut faire pour aller plus vite....


Pouvez vous me suggérer des pistes ?

Merci d'avance....

Ps dans le code ci-dessous je limite la recherche à 10 puissance 6 et mon programme met environ 30 s pour répondre.
[837799, 525, 2974984576]
30.2937331199646
837799 est le nombre cherché, la suite comprend 525 termes et "monte" jusqu'à 2974984576 (ceci n'est pas demandé dans le projet Euler...)

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from time import time
debut=time()
def compte_syracuse(n) :
    a=1
    nb=n
    altitude=nb
    trio=[]
    while nb != 1 :
        if nb%2 == 0 :
            nb=nb//2
        else :
            nb=3*nb+1
        a=a+1
        if altitude<nb :
            altitude=nb
 
    trio=[n,a,altitude]
 
    return trio
resultat=[1,1,1]
 
for i in range(2,1000000):
    provisoire=compte_syracuse(i)
    if provisoire[1]>resultat[1] :
        resultat=provisoire
print(resultat)
fin= time()
print(fin -debut)

[dourouc05]

Les solutions que j'avais écrites (Mathematica et MATLAB), il y a quelques années, utilisaient cette approche par force brute (méthode extrêmement fine ).

Maintenant, à y réfléchir, une approche par mémoisation/programmation dynamique devrait bien fonctionner : une fois que tu as calculé une chaîne (par exemple, pour 13 : 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1), tu peux réutiliser cette longueur par la suite (10). L'idée est donc d'avoir une association entre un nombre (le premier de la chaîne) et la longueur de la chaîne correspondante ; tu appliques la règle, tu regardes la longueur pour le nombre obtenu dans la correspondance, tu ajoutes une unité, tu stockes ; si le nombre obtenu n'y est pas, tu le calcules de la même manière.

Pour arriver à cette solution, ma méthodologie est de rechercher les calculs que tu fais plusieurs fois et de stocker ce résultat intermédiaire. Ça fonctionne souvent très bien pour ce genre de problèmes. Maintenant, je n'ai pas encore implémenté cette solution .

[dourouc05]

Juste un mot pour dire que je viens d'implémenter ma solution avec MATLAB (du récursif avec MATLAB, il faut vraiment le vouloir/être fou…). Exemples de temps de calcul d'une seule valeur :

Code matlab :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
>> tic; lengthTo(159); toc % Sans mémoïsation. 
Elapsed time is 0.206836 seconds.
>> tic; lengthTo(159); toc % Cache vide. 
Elapsed time is 0.010389 seconds.
>> tic; lengthTo(159); toc % Vecteur de mémoïsationdéjà rempli. 
Elapsed time is 0.000065 seconds.

Ce que je n'avais pas vu, c'est que, pour avoir un vecteur suffisamment grand (pour toutes les valeurs considérées), il faut énormément de mémoire, dont une grande partie est remplie de zéros : comme toujours, troquer du temps pour de la mémoire… Passer à une représentation creuse (omettre les zéros) n'aide pas beaucoup, ce petit script explose déjà les huit gigaoctets disponibles sur ma machine. Ne stocker que le premier million d'éléments rend le code affreusement compliqué.

Meilleure solution : une table de hachage, en Python, y ajouter toute valeur calculée. Bien plus rapide qu'avec MATLAB, en utilisant nettement moins de mémoire. Je suppose que le problème vient de la représentation des nombres et de la matrice creuse (soixante-quatre bits pour un nombre en virgule flottante, au moins, puis les métadonnées requises par la matrice creuse pour au moins un million d'éléments, ça fait nettement plus qu'une table de hachage où la clé et la valeur sont entières).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Solution found: number 837799, with a length of 525.
The process took 3.464427947998047 s.

Si tu n'y arrives pas, je peux te fournir mon code.

[Jolimousi]

Merci en tout cas de m'aider...
Tes messages me permettent d'y voir un peu plus clair, mais je dois y réfléchir...

Cordialement