Praca domowa 3 zad 22
22. Wypisz n-ty wyraz ciągu Fibonacciego (gdzie n jest liczbą przekazywaną przez użytkownika do
programu w momencie jego uruchomienia). Ciąg Fibonacciego można zdefiniować w następujący
sposób: pierwszy i drugi element tego ciągu są równe 1, a każdy następny jest sumą dwóch
poprzednich. Kilka pierwszych wyrazów ciągu wygląda zatem w następujący sposób: 1, 1, 2, 3, 5, 8,
13, 21, 34, 55, ... Nie musisz wypisywać wszystkich wyrazów poprzedzających n-ty wyraz. Proszę
wykorzystać w tym celu rekurencję (w poprzednim zestawie zadań domowych podobną operację
należało wykonać iteracyjnie, z użyciem pętli).
// // SPOSOB 1:
// public class MyClass
// {
// public static void main(String args[])
// {
// int n=Integer.parseInt(args[0]);
// int wyr1 = 1 , wyr2 = 1;
// int suma = 0;
// System.out.print(n+" pierwszych wyrazow ciagu fibonacciego: "+wyr1+" "+wyr2+" ");
// for(int i=2; i < n; i++)
// {
// suma = wyr1 + wyr2;
// System.out.print(suma+" ");
// wyr1 = wyr2;
// wyr2 = suma;
// }
// System.out.print("\n"+n+" wyraz ciagu fibonacciego: "+suma);
// }
// }
1 - Czy sposób 1 można zaliczyć jako rozwiązanie rekurencyjne? Bo chyba rekurencja nie znaczy, że trzeba tworzyć nową metodę?
// // SPOSOB 2: //??????????????????????
// public class MyClass
// {
// static int fibo(int x)
// {
// int a=1;
// int b=1;
// x=a+b;
// b=x;
// a=b;
// return x;
// }
// public static void main(String args[])
// {
// int n=Integer.parseInt(args[0]);
// fibo(n);
// }
// }
2 - Czy można jakoś zmodyfikować sposób 2, aby program działał?
// SPOSOB 3 (z odpowiedzi):
public class MyClass
{
public static void main(String args[])
{
int n = Integer.parseInt(args[0]);
System.out.println(n + "-ty wyraz ciągu Fibonacciego: " + wyraz(n));
}
static int wyraz(int n)
{
int x;
if (n == 1 || n == 2)
{
x = 1;
return x;
}
else
{
x = wyraz(n-1) + wyraz(n-2);
return x;
}
}
}
3 - Czy w sposobie 3 "n" działa jak indeks tablicy, tylko że to n jest równe numerowi elementu (np. dla n=1 jest pierwszy element)? Czyli rekurencja to jest jakby niebezpośrednie stworzenie tablicy?
Czemu return x nie można napisać jeden raz poza pętlami if i else?
Skąd program wie, że n ma się zwiększać skoro nie ma bezpośredniej instrukcji n++?
Programowanie Dodaj post do ulubionych Poproś o pomoc
- 1
- Zaloguj się lub zarejestruj, by móc oceniać komentarze.
- Dodaj do ulubionych
1 - ja bym jednak rozumiał rekurencję jako wykorzystanie przez jakąś metodę samej siebie.
2 - trzeba gdzieś tam zaimplementować tę rekurencję, bo jak na razie w ogóle jej tutaj nie ma. Tzn. we wnętrzu funkcji fibo ona nigdzie nie jest wywoływana. Więc ta funkcja jak na razie zawsze zwróci po prostu wartość równą 2.
3 - hmm, nie wiem czy rozumiem pytanie, ale w każdym razie tu nie ma żadnego tworzenia tablicy. Funkcja wywołuje samą siebie, jeśli n jest większe niż 2 i potem każde wywołanie jest już dla zmniejszającego się n (mamy tam n-1 i n-2 w argumentach funkcji wywoływanej). Ale w istocie n oznacza nr elementu z ciągu Fibonacciego.
A return x można w istocie napisać poza ifem i elsem.
Natomiast n właśnie się nie zwiększa tylko zmniejsza - zgodnie z tym co napisałem wcześniej, tak, że w końcu wywołania metody wyraz będą miały w argumencie n równe 1 lub 2, dla których wynikiem jest już po prostu 1. I wtedy cała rekurencja się kończy.