Discussion :

[Rookie5]

Bonjour,

Je dois résoudre le problème suivant :

"Les nombres pentagonaux obéissent à la formule Pn=n(3n-1)/2. Les dix premiers nombres pentagonaux sont :

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

On peut voir que P4 + P7 = 22 + 70 = 92 = P8. Cependant, leur différence, 70 - 22 = 48, n'est pas pentagonale.

Trouver les deux nombres pentagonaux Pj et Pk, dont la somme et la différence sont pentagonales, et dont D = |Pk - Pj| est minimisée. Donner la valeur de D."

Code :

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

1
2
3
4
5
6
7
8
9
10
11
L = [ ]
def abc():
    for n in range(1, 10000):
        L.append(n * (3*n-1) / 2)
    for i in range(1, 9999):
        for j in range(1, 9999):
            for k in range(1, 9999):
                if abs(L[i] - L[j]) == L[k]:
                    for l in range(1, 9999):
                        if L[i] + L[j] == L[l]:
                            return L[i] - L[j]

Or actuellement et après deux jours de réflexion, je ne parviens pas à trouver une solution, je pense que celle ci-dessus, en soit, pourrait fonctionner, mais elle demande beaucoup trop de temps. Pourriez-vous me donner une piste pour un programme plus court et plus rapide s'il-vous-plaît ? Merci !

[VinsS]

Salut,

Tu es sure de ton coup ? avec ceci je n'obtiens aucun résultat.

Code :

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

1
2
3
4
5
6
 
>>> l = [n * (3*n-1) / 2 for n in range(1, 1000)]
>>> for i in l:
...     for j in l:
...             if i + j in l and j - i in l:
...                     print(" %s et %s donnent %s et %s" % (i, j, i+j, j-i))

J'ai essayé avec 10000 mais je l'ai interrompu après 12 minutes sans aucun résultat non plus.

[wiztricks]

Salut,

Ce code va assez vite:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
N = 10000
L = [ n * (3*n - 1) // 2 for n in range(1, N) ]
X = set(L)
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i] + L[j]
        if a in X:
            if L[j] - L[i] in X:
                print ('***', L[i], L[j], L[i] + L[j])
        elif a > L[-1]:
            break

et sort:

Code :

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

*** 1560090 7042750 8602840

Après pour aller plus loin, c'est compliqué (et intuitivement, j'ai l'impression qu'il n'y a pas tant de solutions).

- W

[Rookie5]

Salut,

Tu es sure de ton coup ? avec ceci je n'obtiens aucun résultat.
Code :

Code :

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

1
2
3
4
5
>>> l = [n * (3*n-1) / 2 for n in range(1, 1000)]
>>> for i in l:
...     for j in l:
...             if i + j in l and j - i in l:
...                     print(" %s et %s donnent %s et %s" % (i, j, i+j, j-i))

J'ai essayé avec 10000 mais je l'ai interrompu après 12 minutes sans aucun résultat non plus.

Non justement, comme cela ne donne pas de résultat, je pense que mon code est faux, et le nombre de boucles dans des boucles ne doit pas aider non plus

Salut,

Ce code va assez vite:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
N = 10000
L = [ n * (3*n - 1) // 2 for n in range(1, N) ]
X = set(L)
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i] + L[j]
        if a in X:
            if L[j] - L[i] in X:
                print ('***', L[i], L[j], L[i] + L[j])
        elif a > L[-1]:
            break

et sort:

Code :

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

*** 1560090 7042750 8602840

Après pour aller plus loin, c'est compliqué (et intuitivement, j'ai l'impression qu'il n'y a pas tant de solutions).

- W

Je pense que c'est déjà largement suffisant, surtout niveau rapidité, merci beaucoup !

[marco056]

Salut,

Ce code va assez vite:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
N = 10000
L = [ n * (3*n - 1) // 2 for n in range(1, N) ]
X = set(L)
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        a = L[i] + L[j]
        if a in X:
            if L[j] - L[i] in X:
                print ('***', L[i], L[j], L[i] + L[j])
        elif a > L[-1]:
            break

et sort:

Code :

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

*** 1560090 7042750 8602840

Après pour aller plus loin, c'est compliqué (et intuitivement, j'ai l'impression qu'il n'y a pas tant de solutions).

- W

Bonjour,
J'ai fait un code assez ressemblant mais en 2 fois.
Je n'ai pas utilisé d'ensemble set : par curiosité, quel est l'intérêt ? Est-ce plus rapide car non indexable ?

[wiztricks]

Est-ce plus rapide car non indexable ?

Si on écrit "a in L" avec L liste, en dessous çà fera des itérations genre:

Code :

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

1
2
3
for k in range(len(L)):
     if a == L[k]:
        break

ce qui est assez bourrin car on balaie toute la liste du premier au dernier élément (si on ne trouve pas rapidement).
Une recherche par dichotomie serait meilleure mais le hashage est encore meilleur et, en plus, il n'y a pas grand chose à coder.

- W

[marco056]

Ok, merci.