Ciąg Fibonacciego i wzór Herona

Potrzebuję pomocy z Java. Ktoś pomoże napisać te zadania w Java??

• Zadanie 2.

• a. Przebieg procedury Herona uzależnić od Epsilon
• b. Przebieg procedury Herona uzależnić od N (ilości kroków)

• Zadanie 3. Dany jest ciąg Fibonacciego
  (defn fib [n]
  (if (< n 2)
  n
  (+ (fib (- n 1)) (fib (- n 2)))))

a. Wyznaczyć dokładny wzór opisujący ilość kroków niezbędnych do obliczenia (fib n)
b. Zaproponować procedurę rekurencyjną fib, która generuje proces iteracyjny
c. Zastosować formę (recur ...) i policzyć Fib(10000)

• Zadanie 4. Zbiór potęgowy (ang. powerset)
  Napisać procedurę, która przyjmuje kolekcję elementów (lista, wektor, zbiór) i
  generuje zbiór potęgowy dla tej kolekcji. Zbiór potęgowy to zbiór wszystkich
  podzbiorów danego zbioru łącznie ze zbiorem pustym.

  (powerset [1 2 3]) => ([] [1] [2] [3] [1 2] [1 3] [2 3] [1 2 3])

Co już masz, gdzie szukałeś rozwiązania, dlaczego nie działało? Etc...

Mam coś takiego, jednak powyżej n 92 wyniki są niepoprawne, zaczynają się od "-"

public class Fibonacci {
    public static long fib(int n) {
        if (n < 2) {
            return n;
        }

        long a = 0;
        long b = 1;
        long result = 0;

        for (int i = 2; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 92; // 
        long result = fib(n);
        System.out.println("Fib(" + n + ") = " + result);
    }
}

Zapewne przekroczyłeś longa, a który podpunkt rozwiązać ten kod?

Podpowiedzi do zadania 3.
Zamiast inta i zwracanego longa, dla dużych liczb naturalnych w Javie korzysta się z BigInteger. Klasa opakowująca dla klasy Integer (int też, ale to z przyczyn autoboxingu, zamiany między wartością prymitywną a obiektem).
A tak to, pseudokod masz napisany w zadaniu (wygląda na Clojure)

I coś na zasadzie:

static BigInteger recursiveFibb(BigInteger n) { 
  // kilka warunków
  recursiveFibb(n - 1) + recursiveFibb(n - 2)
}

kubaq111 napisał(a):

• a. Przebieg procedury Herona uzależnić od Epsilon

public class HeronSquareRoot {
    public static double heronSquareRoot(double x, double epsilon) {
        if (x < 0) {
            throw new IllegalArgumentException("Liczba musi być większa lub równa 0.");
        }

        double guess = x; // Inicjalizacja początkowej wartości odgadnięcia
        int iteration = 0; // Licznik iteracji

        while (Math.abs(guess * guess - x) > epsilon) {
            guess = 0.5 * (guess + x / guess); // Aktualizacja odgadnięcia
            iteration++;
        }

        System.out.println("Liczba iteracji: " + iteration);
        return guess;
    }

    public static void main(String[] args) {
        double x = 16.0; // Liczba, której pierwiastek chcemy obliczyć
        double epsilon = 0.0001; // Wartość epsilon

        double sqrt = heronSquareRoot(x, epsilon);
        System.out.println("Pierwiastek kwadratowy z " + x + " wynosi: " + sqrt);
    }
}

kubaq111 napisał(a):

• b. Przebieg procedury Herona uzależnić od N (ilości kroków)

public class HeronSquareRoot {
    public static double heronSquareRoot(double x, int N) {
        if (x < 0) {
            throw new IllegalArgumentException("Liczba musi być większa lub równa 0.");
        }

        double guess = x; // Inicjalizacja początkowej wartości odgadnięcia

        for (int i = 0; i < N; i++) {
            guess = 0.5 * (guess + x / guess); // Aktualizacja odgadnięcia
        }

        return guess;
    }

    public static void main(String[] args) {
        double x = 16.0; // Liczba, której pierwiastek chcemy obliczyć
        int N = 10; // Ilość kroków (liczba iteracji)

        double sqrt = heronSquareRoot(x, N);
        System.out.println("Pierwiastek kwadratowy z " + x + " po " + N + " krokach wynosi: " + sqrt);
    }
}

a. Wyznaczyć dokładny wzór opisujący ilość kroków niezbędnych do obliczenia (fib n)

W algorytmie iteracyjnym wzór na ilość kroków to n - 1, ponieważ zaczynamy od 0 i wykonujemy n - 1 iteracji, aby obliczyć n-tą liczbę Fibonacciego.

W rekurencyjnym liczba kroków wynosi około 2^n.
Jeśli chcesz obliczyć dokładną ilość kroków dla danego n, musiałbyś przeanalizować rekurencyjną strukturę algorytmu Fibonacciego i policzyć liczbę wywołań funkcji rekurencyjnych dla danego n. Można to zrobić przy użyciu technik dynamicznego programowania lub memoizacji, aby uniknąć wielokrotnego obliczania tych samych wartości. Wtedy ilość kroków będzie dokładnie zależała od n, ale nadal będzie to rosnąca funkcja wykładnicza.

b. Zaproponować procedurę rekurencyjną fib, która generuje proces iteracyjny

public class Fibonacci {
    public static long fib(int n) {
        return fibHelper(n, 0, 1);
    }

    private static long fibHelper(int n, long a, long b) {
        if (n == 0) {
            return a;
        } else if (n == 1) {
            return b;
        } else {
            return fibHelper(n - 1, b, a + b);
        }
    }

    public static void main(String[] args) {
        int n = 10;
        long result = fib(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

c. Zastosować formę (recur ...) i policzyć Fib(10000)

W Javie, ze względu na ograniczenia stosu rekursji, obliczanie Fib(10000) za pomocą rekurencji w formie recur byłoby nieefektywne i prowadziłoby do przepełnienia stosu. Jest to wynik ogromnej liczby wywołań rekurencyjnych, co skutkuje błędem "StackOverflowError".

Zapewne to zadanie ma Wam pokazać ten problem i powinniście te obliczenia zrobić iteracyjnie:

import java.math.BigInteger;

public class Fibonacci {
    public static BigInteger fib(int n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            BigInteger next = a.add(b);
            a = b;
            b = next;
        }

        return b;
    }

    public static void main(String[] args) {
        int n = 10000;
        BigInteger result = fib(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}