#include "stdafx.h" #include #include unsigned int fib(unsigned int n) { return 1.0/sqrt(5.0) * ( pow( (1.0+sqrt(5.0))/2.0 , (double)(n) ) - pow( (1.0-sqrt(5.0))/2.0 , (double)(n) ) ); } using namespace std; unsigned long Tfib[88]; void zaladuj_fib(){ Tfib[0]=1; Tfib[1]=1; Tfib[2]=2; Tfib[3]=3; Tfib[4]=5; Tfib[5]=8; Tfib[6]=13; Tfib[7]=21; Tfib[8]=34; Tfib[9]=55; Tfib[10]=89; Tfib[11]=144; Tfib[12]=233; Tfib[13]=377; Tfib[14]=610; Tfib[15]=987; Tfib[16]=1597; Tfib[17]=2584; Tfib[18]=4181; Tfib[19]=6765; Tfib[20]=10946; Tfib[21]=17711; Tfib[22]=28657; Tfib[23]=46368; Tfib[24]=75025; Tfib[25]=121393; Tfib[26]=196418; Tfib[27]=317811; Tfib[28]=514229; Tfib[29]=832040; Tfib[30]=1346269; Tfib[31]=2178309; Tfib[32]=3524578; Tfib[33]=5702887; Tfib[34]=9227465; Tfib[35]=14930352; Tfib[36]=24157817; Tfib[37]=39088169; Tfib[38]=63245986; Tfib[39]=102334155; Tfib[40]=165580141; Tfib[41]=267914296; Tfib[42]=433494437; Tfib[43]=701408733; Tfib[44]=1134903170; Tfib[45]=1836311903; Tfib[46]=2971215073; Tfib[47]=4807526976; Tfib[48]=7778742049; Tfib[49]=12586269025; Tfib[50]=20365011074; Tfib[51]=32951280099; Tfib[52]=53316291173; Tfib[53]=86267571272; Tfib[54]=139583862445; Tfib[55]=225851433717; Tfib[56]=365435296162; Tfib[57]=591286729879; Tfib[58]=956722026041; Tfib[59]=1548008755920; Tfib[60]=2504730781961; Tfib[61]=4052739537881; Tfib[62]=6557470319842; Tfib[63]=10610209857723; Tfib[64]=17167680177565; Tfib[65]=27777890035288; Tfib[66]=44945570212853; Tfib[67]=72723460248141; Tfib[68]=117669030460994; Tfib[69]=190392490709135; Tfib[70]=308061521170129; Tfib[71]=498454011879264; Tfib[72]=806515533049393; Tfib[73]=1304969544928657; Tfib[74]=2111485077978050; Tfib[75]=3416454622906707; Tfib[76]=5527939700884757; Tfib[77]=8944394323791464; Tfib[78]=14472334024676221; Tfib[79]=23416728348467685; Tfib[80]=37889062373143906; Tfib[81]=61305790721611591; Tfib[82]=99194853094755497; Tfib[83]=160500643816367088; Tfib[84]=259695496911122585; Tfib[85]=420196140727489673; Tfib[86]=679891637638612258; Tfib[87]=1100087778366101931; } //szukaczka najbliższego wyrazu po nowemu - wersja rekursywna int znajdz_najblizszy(int liczba, int beg=0, int end=88){ if (Tfib[beg]==liczba) return Tfib[beg]; if (Tfib[end]==liczba) return Tfib[end]; if ((beg-end)==2) if ((liczba-Tfib[beg])<(Tfib[end]-liczba)) return Tfib[beg]; else return Tfib[end]; if (Tfib[beg+(end-beg)/2]<=liczba) return znajdz_najblizszy(liczba, beg, end/2); else return znajdz_najblizszy(liczba, beg/2, end); } ////szukaczka najbliższego wyrazu po nowemu - wersja iteracyjna int znajdz_najblizszy2(int liczba, int beg=0, int end=88){ int a=0; while (a<50){ a++; if (Tfib[beg]==liczba) return Tfib[beg]; if (Tfib[end]==liczba) return Tfib[end]; if ((beg-end)==1 || (beg-end)==-1) if ((liczba-Tfib[beg])<(Tfib[end]-liczba)) return Tfib[beg]; else return Tfib[end]; if (Tfib[beg+(end-beg)/2]>=liczba) {end=beg+(end-beg)/2;} else {beg=beg+(end-beg)/2;} } } int abs(int x){ if (x<0) return -x; else return x; } //dość stara wersja szukaczki najbliższego wyrazu int qf (int x, int beg, int end){ int vbeg=fib(beg), vend=fib(end); if (vbeg==x) return vbeg; else if (vend==x) return vend; else if (end-beg==1){ int dxbeg=x-vbeg, dxend=x-vend; if (dxbeg<=dxend) return vbeg; else return vend; } else if (x>p;p>0;p--){ cin>>l; k=0; while (l!=0){ tmp=znajdz_najblizszy2(abs(l)); if (l<0) l+=tmp; else l-=tmp; k++; } cout<<">>>"<>q; return 0; }