problema de combinatorica sau teoria grafurilor?!

Rezolvarea problemelor de matematica prin realizarea unor programe.
Cruel
utilizator
utilizator
Mesaje: 1
Membru din: 07 Apr 2015, 11:36
Localitate: Romania

problema de combinatorica sau teoria grafurilor?!

Mesaj de Cruel » 07 Apr 2015, 12:01

Salut,

problema suna in felul urmator:
O broasca sta pe piatra nr. 1. El vrea sa visiteze fiecare piatra exact odata, in final ajungand pe piatra n. Broasca poate sari de pe o piatra pe alta daca se respecta urmatoarea conditie: piatra poate fi la 3 unitati distanta. In alte cuvinte, de pe piatra i, poate ajunge pe piatra j daca 1<=j<=n si j este in setul {i-3,i-2,i-1,i+1,i+2,i+3}

sa zicem ca f(n) este numarul total de rute posibile. Pentru f(6) avem 14 rute de mai jos
1 → 2 → 3 → 4 → 5 → 6
1 → 2 → 3 → 5 → 4 → 6
1 → 2 → 4 → 3 → 5 → 6
1 → 2 → 4 → 5 → 3 → 6
1 → 2 → 5 → 3 → 4 → 6
1 → 2 → 5 → 4 → 3 → 6
1 → 3 → 2 → 4 → 5 → 6
1 → 3 → 2 → 5 → 4 → 6
1 → 3 → 4 → 2 → 5 → 6
1 → 3 → 5 → 2 → 4 → 6
1 → 4 → 2 → 3 → 5 → 6
1 → 4 → 2 → 5 → 3 → 6
1 → 4 → 3 → 2 → 5 → 6
1 → 4 → 5 → 2 → 3 → 6

f(6)=14
alte exemple:
f(10) = 254 si f(40) = 1439682432976.


Sa zicem ca S(L) = ∑ f(n)^3 pentru 1 ≤ n ≤ L.
exemple:
S(10) = 18230635
S(20) = 104207881192114219
S(1 000) mod 10^9 = 225031475
S(1 000 000) mod 10^9 = 363486179

calculeaza S(10^14) mod 10^9.



Am creat u program care calculeaza rutele posibile. Calcularea tuturor rutelor e foarte costisitoare de aceea cred ca se poate calcula o formula pentru aflarea numarului rutelor.

de exemplu pentru n=40 calcularea tuturor rutelor dureaza 3 minute si creste exponential.

Ceva idei de plecare? Ce as putea cauta?

A_Cristian
guru
guru
Mesaje: 1964
Membru din: 23 Feb 2015, 17:15

Mesaj de A_Cristian » 07 Apr 2015, 17:33

In general problemele de pe projecteuler nu se pot face doar cu o formula matematica. Exceptand 2-3 probleme din primele 100.
M-am gandit prima data la un PD, dar nu prea merge.
M-a pus pe ganduri cazul n=10 cu solutia 1-->4-->7-->9--->6-->3-->2-->5-->8-->10.

PS: Cate probleme ai rezolvate in total?

Scrie răspuns
  • Subiecte similare
    Răspunsuri
    Vizualizări
    Ultimul mesaj