Zaprogramuj go - wersja rekurencyjna - I_R_W14_M09_Java Ciąg Fibonnaciego

R7L2RZA2MV5A1

Ciąg Fibonnaciego - wersja rekurencyjna

Napiszemy program, który zwróci element ciągu Fibonacciego o indeksie n. Zastosujemy rekurencję.

Napiszemy program, który zwróci element ciągu Fibonacciego o indeksie n. Zastosujemy iterację.Sprubuj rozwiązać zadanie samodzielnie, jeżeli popełnisz błąd zapoznaj się z dalszą częścią materiału.

Ćwiczenie 1

Napisz program, który wyznaczy n‑ty wyraz ciągu Fibonnaciego metodą rekurencyjną.

Specyfikacja problemu:

Dane:

n – liczba naturalna

Wynik:

n‑ty element ciągu Fibonnaciego

R1LHHTDP1CDV5

Przykładowe rozwiązanie zadania

import java.util.Scanner;

public class ciąg {
  public static long rekFibonacci(int n){
  	if (n == 0) 
  		return 0;
  	 else 
       	if (n == 1) 
  			return 1;
  		else 
  			return rekFibonacci(n-1) + rekFibonacci(n-2);
  }
  
  public static void main(String[] args) {
  	// Wczytanie ziennej n z klawiatury
  	
  	Scanner scanner = new Scanner(System.in);
  	System.out.print("Podaj n: ");
  	int n = scanner.nextInt();
  	
  	System.out.print(rekFibonacci(n));
  	
  }
  
}

public static long rekFibonacci(int n) {

}

Wybieramy typ long, ponieważ wartości kolejnych wyrazów ciągu Fibonacciego rosną wykładniczo.

Parametr n funkcji będzie indeksem elementu ciągu, który ma być obliczony.

Zapisujemy warunki, po których spełnieniu zostanie zatrzymane działanie funkcji i zwróci ona wartość. Wiemy, że pierwszy wyraz ciągu Fibonacciego – zatem wyraz o indeksie 0 – ma wartość 0. Natomiast drugi wyraz – czyli wyraz o indeksie 1 – wynosi 1. Zapiszemy odpowiednie instrukcje warunkowe.

public static long rekFibonacci(int n) {
	if (n == 0) {
		return 0;
	} else if (n == 1) {
		return 1;
	}
}

Po zakończenie wykonujemmy rekurencyjne obliczanie (zgodnie z definicją) n‑1 i n‑2 elementu ciągu.

public static long rekFibonacci(int n) {
	if (n == 0) 
		return 0;
	 else 
     	if (n == 1) 
			return 1;
		else return rekFibonacci(n-1) + rekFibonacci(n-2)
	
}

Zaprogramuj go - wersja iteracyjna

Złota liczba

Ciąg Fibonnaciego - wersja rekurencyjna