|
PROBLEME REZOLVATE
|
PAG. 4 / 4
|
Instrucțiunea for
CERINȚĂ
Se citeşte un număr natural. Se cere să se decidă dacă este
prim sau nu.
Exemplu. Citim
7, iar acesta este un număr prim. Citim
9. Acesta nu este număr prim!
REZOLVARE
Reamintim faptul că un număr natural este prim dacă şi numai dacă singurii divizori (numere naturale)
sunt
1 şi numărul testat. Astfel:
7 este prim pentru că singurii săi divizori sunt
1 şi
7,
iar numărul
9 nu este prim pentru că
3 este divizor al lui.
Ce trebuie să facem? Să testăm, pe rând, toate numerele naturale care pot fi divizori ai numărului citit (
nr),
iar dacă găsim unul care este divizor înseamnă că numărul nu este prim.
Care sunt numerele pe care le testăm?
Numărul
1 este divizor pentru orice număr, deci nu trebuie testat. Începem cu
2.
Ultimul număr testat va fi
nr//2. De ce?
Exerciţiu. Cunoaşteţi o metodă care permite să se testeze şi mai puţine numere?
DETALII
Observăm că am folosit o variabilă logică numită
divizor. Aceasta este iniţializată cu valoarea
False.
Dacă dintre numerele testate există cel puţin un divizor, variabila va lua valoarea
True, altfel rămâne
cu valoarea iniţială. Cineva ar putea întreba: dar dacă numărul are mai mulţi divizori, ce valoare
va reţine variabila
divizor? Atunci când a fost găsit primul divizor, variabila divizor va reţine
True.
Dacă am mai găsit unul, variabilei i se atribuie din nou
True. Important este faptul că
la sfârșit aceasta va avea valoarea
True.
Procedeul este des folosit în programare. O variabilă are o anumită valoare inițial.
Dacă la toate testele care se fac nu se îndeplineşte o anumită condiţie, variabila rămâne
cu valoarea iniţială. Altfel, aceasta va reţine o nouă valoare. În final, se va testa valoarea reţinută de variabilă.
Pentru exemplu, am lucrat pornind de la ipoteza că numărul citit este prim. În cazul în care există
un divizor (dintre cei căutaţi), numărul nu va fi prim.
Aţi observat faptul că algoritmul are o deficienţă?
Dacă am găsit deja un divizor, este clar faptul că numărul nu este prim.
Ce rost are să fie testaţi
ceilalţi posibili divizori? De exemplu, dacă numărul citit este
100. Primul număr testat este
2, iar
acesta este divizor. Din acest moment se poate trage concluzia că numărul citit nu este prim.
Cu toate acestea, algoritmul testează toate numerele până la
50... Ce avem de făcut pentru a
remedia deficienţa arătată? Deocamdată lăsăm problema deschisă.
Vom reveni asupra ei curând.
Secțiunea s-a încheiat acum.
Cărțile editurii noastre
O parte dintre manualele și culegerile de probleme se găsește și [
în format electronic]
securizat sub formă
de fișier *.pdf.
"
O cameră fără cărţi este ca un corp fără suflet."
(G. K. Chesterton)
Cursanții au mai cumpărat ...
[
vezi lista completă a cărților]
