Ciag fibonacciego -> ostatnia cyfra

0

Witam! posiadam taki kod, ale nie rozumiem niektórych linijek. Prosiłbym o krótkie wytłumaczenie, z góry dzięki


#include <stdio.h>

int main()
{
	int t, z, n, i, a, b, tab[61];

	// Pobranie liczby zestawów danych
	scanf("%d", &t);

	for (z = 0; z < t; ++z)
	{
		// Pobranie zestawu danych
		scanf("%d %d %d", &n, &a, &b);

		tab[1] = a%10;
		tab[2] = b%10;

		// Obliczenie n-tego wyrazu ciągu.
		// Potrzebujemy tylko ostatniej cyfry, więc wyniki dzielimy przez modulo 10.
		n = (n-1)%60 + 1;
		for(i = 3; i <= n; ++i)
			tab[i] = (tab[i-1] + tab[i-2]) % 10;
		printf("%d\n", tab[n]);
	}

	return 0;
}

A nie rozumiem linijek:

  1. n = (n-1)%60 + 1; -> Dlaczego jest %60?
  2. for(i = 3; i <= n; ++i) -> Dlaczego zaczynamy od i=3?

Z góry dzięki

0
  1. Bo
int tab[61]
  1. Bo
tab[1] = a%10;
tab[2] = b%10;
0

ok, drugą zrozumiałem. A jeśli chodzi o pierwszą, to wiesz może dlaczego jest akurat [61]?

http://pl.spoj.com/problems/KRO/
Tu jest treść tego zadania.

Dzięki za pomoc.

0

Ten kod ma dobry pomysł, który jest źle wykonany.
Cały cymes w tym pomyśle polega na zauważeniu, że ostatnia cyfra ciągu Fibonacciego tworzy cykl.
W pewnym momencie w tym ciągu pojawi się sekwencja dwóch jedynek. https://pl.wikisource.org/wiki/Ci%C4%85g_Fibonacciego
Fib(1) = Fib(61) mod 10 oraz Fib(2) = Fib(62) mod 10 a z powodu wzoru rekurencyjnego to oznacza, że zawsze Fib(n) mod 10 = Fib(n+60) mod 10.

0

Co znaczy dokładnie ta "sekwencja dwóch jedynek"?

1

F(n) \equiv F(n+60) \ mod \ 10
!

0

Już rozumiem. Dzięki za pomoc i cierpliwość

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