Hvordan kan man lave en iterativ metode af denne rekursive metode

hvorfor vil du lave det om? rekursiv kode er mere effektivt efter min bedste overbevisning.

ja det ved jeg godt men jeg har en opgave hvor man skal lave det på begge måder.
Og jeg er helt blank vedrørende den iterative løsning

Det kunne gøres sådan:

public static int fib2(int n)
{
    int k = 2;
    if (n >= k)
        k = n + 1;
    int[] a = new int[k];
    a[0] = 0;
    a[1] = 1;
    count += 2;
    int i = 1;
    while(i < n)
    {
        i++;
        a[i] = a[i - 1] + a[i - 2];
        count++;
    }
    return a[n];   
}

Det var noget kode jeg havde liggende og jeg har lige kigget lidt nærmere på det. Count variablen skal du bare slette - den blev brugt til benchmark.

Metoden returnerer det n'te fibonacci-tal.

Her er et helt eksempel, kan sikkert gøres pænere, men det virker.

/**
* Created by IntelliJ IDEA.
* User: sreinke
* Date: Mar 27, 2003
* Time: 3:42:18 PM
* To change this template use Options | File Templates.
*/
public class Fibo
{
    private final int opTil=10;

    public Fibo()
    {
        for(int x=1;x<opTil;x++)
        {
            System.out.println("Fibo #"+x+" = "+fiboCalc(x));
        }
    }

    private long fiboCalc(int x)
    {
        if(x<=2) return 1;
        x=x-1;
        long[] fibo=new long[x+1];
        fibo[0]=1;
        fibo[1]=1;

        for(int y=2;y<=x;y++)
        {
            fibo[y]=fibo[y-1]+fibo[y-2];
        }
        return fibo[x];
    }

    public static void main(String[] args)
    {
        new Fibo();
    }
}

op til fibo tal #92, så har vi et overflow af 'long'

en lidt pænere model:

/**
* Created by IntelliJ IDEA.
* User: sreinke
* Date: Mar 27, 2003
* Time: 3:42:18 PM
* To change this template use Options | File Templates.
*/
public class Fibo
{
    private final int opTil=6;

    public Fibo()
    {
        for(int x=1;x<opTil;x++)
        {
            System.out.println("Fibo #"+x+" = "+fiboCalc(x));
        }
    }

    private long fiboCalc(int x)
    {
        if(x<=2) return 1;
        long[] fibo=new long[x];
        fibo[0]=1;
        fibo[1]=1;

        for(int y=2;y<x;y++)
        {
            fibo[y]=fibo[y-1]+fibo[y-2];
        }
        return fibo[x-1];
    }

    public static void main(String[] args)
    {
        new Fibo();
    }
}

nææh det virker ikke....
da fibo(4) skal give 7.33333
og fib0(5) skal give 9.11111

skriver lige lidt mere info her..

x  f(x)
1    2
2    4
3    16

f(4)=(f(3)+f(2)+f(1))/3=(16+4+2)/3 =7.3333
f(5)=(f(4)+f(3)+f(2))/3=(7.3333+16+4)/3 = 9.1111

den recursive metode virker fint og returnere det som står ovenover for eks f(4) og f(5)

og sådan skal den iterative oxo virke...

no way !
fibonaci tal rækken er følgende:
1 1 2 3 5 8 13 21 34 55 ....

Det næste tal er altid summen af de forgående 2 fibonaci tal.

tal #1 og tal #2 er begge 1


Se f.eks. her:
http://www.formeraboutguides.com/investingcanada/library/weekly/1999b/aa112599.htm

Okay nogle gange er tal #1 defineret som 0.

men så er koden bare:

/**
* Created by IntelliJ IDEA.
* User: sreinke
* Date: Mar 27, 2003
* Time: 3:42:18 PM
* To change this template use Options | File Templates.
*/
public class Fibo
{
    private final int opTil=6;

    public Fibo()
    {
        for(int x=1;x<opTil;x++)
        {
            System.out.println("Fibo #"+x+" = "+fiboCalc(x));
        }
    }

    private long fiboCalc(int x)
    {
        if(x<=2) return x-1;
        long[] fibo=new long[x];
        fibo[0]=0;
        fibo[1]=1;

        for(int y=2;y<x;y++)
        {
            fibo[y]=fibo[y-1]+fibo[y-2];
        }
        return fibo[x-1];
    }

    public static void main(String[] args)
    {
        new Fibo();
    }
}

Jeg gik ud fra siden du kaldte din metode fibo at det var fibonaci's talrække vi snakkede om, hvis det ikke er korrekt, er mit eksempel selvfølgelig forkert.

Er det ikke fibonnachi funktionen vi ser på?

fib(n) = fib(n-2) + fib(n-1) for alle hele tal n>0

Da summanterne er heltal kan fib(n) aldrig givet en double.

Hvis det er en anden funktion kan du så ikke give definitionen?

Her er forøvrigt en pænere rekursiv metode der finder de korrekte fibonnachi tal:

public static int fib(int n) {
  if (n<1) return 0;
  return (n>=2 ? fib(n-2) + fib(n-1) : 1);
}

jjust:
Pæn vil jeg nu ikke kalde den, brug af den ternary operater gavner ikke ligefrem læsbarheden af koden, en if sætning istedet er mere læsbart, og i den sidste ende gør det ingen forskel.

public static int fib(int value) {
        if (value==0||value==1||value==2) return value;
        else return (fib(value-1)+fib(value-2));
    }
min egen, men den giver vist desværre fib(n-1) og ikke fib(n).

disky: Det er vel en smagssag. Når man har vendet sig til ( ? : )
synes at det er hurtigere at overskue hvad der foregår.

yep det er en smagssag ingen tvivl om det, jeg hader bare koder der er lavet så det rent tegn mæssigt fylder mindst muligt.

Nogle udviklere tror det er hurtigere i afvikling, hvis sourcen fylder mindst muligt :(

disky: Jeg er godt klar over at det ikke nødvendigvis er hurtigere (har ikke kigger javac efter i sømmene). Jeg er også enig med dig i at ( ? : ) til tider kan gøre koden uoverskuelig (specielt hvis det er første gang man ser sådan et udtryk). I ovenstående tilfælde mener jeg bare at koden er klar og let overskuelig. Den matematiske funktion træder tydeligt igennem, og al udenomssnakken er stærkt begrænset.

jeg følger KISS standarden :-)

Keep It Simple Stupid

Dette er dog ikke ment som at alle der ikke gør er dumme.

jamen det er jo simpelt ;-)

Mit forslag (til tal = sum af 2 foregående tal):

public class Fib {
    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println(i + " " + fib1(i) + " " + fib2(i));
        }
    }
    public static int fib1(int n) {
        if (n > 2) {
            return (fib1(n - 1) + fib1(n - 2));
        } else {
            return 1;
        }
    }
    public static int fib2(int n) {
        if (n > 2) {
            int[] a = new int[2];
            a[0] = 1;
            a[1] = 1;
            for(int i = 2; i < n; i++) {
                a[i % 2] = a[0] + a[1];
            }
            return a[(n - 1) % 2];
        } else {
            return 1;
        }
    }
}

Dem der bruger int til beregning kan kun regne op til omkring #47 før man ramler ind i et overflow.

jjust:
Synes jeg ikke, koden bliver for compact, og det gør ingen forskel til sidst alligevel.

Og den angivne algoritme (som jeg ikke helt forstår) vil se ud som:

public class FibX {

    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println(i + " " + fibRecursive(i) + " " + fibIterative(i));
        }
    }
    public static double fibRecursive(int n) {
        if (n < 0)
            return -1;
        else if (n == 1 || n == 2)
            return n * 2;
        else if (n == 3)
            return 16;
        else
            return (fibRecursive(n - 1) + fibRecursive(n - 2) + fibRecursive(n - 3)) / 3.0;
    }
    public static double fibIterative(int n) {
        if (n < 0)
            return -1;
        else if (n == 1 || n == 2)
            return n * 2;
        else if (n == 3)
            return 16;
        else {
            double[] a = new double[3];
            a[0] = 2;
            a[1] = 4;
            a[2] = 16;
            for(int i = 3; i < n; i++) {
                a[i % 3] = (a[0] + a[1] + a[2]) / 3.0;
            }
            return a[(n - 1) % 3];
        }
    }
}

jeg siger mange tak arne v din metode virkede point dine
fandt ud af jeg havdet rodet rundt i to opgave en med fibonaci og en med f(x)
derfor den store misforståelse og denne her skulle være f(x) og ikke fibonaci
som jeg sagde...
mange gange undskyld for den bommert...