Fibonacci, sume și determinarea minimului sau maximului

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Fibonacci e un exemplu pentru o idee mai generală: un termen se obține din cei de dinainte, deci nu trebuie să ții tot șirul.
• Suma, numărarea, minimul și maximul au aceeași formă: inițializezi, apoi actualizezi. Baremul le numește algoritmi de bază și le punctează separat.
• Toate apar la ambele specializări, de obicei în interiorul unei cerințe mai mari.

Urmează · 1 min

Șirul lui Fibonacci

6 min 3 întrebări la final

Fiecare termen e suma celor doi de dinainte: 1, 1, 2, 3, 5, 8, 13...

a=1;
b=1;
for(i=3;i<=n;i++)
{ c=a+b;
  a=b;
  b=c;
}

După buclă, b e al n-lea termen. Ordinea atribuirilor contează: dacă scrii a=b întâi fără c, pierzi valoarea veche a lui a.

Cât apare, de fapt? În cele 67 de lucrări C/C++ importate (2020–2027), cuvântul Fibonacci apare în doi itemi, amândoi la științele naturii, la I.5. Nu-l învăța ca pe o temă separată, ci ca pe un șablon: cum mergi înainte și cum mergi înapoi într-un șir.

Oficial: iunie 2021, varianta 1, SN, I.5

while(x>0)
{ z=y-x;
  y=x;
  x=z;
}
if(.........) z=1;
else z=0;

Enunțul spune că șirul are termenii 1, 1, 2, 3, 5, 8 și cere condiția cu care z e 1 dacă x și y (x<y) sunt termeni consecutivi. Bucla merge înapoi: dacă y e termenul curent și x cel de dinainte, atunci y-x e cel de dinaintea lui x.

Se ajunge la x=0, y=1, deci răspunsul e x==0 && y==1 (varianta c, 4 p). Simularea din 2023, I.5, are aceeași idee, cu altă condiție de oprire, și răspunsul x*y==1 (varianta c, 4 p).

Aceeași idee la III.3: sesiunea specială 2021, varianta 7, MI

Șirul 1, 3, 7, 13, 21, 31, 43... are f0=1 și fn=fn-1+2n. Se citesc doi termeni consecutivi, x și y, iar în bac.out se scriu toți termenii până la y, în ordine inversă. Pentru 21 și 31: 31 21 13 7 3 1.

Din y-x=2n afli poziția: n=(y-x)/2. Apoi cobori.

#include <iostream>
#include <fstream>
using namespace std;

int main()
{ ofstream g("bac.out");
  int x,y,n;
  cin>>x>>y;
  n=(y-x)/2;
  g<<y;
  while(n>=1)
  { y=y-2*n;
    g<<" "<<y;
    n=n-1;
  }
  g.close();
  return 0;
}

Barem III.3 (10 p): a) descriere coerentă 1 p și justificarea eficienței 1 p; b) operații cu fișiere 1 p, valori determinate 5 p, algoritm eficient 1 p, declarări, citire și corectitudine globală 1 p. Punctul de eficiență se dă „numai pentru un algoritm liniar care utilizează eficient memoria”. Baremul indică și o a doua soluție, cu termenul general fn=1+n(n+1).

Ai același tipar și la sesiunea specială 2026, III.3, rezolvată în lecția despre fișiere.

Urmează · 6 min

Sume

5 min

Începi de la 0 și aduni, pe rând, fiecare termen.

s=0;
for(i=1;i<=n;i++)
  s=s+i*(i+1);

Secvența calculează 1*2+2*3+...+n*(n+1); pentru n=4 obții 40. Acesta e un exemplu al meu, ca să vezi ce înseamnă termen general: i*(i+1) e formula termenului de pe poziția i, iar bucla le adună. Dacă suma poate fi mare, declară s cu un tip mai larg, long long.

Programa cere „sume cu termenul general dat”, dar în lucrările importate nu am găsit un item care să scrie o astfel de sumă direct. Suma apare altfel:

Oficial: două de la Subiectul I

August 2023, varianta 7, SN, I.5 cere o formulă pentru suma de la x la y. Suma până la y e y*(y+1)/2. Scazi suma până la x-1, adică x*(x-1)/2. Răspunsul e s=y*(y+1)/2-x*(x-1)/2; (varianta d, 4 p). Valoarea x trebuie să rămână în sumă, de aceea nu scazi x*(x+1)/2.

Sesiunea specială 2024, varianta 4, SN, I.5 cere ca, după citirea a 10 numere, s să fie ultima cifră a sumei lor. Răspunsul e (s+x)%10 (varianta c, 4 p). Varianta s%10+x%10 poate ajunge la 18, deci nu mai e cifră.

Urmează · 5 min

Minim și maxim

9 min

Ții minte cea mai bună valoare de până acum. La fiecare valoare nouă, o compari.

cin>>n>>x;
max=x;
for(i=2;i<=n;i++)
{ cin>>x;
  if(x>max) max=x;
}

Când nu știi câte valori urmează, cum e la fișiere, pornești de la o valoare în afara domeniului. Dacă numerele sunt din [1,9999], max=0 și min=10000 sunt alegeri sigure.

Oficial, baremul de la model 2027, III.3, numește asta „algoritm de bază pentru determinarea maximului dintr-o serie de valori, cu inițializarea și actualizarea rezultatului”.

Oficial: sesiunea specială 2025, varianta 6, MI, III.1

Subprogramul diviz primește n din [1,10⁹] și returnează cel mai mare divizor al lui n care e pătrat perfect. Pentru 72 returnează 36, pentru 16 returnează 16, pentru 15 returnează 1.

int diviz(int n)
{ int d,rez=1;
  for(d=2;d*d<=n;d++)
    if(n%(d*d)==0) rez=d*d;
  return rez;
}

Pătratele se parcurg crescător, deci ultimul găsit e cel mai mare. d*d nu depășește 10⁹, deci încape în int.

Barem: antet 2 p; valoare determinată 6 p, câte 2 p pentru algoritmul de maxim sau de ultimă valoare, identificarea unui divizor pătrat perfect, divizorii analizați; returnare 1 p; variabile locale și corectitudine globală 1 p.

Oficial: rezervă 2025, varianta 7, MI, III.3

Fișierul bac.in are cel mult 10⁶ numere din [1001,9999], cu ultima cifră nenulă. Fiecăruia i se inversează cifrele. Dintre valorile distincte se extrag: cel mai mic, apoi cel mai mare dintre cele rămase, apoi cel mai mic dintre cele rămase. Dacă nu există trei valori distincte, se afișează nu exista. Pentru 1114 3212 3217 2855 7309 2131 2131 1238 7893 se afișează 1312 9037 2123.

Ideea: nu trebuie să ții minte și să ordonezi toate valorile. Îți trebuie cele mai mici două și cea mai mare.

#include <iostream>
#include <fstream>
using namespace std;

int main()
{ ifstream f("bac.in");
  int x,y,m1=10000,m2=10000,mx=0;
  while(f>>x)
  { y=0;
    while(x!=0)
    { y=y*10+x%10;
      x=x/10;
    }
    if(y<m1)
    { m2=m1;
      m1=y;
    }
    else
      if(y>m1 && y<m2) m2=y;
    if(y>mx) mx=y;
  }
  f.close();
  if(m2<10000 && mx>m2)
    cout<<m1<<" "<<mx<<" "<<m2;
  else cout<<"nu exista";
  return 0;
}

• m2 se schimbă și când apare un minim nou: vechiul minim devine al doilea.
• Valoarea egală cu m1 nu schimbă nimic, deci dublurile sunt ignorate.
• mx se actualizează separat, la fiecare valoare. Dacă mx>m2, cele trei valori sunt distincte.
• m2 rămâne 10000 dacă nu există două valori distincte.

Urmează · 9 min

Ce se cere la BAC

2 mincum apare la examen

Urmează · 2 min

Greșeli care costă puncte

1 mincapcanele de evitat

• s sau max neinițializate. Baremul punctează explicit inițializarea.
• max=0 când pot apărea valori negative.
• Compararea cu >= în loc de >, când enunțul cere prima poziție.
• Toate valorile memorate și ordonate, când aveai nevoie doar de două sau trei: pierzi punctul de eficiență.
• m2 neactualizat la un minim nou: vechiul minim se pierde.
• Fibonacci cu altă numerotare. Enunțurile oficiale citate pornesc de la 1, 1. Citește de la ce termen se începe.

Urmează · 1 min