RSS Feed
Precedenta

Problema 67

09 Aprilie 2004

Suma maximă a căii II


Începând din vârful triunghiului de mai jos și mergând la numerele adiacente de pe rândul inferior, suma maximă a numerelor prin care trecem din vârf până la bază e 23.

3
7 4
2 4 6
8 5 9 3

Adică 3 + 7 + 4 + 9 = 23.

Găsește suma maximă din varf până la bază în triangle.txt (click dreapta și 'Save Link/Target As...'), un fișier text de 15K care conține un triunghi cu 100 de rânduri.

NOTĂ: Aceasta e o versiune mult mai dificilă a Problemei 18. Nu e posibilă încercarea fiecarei rute pentru a rezolva această problemă, deoarece sunt 299 rute in total ! Dacă ai putea încerca 1 trilion (1012) de rute în fiecare secundă, ar dura peste 20 de miliarde de ani pentru a le încerca pe toate. Există un algoritm eficient de rezolvare. ;o)


Tag-uri:

>> Vezi problema originală <<