Enigme Pyramide de nombres @ Prise2Tete

schaff60 · #1

On voit souvent dans des magazines un petit casse-tête en forme de pyramide : il s'agit de trouver le chemin de haut en bas de la pyramide qui donne le total le plus élevé, à partir de chaque nombre on ne peut aller que vers l'un des deux immédiatement en dessous :

par exemple : 1
3 5
5 9 6
3 4 5 7
donnera comme maxi 1 + 5 + 9 + 5 = 20

Pour s'entraîner on peut avoir un peu plus compliqué :

Cela reste faisable en tâtonnant , les rois de la programmation vont pouvoir aussi tester le total de tous les chemins possibles (il n'y en a 'que' 2048) et en extraire le plus grand.

A ceux-là je leur propose donc de résoudre également la pyramide jointe en fichier texte pour l'importer plus facilement (attention les nombres devront être replacés sous forme de pyramide).
Pour trouver tous les chemins possibles il suffira de faire tourner son ordinateur quelques milliards d'années !

pyramide

EfCeBa · #2

Alors j'ai ça :
82
83 81
95 97 88
92 93 94 91
95 83 84 93 96
86 96 95 82 97 81
88 99 90 91 85 89 80
89 83 93 82 81 80 94 89
85 87 90 85 87 84 94 98 90
92 98 82 82 89 92 99 94 81 89
87 99 93 95 82 84 99 90 86 99 95
99 90 82 87 93 81 82 94 83 80 94 97

1115 (82+83+97+94+93+97+89+94+94+99+99+94)

Et sauf erreur 8869 pour le fichier.

Mais je dirais pas que j'ai utilisé mon algorithme de parcours de pyramide
développé pour Project Euler.
Il consiste à prendre les chiffres voisins du bas par deux et d'additionner le plus grand au chiffre commun du dessus et de répéter jusqu'en haut. De cette manière on fait taille_de_la_pyramide*(taille_de_la_pyramide+1)/2 calculs.

Si la pyramide a 100 lignes, on fait 5050 calculs ce qui est très peu et prends moins d'une seconde.

perceval · #3

je trouve 1115 au premier essai.
A voir si on peut ameliorer.

dhrm77 · #4

Que neni... il n'est nul besoin de trouver tous les chemins possibles. Si on commence par le bas, on élimine au fur et à mesure les chemins qui donnent la plus petite somme comparés à leurs voisins, et on trouve trés vite le chemin optimal.
Pour la pyramide que tu donnes, je trouve :
82+83+97+94+93+97+89+94+94+99+99+94=1115

Donc pour la grande pyramide que tu nous donnes, pas besoin de milliards d'années, il suffit d'une dizaine de minutes pour le programmer, et de moins d'une seconde pour que le programme trouve la solution...
Si je n'étais pas en route pour une compétition de rubik's cube aujourd'hui, je m'y attelerais.

Edit:
le chemin qui donne le plus de points nous donne 8869 points.
celui qui en donne le moins, nous donne 3440 points.

MthS-MlndN · #5

Une pyramide à 120 étages, ça fait [latex]2^{119} = 6,6 \times 10^{35}[/latex] chemins possibles... o_0' J'ai hâte de voir ce que les tarés de la prog ont fait

scarta · #6

Petit guide de la programmation facile:
pour chaque case de la pyramide, le nombre le plus grand qu'on peut former en passant par ce nombre est égal à ce nombre plus le max de ses deux "pères".
Le plus grand nombre final est le plus grand nombre que l'on trouve sur la dernière ligne.
Première pyramide = 1115
Pour la "grosse" pyramide= 8869

"Programmé" avec Excel, résolu en 1 milliard d'années * 10^-17.

PS: j'ai rien inventé, la méthode existait déjà il y a plus d'un demi siècle
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

schaff60 · #7

Bravo à tous,

effectivement l'algorithme est simple et se calcule très facilement dans excel.

Ce problème est l'un de nombreux problèmes du site du Projet Euler :

http://projecteuler.net/

Ce site contient principalement des défis mathématiques lancés aux programmeurs, mais certains problèmes sont abordables par les non-initiés comme moi, en n'utilisant que les fonctions d'un tableur, comme ce problème en est l'exemple.

scarta · #8

Il est super ce site de" project euler", je connaissais pas !
Le seul point négatif est qu'on ne peut pas rentrer trop de bonnes réponses par jour, du coup ça avance doucement, mais sinon il y a pas mal de problemes tres sympa !

shadock · #9

Projet Euler 67, résolu en 0.01 secondes :

Code:

from time import time

s=time()

triangle=open('p067_triangle.txt')

l=[]
for line in triangle:
    t=line.strip().split(' ')
    t=list(map(lambda x: int(x),t))
    l.append(t)
l.reverse()

while len(l)>1:
    currentline=l.pop(0)
    nextline=l[0]
    for i in range(len(nextline)):
        nextline[i]+=max(currentline[i],currentline[i+1])

print(l[0][0],time()-s)

Le triangle

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 27-02-2010 11:57:31

pyramide de nolbres

#0 Pub

#2 - 27-02-2010 14:06:45

Pyraide de nombres

#3 - 27-02-2010 14:21:29

Pyyramide de nombres

#4 - 27-02-2010 14:50:42

Pyramidee de nombres

#5 - 01-03-2010 13:56:17

Pyyramide de nombres

#6 - 01-03-2010 14:08:09

Pyramide de nombrse

#7 - 02-03-2010 19:37:30

pytamide de nombres

#8 - 07-03-2010 14:00:15

pyramode de nombres

#9 - 24-07-2015 19:02:22

pyramude de nombres

Code:

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums