Lista de probleme 66

Fibonacci, un celebru matematician italian din Evul Mediu, a descoperit un șir de numere naturale cu multiple aplicații, șir ce-i poartă numele:

$Fibonacci(n)=\{\begin{array}{ll}1& \text{dacă }n=1\text{ sau }n=2\\ Fibonacci(n-1)+Fibonacci(n-2)& \text{dacă }n>2\end{array}$

Fascinat de șirul lui Fibonacci, și mai ales aplicațiile acestui șir în natură, Iccanobif, un matematician în devenire, a creat un șir si el un care-i poartă numele:

$Iccanobif(n)=\{\begin{array}{ll}1& \text{dacă }n=1\text{ sau }n=2\\ răsturnat(Iccanobif(n-1))+răsturnat(Iccanobif(n-2))& \text{dacă }n>2\end{array}$

Obținându-se astfel șirurile:

• Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
• Iccanobif: 1, 1, 2, 3, 5, 8, 13, 39, 124, 514, 836, …

Iccanobif, se întreabă acum, ce număr are mai mulți divizori numere naturale: al n-lea termen din șirul Fibonacci sau al n-lea termen din șirul său.

Scrieți un program care să citească un număr natural n și să afișeze:

a) al n-lea termen din șirul lui Fibonacci și numărul său de divizori
b) al n-lea termen din șirul lui Iccanobif și numărul său de divizori

Se consideră Șirul lui Fibonacci cunoscut prin relația de recurență: $F_1=1$; $F_2=1$; $F_i=F_{i–2}+F_{i–1},i\ge 3$.

Pentru n perechi de numere x, y să se afișeze numărul de perechi pentru care numerele $F_x$ și $F_y$ sunt prime între ele.

Lumea este în pericol. Încălzirea globală are efecte profunde în cele mai diferite domenii. Ea determină apariția extremelor climatice, topirea ghețarilor, ridicarea nivelului mărilor și, cel mai grav, dispariția a numeroase specii de animale. Cercetătorii au observat că cele mai afectate sunt furnicile.

Pentru a stabili cât de rapid este procesul de dispariție, ei și-au propus să le studieze timp de n zile, notând în fiecare zi numărul de furnici lucrătoare care ies după hrană. Ei au constatat că ele sunt afectate dacă, în zile consecutive, numărul de divizori ai numărului de furnici lucrătoare descrește. Vor lua în considerare doar perioadele de cel puțin două zile consecutive de descreșteri.

Pentru finalizarea studiului, trebuie să știe câte astfel de perioade au existat. Pentru că la calculele matematice pot greși, vă roagă să-i ajutați.

O persoana are de urcat n trepte. Aflaţi in câte moduri poate urca cele n trepte.

Se consideră o expresie aritmetică fără paranteze, în care operanzii sunt cifre, iar operatorii sunt + sau −. Să se evalueze expresia dată.

Se dau n numere naturale. Doar unul are frecvență impară. Să se identifice acel număr.

Georgiana a mai primit o problemă de la doamna profesor. Se dau n triplete de forma m, b, r, iar pentru fiecare triplet Georgiana trebuie să afle care este cel mai mic număr natural format cu m cifre, care împărţit la b dă restul r.

Se dau n şiruri, fiecare şir fiind format din m numere. Să se determine cel mai mare număr din fiecare şir. Să se determine suma numerelor fiecărui şir.

Fiind date n - 1 numere de la 1 la n, să se găseasca numărul lipsă.

Se consideră operația : {1; 2} → {1; 2}, astfel încât 1 = 2, 2 = 1. Operația se extinde asupra oricărei secvențe formate cu cifre de 1 și 2, de exemplu 1211212121 =2122121212.
Se consideră șirul infinit s format cu cifre de 1 și 2, generat incremental prin extindere după următoarea regulă de concatenare:
s1 = 1221, s2 = 1221211221121221, … , sk+1 = sk sk sk sk, …, pentru orice număr natural nenul k.

Să se scrie un program care pentru un n număr natural nenul cunoscut determină și afișează a n-a cifră a șirului s, astfel încât numărul de pași ai programului să fie proporțional cu log2(n) (complexitate timp logaritmică în funcție de n).