Imprimă pagina - 044 Al k-lea termen Fibonacci

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Marius Stroe din Ianuarie 04, 2010, 18:56:18

Titlul: 044 Al k-lea termen Fibonacci
Scris de: Marius Stroe din Ianuarie 04, 2010, 18:56:18

Aici puteţi discuta despre problema Al k-lea termen Fibonacci (http://infoarena.ro/problema/kfib).

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Ionescu Robert Marius din Martie 03, 2010, 16:53:22

cine imi explica si mie de ce sursa asta ia 100-a :
http://infoarena.ro/job_detail/380187?action=view-source

Cod:

#include<fstream>
using namespace std;
int main()
{
	fstream in("kfib.in",ios::in),out("kfib.out",ios::out);
    int x=0,y=1,z,k;
    in>>k;
    while(k--%1332028)z=(x+y)%666013,x=y,y=z;
    out<<x<<endl;
}

aha ms

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Mihai Calancea din Martie 03, 2010, 17:33:22

Numerele Fibonacci sunt periodice modulo m . Cel mai probabil 1332028 este lungimea perioadei pentru m = 666013.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Canta Andrei din Martie 08, 2010, 15:48:57

Exista formula pentru termenul general la sirul fibonacci (nu ma refer la recurenta)
O explicatie : http://www.ginfo.ro/revista/14_1/mate2.pdf (http://www.ginfo.ro/revista/14_1/mate2.pdf)

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Cosmin Negruseri din Martie 08, 2010, 16:20:07

Nu prea ai ce face cu formula pt problema asta pt ca ti-ar trebui calcule cu numere reale de precizie mare.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Simoiu Robert din Martie 08, 2010, 16:20:59

Nu cred ca merge cu numere mari :-?

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Canta Andrei din Martie 08, 2010, 23:03:50

N-am incercat sa implementez... dar banuiesc ca daca folosesti round() o sa dea bine

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Cosmin Negruseri din Martie 08, 2010, 23:40:14

Ia incearca, ca sa intelegi mai bine ce se intampla.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Otilia Stretcu din Martie 23, 2010, 12:51:53

Puteti sa imi explicati si mie va rog cum functioneaza "1LL" din expresia:
C[j] = (C[j] + 1LL * A[k] * B[k][j]) % mod;
Presupun ca transforma in long long, pentru cazul in care A[k]*B[k][j] depaseste tipul int. Dar mi-ar placea sa inteleg mai bine ce se intampla cu expresia si in ce context ar mai putea fi folosit.
Multumesc! :D

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Andrei Grigorean din Martie 23, 2010, 13:58:02

1LL înseamna valoarea 1 reținută pe 64 de biți. Când înmulțești un long long cu un int, se va face cast la long long. Astfel, dacă vrei să înmulțești două variabile A și B de tip int, iar produsul lor intră doar pe long long, poți face ca mai sus: 1LL * A * B. O altă varianta ar fi să scrii tu castul de mână: (long long)(A) * B.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Otilia Stretcu din Martie 23, 2010, 14:28:27

Am inteles! :) Multumesc!

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Petru Trimbitas din Iunie 06, 2010, 19:39:49

Ar mai fi aici si problema nkbiti

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: c a e n din Aprilie 24, 2011, 18:46:04

Exista vreun mod prin care sa determini (rapid) perioada in astfel de cazuri, sau metoda simpla nu este practica in timpul unui concurs? Multumesc!

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: FMI Ciprian Olariu din Noiembrie 03, 2011, 20:29:00

Cred ca este o problema cu timpii la evaluator la problema aceasta,intrucat observ in monitor foarte multe surse de 0.30-0.50kb care implementeaza fibonacci in mod clasic,liniar,surse care iau 100pct,desi se zice ca ar trebui sa ia vreo 20pct :readthis:

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Mihai Calancea din Noiembrie 03, 2011, 21:00:26

Citat din mesajul lui: Olariu Ciprian din Noiembrie 03, 2011, 20:29:00

Mnop. Sursele alea se folosesc de periodicitatea numerelor Fibonacci modulo n. Pentru n-ul din problema asta, perioada e mica (2 * n parca ) si poate fi calculata liniar.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Nicu B. din Aprilie 17, 2013, 14:56:09

Merge cu o idee asemanatoare sa faci in timp logaritmic si al k-lea termen fibonacci de 3, 4, 5 s.a.m.d. ?(fib de 3 fiind Fn=Fn-1+Fn-2+Fn-3)

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Paul-Dan Baltescu din Aprilie 17, 2013, 14:58:53

Da.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Nicu B. din Aprilie 17, 2013, 22:49:22

Imi poti spune te rog cum arata matricea fixata pentru fib de 3? Nu gasesc niciun pattern fata de fib de 2.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Mihai Calancea din Aprilie 17, 2013, 23:12:47

Iti spunem duminica la 00:00:00 daca vrei :D.

L.E: Sarumana, Craciun :).

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Adrian Craciun din Aprilie 18, 2013, 00:38:58

@Mihai
Cred ca vrei sa zici duminica :P

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Nicu B. din Aprilie 18, 2013, 08:18:17

:)) Ok.

L.E.: Am reusit dupa cateva zile de inmultit matrici pe la scoala sa ajung la un rezultat. Parca ma simt mai bine decat daca mi-ati fi trantit rezultatul in fata :)) Deci, multumesc!

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Andrei Constantinescu din Iulie 08, 2013, 21:51:55

Am facut si eu problema asta si am luat pe ea 100p, explicatia este foarte bine realizata! (mai ales ca poate fi usor generalizata rezolvarea problemei pentru Fn=aFn-1+bFn-2) :thumbup:
La restrictii scrie ca "0 ≤ K ≤ 1 000 000 000." Cazul k=0 nu se afla in testele problemei desi este particular si multe surse (inclusiv prima pe care am trimis-o) dau raspuns gresit sau se blocheaza pe acest caz. Eu am tratat cazul printr-un simplu if. Cred ca ar trebui incurajata o rezolvare corecta a problemei caci in timpul unui concurs o sursa ce nu trateaza cazul k=0 poate duce la pierderea de puncte valoroase.
Toate cele bune.

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Daniel Constantin Anghel din Iulie 09, 2013, 19:11:22

f[-1]= 1 si toate cazurile tale particulare dispar
dar e o idee buna sa fie modificata restrictia in 1<=k<=10^9

Titlul: Răspuns: 044 Al k-lea termen Fibonacci
Scris de: Certnat Sorin din Mai 07, 2014, 10:49:46

testele dau 100 de puncte la implementarea directa :!: