I serien av hvordan jeg har løst Project Euler problemer kommer problem 3. Til nå har mine løsninger vært relativt naiv brute force framfor eleganse.
Problemet 2 var å finne summen av alle partall i en fibbonaccirekke.
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Fordelen med å brute force, er at en får muligheten til å se hvordan VANVITTIG smarte mennesker har løst problemet du nettopp jobbet gjennom. For eksempel ville jeg aldri oppdaget at fibbonaccirekker har et mønser som ser slik ut:
O, O, P, O, O, P...
Med andre ord, i stedet for å lagre alle tallene for så sjekke om de er partall som jeg gjorde i første forsøk, så kan en bare holde tellingen på hvor en er i rekken og plukke ut hvert tredje tall.
Min første naive løsning
public class Problem2
{
int sum = 0;
List<int> fibbseq;
public int fib(int first, int second)
{
fibbseq = new List<int>();
fibbseq.Add(first);
fibbseq.Add(second);
int counter = 1;
while (fibbseq.Last() <= 4000000)
{
fibbseq.Add(fibbseq.ElementAt(counter) + fibbseq.ElementAt(counter-1));
counter++;
}
foreach (int i in fibbseq)
{
if (i % 2 == 0)
sum += i;
}
return sum;
}
}
Hadde egentlig tenkt til å løse problemet rekursivt med memoization, men kom frem til at det ville være raskere å bruke en liste slik at jeg raskt kunne løpe over den etterpå for å hente ut partallene. Ja, i perspektiv av etterpå ser jeg at det var mange bedre måter å gjøre det på.
Refaktorert løsning
public class Problem2Alt
{
int sum = 2;
public int fib(int first, int second)
{
int temp;
int counter = 0;
while (second <= 4000000)
{
temp = second;
second += first;
first = temp;
counter++;
if (counter % 3 == 0)
sum += second;
}
return sum;
}
}
Kort fortalt har jeg droppet listen, gått tilbake til "klassiske fibbonacci swap"* og hver gang jeg er på en plass det er partall legges det til den totale summen.
Utregningen tar nå 0.0002638 sekunder, i motsettning til vanvittige 0.0132318 sekunder (~13ms) det tok på den orginale brute forcingen. Dette på en 2.33GHz quad core Xeon cpu med 4GB minne. Skal jeg være ærlig så er begge helt akseptabel, i den store sammenheng, men det er morsomt å se at en kan forbedre hastigheten bare fordi en kan.
"We do what we must because we can." - John Coulton
* Jeg har hovedsaklig sett tre måter å løse fibbonacci på:
- Rekursivt
- Swap med a, b, tmp
- Rekursivt med memoization