Sprawdzanie Fibonacciego

0

Napisałem takie algorytmy sprawdzające czy liczba należy do ciągu Fibonacciego. MAX_N ograniczyłem do 50(liczba obrotów pętli),
lecz pani profesor stwierdziła że algorytmy te muszą kończyć się kiedy zostanie wykryte że liczba jest fibo(bądź nie) . Proszę o poprawę algorytmów. Bo ja już pomysłu nie mam jak to powinno być:)

 

a.	Na prostych zmiennych

bool isInFibVar(int x)
{
	if (x == 0 || x == 1) return true;
	int f0 = 0, f1 = 1, fn;
	for (int i = 2; i <= MAX_N; i++)
	{
		fn = f0 + f1;
		if (fn == x) return true;
		f0 = f1;
		f1 = fn;	
	}
	return false;
}

b) Na tablicy

bool isInFibTab(int x)
{
	if (x == 0 || x == 1) return true;
	int tab[MAX_N+1] = {0, 1};
	for (int i = 2; i <= MAX_N; i++)
	{
		tab[i] = tab[i-1] + tab[i-2];
		if (tab[i] == x) return true;
	}
	return false;
}

1

Pewnie chodzi o to że jeśli pewna liczba fibonaciego jest większa niż Twój x to nie musisz szukać dalej (przerywasz wtedy działanie programu).

Ciekawostka (nie wiem na ile będzie przydatna w praktyce z powodu ograniczonej precyzji):
X jest liczbą fibonacciego wtedy i tylko wtedy kiedy zachodzi
\varphi x - \frac{1}{x} \leq n \leq \varphi x + \frac{1}{x}
Dla jakiegoś naturalnego n (mówiąc prościej, kiedy w przedziale &lt;\varphi x - \frac{1}{x}; \varphi x + \frac{1}{x}&gt; jest jakaś liczba całkowita).

Jakiś mały kod demonstracyjny (najszybciej było w pythonie):

phi = 1.61803398875

def is_fib(x):
    return floor(phi * x - 1.0 / x) < floor(phi * x + 1.0 / x)

for i in (x for x in range(1, 100) if is_fib(x)):
    print i
0

Ciąg Fibonacciego jest bardzo szybko rosnący, wiec ilość liczb, które zmieszczą się w zakresie int jest dość mała (47 licząc od 0, 1, 1, 2). Spokojnie można je wygenerować wszystkie raz osobnym programem, a potem twardo wpisać w tablicę i potem przeszukiwać tablicę by sprawdzić czy podana liczba należy do ciągu Fibonacciego.

Możesz też inaczej zbudować warunek kończący pętlę fn<x powinno załatwić sprawę.

1 użytkowników online, w tym zalogowanych: 0, gości: 1