class EffektivFib {
// Dette er et eksempel p? en mer effektiv m?te ? regne ut fibbonacci-tall p?. Dette er ikke ekesamensrelevant, men illusterer
// hvordan man kan gj?re rekursive metoder litt mer effektive ved ? lagre mellomregninger. Enten kan man gj?re det slik jeg har gjort her ved ? ha en
// global variabel som lagrer mellomregninger, eller man kan sende memoet med i funksjonskallet.
private long [] memo; // For ? ung? dobbelt arbeid lagrer vi tallene vi regner ut underveis. Dette lar oss effektivt regne ut mye h?yere verdier av Fibbonaccitallene.
public EffektivFib(int n) {
memo = new long[n];
memo[0] = 1;
}
public long nthFib() {
return nthFib(memo.length);
}
private long nthFib(int n) {
if (n == 0) return 0;
else if (memo[n-1] != 0) return memo[n-1]; // Sl?r opp i memoet, og dersom tallet finnes i lista returnerer vi det.
memo[n-1] = nthFib(n-1) + nthFib(n-2); // Hvis ikke regner vi ut det neste tallet, og returnerer det.
return memo[n-1];
}
public static void main(String[] args) {
EffektivFib f = new EffektivFib(92); // Dette er det h?yeste fibonaccitallet vi kan regne ut med long uten at tallet overl?per (tallet er for stort til ? lagte med 64 bit).
f.nthFib();
for (long i : f.memo) System.out.println(i); // Skriver ut alle tallene.
}
}