Lectia 1 Informatica - noţiuni introductive Definiţie 1: Informatica este ştiinţa care se ocupă cu prelucrarea informaţiilor cu ajutorul calculatorului. Informaţiile prelucrate pot avea diferite tipuri (valori numerice intregi sau reale, şiruri de caractere, imagini, sunete, filme, etc.). În prezent, calculatorul este implicat din ce în ce mai mult în viaţa noastră, fiind utilizat în diferite aspecte după cum urmează: pentru gestionarea informaţiilor: accesul rapid şi exact la anumite informaţii care ne interesează la un anumit moment(de exemplu: bazele de date); pentru rezolvarea unor probleme din domenii diferite cum ar fi matematica, fizica, chimia, etc; pentru comunicare: in prezent comunicarea rapida face parte din viata de zi cu zi, utilizând frecvent reteaua internet prin programele specifice (e-mail, chat, etc.); pentru păstrarea amintirilor: realizarea de albume foto virtuale şi arhive cu filme; pentru relaxare: jocuri, filme, muzică. În această carte vom învăţa să rezolvăm probleme cu ajutorul calculatorului utilizând limbajul de programare C++. Orice program are la bază un algoritm de rezolvare. Definiţie 2: Algoritmul 1 este alcătuit dintr -o succesiune de etape, numite paşi, care trebuie parcurse într- o anumită ordine astfel încât plecând de la datele iniţiale ale problemei, într -un timp finit sa ajungem la rezultatul dorit. Algoritmul este noţiunea fundamentală a informaticii. Totul este construit în jurul algoritmilor (şi al structurilor de date, cum ar fi listele sau grafurile). Definiţie 3: Descrierea unui algoritm de rezolvare a unei probleme sau a unei situaţii date într -un limbaj de programare se numeste program sau cod sursă. Cele mai importante proprietăţi ale unui algoritm sunt următoarele: Corectitudinea - este proprietatea algoritmului de a furniza o soluţie corectă a problemei date. În acest sens este de dorit ca algoritmii să se bazeze pe fapte şi relaţii matematice demonstrabile. Caracterul univoc sau deterministic - plecând de la un set de date iniţial anume, rezultatul este unic, sau altfel spus, repetarea execuţiei algoritmului duce întotdeauna la aceleaşi rezultate. Generalitatea - este proprietatea unui algoritm de a rezolva o clasă sau categorie de probleme, şi nu doar o singură problemă particulară. Spre exemplu, un algoritm care rezolvă doar ecuaţia x 2 + 5x − 6 = 0 este mai puţin general decât unul care rezolvă ecuaţia de gradul II care are următoare formă generală ax 2 + bx + c = 0, oricare ar fi valorile lui a,b,c. 1 Cuvântul are la origine numele matematicianului persan Al-Khwarizmi Date de intrare (Ce se dă) Date de iesire (Ce se cere) Program C++ (scris pe baza unui algoritm de rezolvare)
Transcript
Lectia 1 Informatica - noţiuni introductive
Definiţie 1: Informatica este ştiinţa care se ocupă cu prelucrarea informaţiilor cu ajutorul
calculatorului. Informaţiile prelucrate pot avea diferite tipuri (valori numerice intregi sau reale,
şiruri de caractere, imagini, sunete, filme, etc.).
În prezent, calculatorul este implicat din ce în ce mai mult în viaţa noastră, fiind utilizat în
diferite aspecte după cum urmează:
pentru gestionarea informaţiilor: accesul rapid şi exact la anumite informaţii care ne
interesează la un anumit moment(de exemplu: bazele de date);
pentru rezolvarea unor probleme din domenii diferite cum ar fi matematica, fizica,
chimia, etc;
pentru comunicare: in prezent comunicarea rapida face parte din viata de zi cu zi,
utilizând frecvent reteaua internet prin programele specifice (e-mail, chat, etc.);
pentru păstrarea amintirilor: realizarea de albume foto virtuale şi arhive cu filme;
pentru relaxare: jocuri, filme, muzică.
În această carte vom învăţa să rezolvăm probleme cu ajutorul calculatorului utilizând
limbajul de programare C++. Orice program are la bază un algoritm de rezolvare.
Definiţie 2: Algoritmul1 este alcătuit dintr-o succesiune de etape, numite paşi, care trebuie
parcurse într-o anumită ordine astfel încât plecând de la datele iniţiale ale problemei, într-un timp
finit sa ajungem la rezultatul dorit.
Algoritmul este noţiunea fundamentală a informaticii. Totul este construit în jurul
algoritmilor (şi al structurilor de date, cum ar fi listele sau grafurile).
Definiţie 3: Descrierea unui algoritm de rezolvare a unei probleme sau a unei situaţii date într-un
limbaj de programare se numeste program sau cod sursă.
Cele mai importante proprietăţi ale unui algoritm sunt următoarele:
Corectitudinea - este proprietatea algoritmului de a furniza o soluţie corectă a problemei
date. În acest sens este de dorit ca algoritmii să se bazeze pe fapte şi relaţii matematice
demonstrabile.
Caracterul univoc sau deterministic - plecând de la un set de date iniţial anume,
rezultatul este unic, sau altfel spus, repetarea execuţiei algoritmului duce întotdeauna la
aceleaşi rezultate.
Generalitatea - este proprietatea unui algoritm de a rezolva o clasă sau categorie de
probleme, şi nu doar o singură problemă particulară. Spre exemplu, un algoritm care
rezolvă doar ecuaţia x2 + 5x − 6 = 0 este mai puţin general decât unul care rezolvă ecuaţia
de gradul II care are următoare formă generală ax2 + bx + c = 0, oricare ar fi valorile lui
a,b,c.
1 Cuvântul are la origine numele matematicianului persan Al-Khwarizmi
Date de intrare (Ce se dă)
Date de iesire (Ce se cere)
Program C++ (scris pe baza unui algoritm de rezolvare)
Claritatea - proprietatea algoritmului de a descrie cu exactitate şi fără ambiguităţi paşii
care trebuiesc parcurşi în rezolvarea problemei.
Verificabilitatea - acea proprietate a algoritmilor care permite ca fiecare pas să poată fi
verificat într-un timp rezonabil de către om, folosind mijloace de validare de încredere.
Optimalitatea - proprietatea unui algoritm de a se termina după un număr minim de paşi.
Spre exemplu, dacă se cere să se calculeze suma primelor n numere naturale, putem
aplica formula de calcul, şi astfel algoritmul se termină într-un singur pas, pe când dacă
am aduna toate numerele de la 1 la n, el s-ar termina abia în n paşi, şi deci nu ar fi optim.
Finitudinea - este proprietatea algoritmului de a se termina într-un număr finit de paşi.
Există şi algoritmi care nu se termină într-un număr mărginit de paşi, dar aceştia se
numesc "metode algoritmice".
Eficienţa - este proprietatea unui algoritm de a se termina nu numai într-un număr finit, ci
şi "rezonabil" de paşi, chiar dacă acesta nu este cel mai mic posibil (nu este optim).
Algorimul este ineficient şi dacă rezultatul se obţine într-un timp mai lung decât cel dorit
sau permis.
Existenţa unei intrări (datele de prelucrat). Întrucât operatorii se aplică unui operand (sau
şi mai multor operanzi deodată), este de neconceput un algoritm fără niciun operand.
Intrările permise formează împreună un set (mulţime) specific de obiecte sau valori, care
se numeşte "domeniul" algoritmului.
Existenţa unei ieşiri (rezultatele). Este de neconceput un algoritm care nu are nicio ieşire,
deoarece în acest caz intră în discuţie însăşi utilitatea sa.
Operaţiile care apar în cadrul unui algoritm sunt:
Operaţii de intrare ieşire: datele de intrare se vor citi de la tastatră sau din fişiere text şi
ele reprezintă valorile iniţiale cu care se incepe rezovarea unei probleme. Datele de ieşire
reprezintă rezultatul problemei după parcurgerea algoritmului şi aceste fie vor fi afişate
pe ecran, fie vor fi scrise în fişiere text.
Operaţia de atribuire: reprezintă operaţia în urma căreia valoarea unei expresii
(matematice, logice sau relaţionale) este memorată într-o variabilă
Operaţia de decizie: determină valoarea de adevăr a unei expresii logice şi în funcţie de
rezultatul obţinut se continuă execuţia programului pe una din cele doua ramificatii
posibile(adevărat sau fals).
Etapele rezolvării unei probleme cu ajutorul calculatorului
1. Analiza problemei: presupune:
citirea şi analiza cu atenţie a enunţului problemei date pentru identificare datelor de
intrare (datele iniţiale ale problemei). (Ce se cunoaste ? )
Înţelegerea şi identificarea rezultatului aşteptat (stabilirea datelor de iesire). (Ce se
cere?)
Alegerea strategiei de rezolvare a problemei (identifiarea algoritmului optim de
rezolvare a problemei) (Cum rezolv?) Pentru rezolvarea unei probleme date pot exista
mai multe metode. În acest moment trebuie identificat care este cel mai optim mod de
rezolvare a problemi astfel încât în cel mai scurt timp şi cu cele mai puţine resurse să
obţinem rezultatul dorit. Analiza timpului de lucru a unui program se numeste
complexitate1, dar pentru acest subiect vom discuta mai pe larg intr-un capitol
separat.
2. Descrierea în limbaj natural a modului de rezolvare propus, stabilirea tipurilor de
informaţii care trebuie prelucrate precum şi a tipurilor de rezultate aşteptate. Limbajul
natural descrie în termeni largi etapele propuse pentru rezolvarea problemei date.
3. Descrierea algoritmului în limbaj pseudocod: Limbajul pseudocod este un limbaj
intermediar între limbajul natural şi limbajul de programare. În aceasta etapă se stabilesc
paşii de algoritm, tipurile datelor de intrare, de manevră şi de ieşire, se identifică
condiţiile care impun şi se scriu în expresii matematice care sunt uşor de interpretat de
calculator (calculatorul nu face presupuneri si nici nu ghiceşte ce doritţi dumneavoastră ci
doar execută rapid comenzile pe care le-a primit). Un algoritm scris în limbaj pseudocod
nu este un program care poate fi rulat direct pe calculator, dar poate si transcris uşor într-
un limbaj de programare ţinând cont de vocabularul, semantica si sintaxa limbajului de
programare. În această carte vom folosi un limbaj pseudocod scris în limba română
(pentru a fi mai uşor de inteles logica algoritmicii). Limbajul pseudocod se va baza
implementarea ideii de rezolvare într-un format apropiat de limbajul C++, dar care nu
pune accent pe sintaxa riguroasă care trebuie respectată atunci când scrii într-un limbaj de
programare.
4. Scrierea codului sursă: Aceasta este etapa în care algoritmul scris în limbaj pseudocod
este transcris în limbaj de programare, ţinând cont de regulile impuse de acesta şi
repectând semnificaţia construcţiilor sintactice corecte impuse de limbajul de
programare.
5. Corectarea erorilor sintactice: Corectarea unui cod sursă din punct de vedere sintactic se
numeste compilare2. În aceasta etapă programul este verificat, iar eventualele greşeli sau
omisiuni ale respectării regulilor sintactice sau semantice sunt semnalate de compilator
print-o listă de erori. Cel care a scris programul are obligaţia să corecteze aceste erori
folosindu-se de masajele de eroare afişate precum şi de cunoştinţele sale. Mesajul de
eroare afişat, care semnalează o eroare de compilare, nu indică întotdeauna corect
modalitatea de corectare (el este mai mult informativ). Erorile de eroare vor fi căutate
începând de la poziţia semnalat de compilator sau de la poziţia semnalată spre începutul
programului. O serie de greşeli frecvent întâlnite la începători sunt generate de definirea
eronată a tipurilor de date care vor contine rezultatele. Dacă rezultatul aşteptat depăşeşte
ca valoare domeniul de definiţie stabilit atunci aceasta greşeala nu va fi identificată de
către compilator, deci nu va fi corectată in acestă etapă. La execuţia programului vom
avea însă surpriza unor rezultate neaşteptate, chiar daca soluţia de rezolvare găsită este
corectă si programul scris nu are greseli de compilare.
6. Testarea programului: În această etapă se verifică corectitudinea rezolvării problemei
prin analiza rezultatului obţinut pentru diferite valori ale datelor de intrare. Tot aici se
identifică si eventualele erori de gândire, care apar prin alegerea unui algoritm de
rezolvare greşit. În această etapă trebuie indentificate seturi de date de intrare numite şi
cazuri limită pentru care programul s-ar putea bloca sau ar genera rezultate greşite
datorită unei neglijenţe în etapa de analiză şi implementare a programului. 1 Complexitatea unui algoritm este determinată ţinând cont de spaţiul de memorie utilizat (complexitate spaţiu) si de timpul de obţinere a rezultatului (complexitate timp). Prin complexitate
spaţiu înţelegem dimensiunea spaţiului de memorie utilizat de program. Un program necesită un spaţiu de memorie constant, independent de datele de intrare, pentru memorarea codului său, a constantelor, a variabilelor simple şi a structurilor de date de dimensiune constantă alocate static şi un spaţiu de memorie variabil, a cărui dimensiune depinde adesea de datele de intrare de cerinţele problemei de rezolvat şi din spaţiul de memorie necesar apelurilor de proceduri şi funcţii. Prin complexitate timp înţelegem timpul necesar execuţiei programului. Înainte de a evalua timpul necesar execuţiei programului ar trebui să avem informaţii detaliate despre sistemul de calcul folosit.
2 Un compilator este un program (sau set de programe) care traduce textul scris într-un limbaj de programare (limbajul sursă – low level) într-un alt limbaj de calculator (numit limbaj ţintă-
hight level). Sursa originală se numeşte de obicei cod sursă iar rezultatul cod obiect. În general codul sursă este compilat pentru a crea un program executabil .
Limbajul pseudocod şi schema logică
Asa cum am precizat anterior pseudocodul este o forma de reprezentare a algoritmilor şi
ca orice limbaj foloseşte un grup de cuvinte cheie (citeşte, scrie, dacă, atunci, cât timp, pentru,
etc.), organizate în construcţii sintactice care traduc structurile fundamentale1, dar neavând o
sintaxă rigidă ca un limbaj de programare. Limbajul pseudocod lasă la libera alegere a
utilizatorului introducerea unor notaţii care să permită o mai buna exprimare.
Schema logică este un mijloc de descriere a algoritmilor prin reprezentare grafică.
Fiecărui tip de operaţie îi este consacrată o figură geometrică (un bloc tip) în interiorul căreia se
va înscrie operaţia din pasul respectiv, iar succesiunea operaţiilor este indicată prin săgeţi.
Blocuri utilizate în realizarea schemelor logice:
Pentru întocmirea unei scheme logice corecte sunt necesare respectarea unor anumite
reguli după cum urmează:
Orice schemă logică se întocmeşte de sus în jos;
Legătura intre blocurile schemei se face numai prin săgeţi, pentru a stabili sensul de
parcurgere;
În cazul întâlnirii unui bloc de decizie se precizează deasupra liniilor de legătură când
expresia
1 Structurile fundamentale din programarea structurată sunt structura liniara, structura alternativa şi structurile repetitive.
START STOP Marchează începutul / sfărşitul unui algoritm reprezentat în schemă logică
Se utilizează pentru implementarea operaţiilor de intrare / ieşire
Se utilizează pentru scrierea condiţiilor în cazul structurilor alternativă sau repetitivă
Se utilizează pentru scrierea operatiilor de atribuire (atunci când o variabilă primeste o valoare)
Se utilizează pentru conectarea liniilor care leagă diferitele figuri geometrice şi marchează un punct de intersecţie.
Legăturile dintre blocurile schemei logice se realizează numai prin intermediul săgetilor, pentru a stabili sensul de parcurgere al algoritmului.
Aplicaţii practice
1. Un algoritm este un limbaj de programare?
a. Adevărat
b. Fals
2. Cu ajutorul unui calculator se pot prelucra următoarele tipuri de informaţii:
a. Imagini
b. Documente
c. Numere
d. Cărţi
3. Descrierea unui algoritm se poate face prin:
a. Limbaj natural
b. Limbaj de programare
c. Limbaj pseudocod
d. Nici un răspuns nu e corect
4. Limbajul pseudocod este un limbaj de programare?
a. Fals
b. Adevărat
5. Datele de intrare sunt si date de ieşire?
a. Adevărat
b. Fals
6. Complexitatea unui cod sursa a unui program este masurată prin numărul de linii de cod
scrise?
a. Adevărat
b. Fals
7. Corectarea erorilor de compilare implică automat si corectarea erorilor de gândire?
a. Adevărat
b. Fals
8. Datele de ieşire reprezintă acele valori obţinute la terminarea unui algoritm?
a. Adevărat
b. Fals
9. Limbajul pseudocod este:
a. Un cod fals
b. Un limbaj intermediar de scriere a algoritmilor şi care face trecerea de la limbajul
natural la cel de programare
c. Un limbaj nefolositor
d. Nici un răspuns nu e corect
10. Pentru a verifica corectitudinea funcţionării unui program acesta trebuie testat cu:
a. Valorile pentru care a fost gândit în etapa de analiză
b. Cu orice fel de valori
c. Cu valori speciale identificate pentru cazurile limită
12. Precizaţi care este diferenţa între scrierea algoritmului în limbaj pseudocod faţă de
limbajul de programare. (Precizaţi avantajele şi dezavantajele)
13. Care sunt deosebirile dintre erorile de compilare si erorile de gândire?
14. Definiti următorii termeni:
a. Complexitatea unui algoritm
b. Operaţia de compilare
c. Limbaj de programare
d. Limbaj natural
Lectia 2. Elemente de bază în reprezentarea algoritmilor Una dintre principalele noţiuni care intervin în programare este noţiunea de dată.
Definiţie 1: Data este o informaţie care se prelucrează cu ajutorul calculatorului. Datele se pot
clasifica:
a. După locul în care sunt prelucrate:
date de intrare - reprezintă un set de informaţii iniţiale care sunt cunoscute şi
care reprezintă punctul de plecare în rezolvarea problemei.
date de manevră – se utilizează în interiorul algoritmului pentru a memora la
un anumit moment valori intermediare necesare procesului de rezolvare al
problemei date
date de ieşire - sunt rezultatele aşteptate şi care sunt obţinute prin prelucrarea
datelor de intrare cu ajutorul algoritmului dat.
b. După tipul informaţiilor memorate:
date numerice – conţin ca valori numere întregi sau reale
date logice – pot sa conţină ca valoare doar: True sau False
date de tip caracter – conţin ca valoare un singur caracter din cele 256 din
codul Ascii1
date structurate – sunt acele date care se compun pe baza unor reguli precise
din datele simple(numere, caractere, logice)
c. După felul în care îşi schimbă valoarea pe parcursul unui algoritm
1. variabile - valorile se modifică pe masură ce algoritmul se execută
2. constante- valorile lor rămân constante pe toata durata de execuţie a
programului
O variabilă se caracterizează prin:
numele variabilei - este format din unul sau mai multe caractere (litere mari sau
mici ale alfabetului englez, numere si caracterul underline) cu condiţia ca primul
caracter nu fie cifră.
tipul variabilei – stabileste mulţimea de valori posibilă pentru variabila respectivă
precum si setul de operaţii permise; un tip de dată poate fi elementar (reprezinta
date de tip numeric-întreg sau real şi nenumeric-caracter, logic), structurat ( sunt
obţinute prin gruparea tipurilor elementare de date după reguli bine precizate ) sau
referinţă (permit referirea la date alocate dinamic în timpul execuţiei
programului)
valoarea variabilei – reprezintă valoarea efectivă pe care o are o variabilă la un
moment dat în interiorul codului sursă. într-un moment dat o variabilă are
întotdeauna o singură valoare, valoarea ei modificându-se doar în urma unei
operaţii de atribuire sau a unei operaţii de citire de la tastatură sau din fişier text.
adresa variabilei – reprezintă locaţia fizică din memoria calculatorului în care se
păstrează valoarea unei variabile. în majoritatea situaţiilor adresele variabilelor
sunt invizăbile pentru utilizator.
Pentru memorarea informaţiilor în memoria internă a calculatorului se foloseste sistemul
binar, care are doar două valori 0 si 1.
1 ASCII este acronimul pentru American Standard Code for Information Interchange, ceea ce înseamnă "Codul Standard
American pentru Schimbul de Informaţii". ASCII reprezintă un sistem de codificare a caracterelor bazat pe alfabetul englez. Codurile ASCII reprezintă caractere text pentru calculatoare, echipamente de comunicaţie şi echipamente care lucrează cu text.
Setul de caractere ASCII conţine 128 de caractere: litere mari şi mici, numere, elemente de punctuaţie şi coduri de control.
Definiţie 2: Unitatea elementară de memorare a informaţiilor în memoria internă a calculatorului
este bit-ul, care poate avea doar valoarea 0 sau valoarea 1( modelarea fizică a sistemului binar
este comutatorul.0 – nu trece „curent electric”, 1- trece „curent electric”).
K1↔1 K1↔0
A B A B
a. comutatorul K1 închis, b. comutatorul K1 deschis
echivalentul valorii 1 echivalentul valorii 0
trece „curent electric” nu trece „curent electric”
de la punctul A la B de la punctul A la B
Definiţie 3: Un octet(byte) este alcătuit dintr-un grup de 8 biţi şi orice informaţie poate fi
memorată utilizând întotdeauna un număr întreg de octeţi, măsurându-se în multipli de
octeţi(1024 octeţi= 1Kb, 1024 Kb=1Mb, etc).
Reprezentarea datelor numerice în memoria calculatorului
În funcţie de valoarea pe care o au datele numerice ele pot reprezenta numere naturale,
numere întregi sau numere reale, iar pentru fiecare astfel de număr se vor aloca în memorie un
număr diferit de octeţi.
Reprezentarea numerelor naturale
Formatul de reprezentare întreg fără semn nu presupune nimic în plus decât trecerea de la
baza 10 la baza 2. În aceasta reprezentare putem scrie spre exemplu:
numărul (188)10 = (10110110)2
(1·102+8·10
1+8·10
0)10 = (0·2
0+1·2
1+1·2
2+0·2
3+1·2
4+1·2
5+0·2
6+1·2
7)2
O reprezentare a unui număr întro bază de numeraţie notata B foloseste doar cifre din
inteervalul [0, B-1]. Trecerea unui numar de la o bază la alta presupune aflarea unei secvente
unice de resturi conform algoritmului următor:
numărul se imparte la baza si se retine restul obtinut. Acesta constituie ultima
cifra din reprezentare in acea baza.
câtul obtinut in urma acestei prime impartiri este din nou imparti la baza si se
retine iarasi restul. Acest rest constituie a doua cifra, in ordinea de la dreapta la
stanga, a reprezentarii in baza aleasa.
algoritmul continuă până când câul obţinut este mai mic decât baza. Acest cât va
reprezenta cea mai semnificativă cifră a numărului în baza data.
Tabelul următor prezinta paşii acestui algoritm pentru trecerea numarului 25 în baza 2:
Nr. baz
a
25:2 25 2 (25)10=(11001)2
rest 1 12 2
0 6 2
0 3 2
1 1 2
1 0
Reprezentarea în baza 2 a numărului 25 se obţine luând în ordine inversă resturile
împarţirii la 2.
Pentru a putea memora un număr natural în memoria internî a claculatorului se pot aloca
1,2 sau 4 octeţi. Pe un octet se pot memora numere naturale cuprinse în intervalul [0..255]
bit: 7 6 5 4 3 2 1 0
cea mai mică valoare naturală reprezentată pe un octet este 0: 0 0 0 0 0 0 0 0
adică numărul natural 0=0·20+0·2
1+0·2
2+0·2
3+0·2
4+0·2
5+0·2
6+0·2
7.
bit: 7 6 5 4 3 2 1 0
cea mai mare valoare naturală reprezentată pe un octet este 0: 1 1 1 1 1 1 1 1
adică numărul natural 255=1·20+1·2
1+1·2
2+1·2
3+1·2
4+1·2
5+1·2
6+1·2
7= 1+2+4+8+16+32+64+128
Propun ca exerciţiu de calcul reprezentarea intervalului de numere naturale care pot fi
memorate pe 2 octeţi.
De exemplu, numerele întregi reprezentate pe 32 bits(4 octeţi) pot lua valori cuprinse în
intervalul [-2147483648, 2147483647]. Adunarea, scăderea şi înmulţirea acestor numere
returnează rezultate exacte atâta vreme cât nu se depăşesc limitele precizate. În cazul în care
apare o depasire (overflow) rezultatul este imprevizibil. Rezultatul împaţirii numerelor întregi
reprezentate este tot un număr întreg obţinut prin rotunjirea rezultatului corect la întregul imediat
mai mic.
Reprezentarea numerelor întregi
Numerele întregi se reprezintă în memorie în complement faţă de 2. Reprezentarea în
complement fata de 2 este folosită de majoritatea procesoarelor actuale. Ideea acestei
reprezentări se întelege pe baza observaţiei simple că numărul x adunat cu numărul -x trebuie să
dea întotdeauna valoarea 0. Întrebarea ce se pune este cum se scrie -x, deoarece pentru numerele
întregi pozitive se păstreză regula de la paragraful precedent. Cel mai simplu este să folosim un
bit pentru reprezentarea semnului (de ex., 0 înseamnă plus şi 1 înseamnă minus) si ceilal ţi (n-1)
biţi pentru reprezentarea valorii absolute.
Numerele negative se reprezintă astfel:
plecăm de la reprezentarea în baza 2 a opusului (care este pozitiv),
inversăm toate cifrele până la ultimul 1 (exclusiv)
Exemple:
(22)10 = (00010110)2, număr pozitiv ( -22)10 = (11101010)2, număr negativ
Primul bit (cel scris cu culoare roşie) se mai numeste bit de semn deoarece el indică
semnul numarului (este 0 dacă şi numai dacă numărul este pozitiv). Avantajul acestei
reprezentări este urmatorul: algoritmii de adunare şi de scadere a două numere reprezentate în
cod complementar sunt identici cu algoritmii de adunare si de scadere pentru numere pozitive
reprezentate in baza 2.
Pe un octet se pot memora numere naturale cuprinse în intervalul [-128..+127]
Reprezentarea numerelor reale
Modul în care numerele reale sunt reprezentate în memorie este reglementat de IEEE1
Floating Point Standard2, un set de reguli care ne ajută în prezicerea gradului de inexactitate a
rezultatelor calculelor aritmetice. Una dintre sursele de erori în calculul ştiinţific este eroarea de
1 Institute of Electric and Electronic Egineering 2 IEEE Floating Point Standard — standardul IEEE de reprezentare a numerelor în virgulă mobilă este un set de convenţii de reprezentare şi de operare a numerelor reale în memoria calculatorului şi care are câteva obiective:
Creşterea preciziei operaţiilor cu numere reale.
Standardizarea operaţiilor cu numere reale pe toate platformele de calcul.
Stabilirea felului în care sunt tratate erorile.
rotunjire datorată calculelor aritmetice inexacte efectuate de calculator. Eroarea de rotunjire face
parte din categoria erorilor inevitabile dar consecinţele sale diferă de la o problema la alta, de la
o strategie de rezolvare la alta. O singura operaţie aritmetică efectuată de calculator cu numere
reale va da de cele mai multe ori un răspuns cu un grad relativ mare de precizie.
Pentru reprezentarea numerelor în calculator se folosesc două formate de reprezentare:
formatul cu virgulă fixă:
± partea întreagă. partea zecimală de exemplu:12.351 sau -54.789
formatul cu virgulă mobilă: s-a impus datorită necesităţii de a reprezenta în sistemele de
calcul numere foarte mari sau foarte mici cu un grad de precizie ridicat. La baza acestui
mod de reprezentare se situează reprezentarea numerelor reale cu ajutorul mantisei(indică
ordinul de mărime al numărului printr-o putere a bazei) şi exponentului exponentul
(mărimea numărului în cadrul ordinului respective):
± mantisă·E±exponent
.
Mantisa în reprezentarea normalizată este un număr subunitar, E reprezintă valoarea
bazei 10, iar exponentul este un număr întreg care stabileşte valoarea numărului real. De
exemplu: numărul real -102.224 scris în virgulă fixă va fi egal cu 0.102224·E3 în virgulă
//definiţii de tipuri de date şi variabile globale
//definiţii de funcţii utilizator
void main()
{ //declaratii locale în functia main
// instructiuni c++
}
Unde:
Directivele preprocesor sunt fişiere librării memorate separat si care au extensia .h.
Astfel:
iostream.h este un fisier antet (header) care este utilizat pentru gestionarea intrările şi
ieşirile implicite de date (datele de intrare se vor prelua împlicit de la tastatura, si
datele de ieşire vor fi afişate în mod implicit pe monitorul) . Librăria iostream.h face
parte din biblioteca implicită a limbajului C++.
În funcţie de alte obţiuni ale utilizatorului se vor insera în codul sursă si alte fişiere antet cum ar
fi:
conio.h - este un vechi fişier antet, folosit de vechile compilatoare C pentru a realiza
interfata utilizatorului(cele mai folosite funcţii definite în biblioteca conio.h sunt
clrscr()-sterge ecranul cu toate datele afişate în urma execuţiei unui program,
getch() citeste de la tastaură un caracter, dar caracterul citit nu este afisat pe ecran,
se utilizează în situaţia în care dorim sa oprim în anumite puncte un program în
execuţie pentru a putea vedea şi analiza informaţiile afisate; după apasarea oricărei
taste programul îşi continuă execuţia cu următoarea instrucţiune)
math.h – este un fişier care face din biblioteca standard a limbajului C, unde sunt
definite funcţiile matematice (cum ar fi radical din x –sqrt(x), ridicare la putere
pow(a,b), modulul unui număr abs(a),funcţiile trigonometrice, etc.
fstream.h-este un fişier în care sunt definite funcţiile de bază pentru lucru cu fişiere
text. Stream-urile implicite tastaura şi monitorul se vor schimba în fişiere text de
intrare sau de iesire.
După includerea în program a fişierelor header urmează o secţiune rezervată definirii de
tipuri de date şi variabile globale.
Definiţie 2: Definirile globale de variabile se fac la începutul programului si acestea vor fi
cunoscute în toate funcţiile din program.
Definiţie 3: Definirile locale de variabile se fac în cadrul unei fucţii şi ele sunt cunoscute doar în
funcţia în care au fost definite.
În cazul programelor simple, care conţin doar funcţia main() nu este necesar definirea
globala a variabilelor.
Funcţiile utilizator :
definirea oricărei funcţii este constuită din antetul funcţiei si corpul funcţiei
antetul funcţiei conţine numele funcţiei, tipul rezultatului pe care funcţia îl calculează şi o
listă de parametri prin care funcţia comunică cu exteriorul ei, încadrată între paranteze
rotunde:
tip_rezultat nume_functie(lista de parametri)
nu fac obiectul materiei de clasa a IX-a, ele vor fi învăţate pe larg în clasa a X-a
Funcţia main() este o fucţie specială, mai este numită şi funcţia principală sau programul
principal, prezenţa ei este obligatorie în orice program C++ deoarece execuţia oricărui program
începe cu aceasta. Pentru început vom scrie doar programe constituite doar din funcţia main().
Cel mai simplu program C++, care desigur nu are nici un efect este: void main()
{ }
Prezentarea ecranului mediului de programare C++ 3.1
Lansarea în execuţie a mediului de programare C++ se face lansând în execuţie fişierul
executabil bc.exe aflat în directorul BIN din pachetul Borland C++, obţinut după instalarea
acestuia. După acestă acţiune ecranul afişat va avea următoarea formă:
2
1
1
4
3
5 6
Unde:
1. bara de titlu în care este trecut mediul de programare Borland C++ for DOS
2. butoane pentru minimzare/ maximizare şi inchidere aplicaţie
3. bara de meniu a mediului de programare care conţine opţiunile: File, Edit, Search,
Compile, Debug, Project, Options, Windows, Help
4. zona de lucru în care veti scrie programele C++
5. meniul Help care conţine semnificaţia principalelor taste funcţionale pentru operaţiile de
bază:
F1- lansează help-ul limbajului C++ pentru a ne ajuta în cazul semnificaţiei, modului
de execuţie al unei comenzi, sintaxă, definire
F2- tastă utilizată pentru a memora pe hard fişierul curent deschis şi care conţine
codul sursă al programului scris in C++
F3-deschide o nouă fereastră in care se va scrie un cod sursă. După apasarea tastei F3
trebuie precizat numele noului fisier in forma nume.cpp
ALT+F9 realizează operaţia de compilare a programului, adică o verificare din punct
de vedere sintactică a programului scris, si care va afişa toate erorile din program.
F10 –permite cursorul sa ajungă în partea de meniu principal al limbajului C++
6. 1:1 – precizează poziţia curentă a cursorului în zona de lucru, în cazul nostru linia 1,
coloana 1.
Pentru a afişa această fereastă pe intreg ecranul monitorului apasaţi ALT+ENTER.
Meniul File conţine următoarele obţiuni:
New - Deschide un nou fisier sursă cu numele implicit
Noname00.cpp, sau ....001.cpp
Open... - deschide un fisier cpp existent pe disk
Save – salvează fisierul curent
Save as - realizează un lat fişier cu continut identic cu cel
curent, dar cu nume schimbat
Save all - salveaya continutul tuturor fisierelor deschise
Change dir...-permite schimbarea directorului curent in care
va fi memorat fisierul curent
Print – tipareste la imprimanta continutul sursei programului
curent
Quit - inchide aplicaţia Borland C++.
Etape în scrierea si execuţia unui program C++:
1. se deschide aplicaţia Borland C++
2. se stabileste directorul curent în care vom salva sursa programului folosind File →
Change dir... →selecţie director dorit si la final se apasa butonul OK
3. Se deschide un fisier nou : File →New sau direct apasând tasta F3, caz în care trebuie sa
stabilim un nume pentru noul fişier
4. se scrie în zona de lucru codul sursă al programului
5. se salvează pe parcursul editării programului si la terminarea acestei operaţii continutul
programului utilizând File → Save sau tasta F2
6. Se verifica respectarea regulilor sintactice compilând programul folosind combinaţiile de
taste ALT+F9 sau din meniul superior alegând Compile → Compile
7. după ce au fost corectate toate erorile de compilare, se mai salvează o dată programul
scris după care se lansează în execuţie prin combinaţia CTRL+F9 sau din meniul
superior Run→Run
8. În această etapă se verifică corectitudinea funcţionării programului scris verificând şi
analizând rezultatele afişate.
Tipuri de date standard
Noţiunea de dată a fost prezentată pe larg în lecţia trecută. Orice limbaj de programare dispune
de un set de date predefinite numite şi tipuri de date standard. Tipurile de date standard sunt
prezentate în următorul tabel:
Grupa
de
dată
Tipul Nr. octeţi
ocupaţi Domeniu de valori
Mod de reprezentare în
memorie
întreg
char 1 octet cu semn -128...127 codul ASCII al
caracterului. unsigned char 1 octet fara semn 0...255
int 2 octeti cu semn -32768...23767 complement faţă de 2
unsigned int 2 octeti fară semn 0...65535 în baza 2
long 4 octeţi cu semn -231..231-1 complement faţă de 2
unsigned long 4 octeţi fara semn 0.. 232-1 în baza 2
real
float 4 octeţi cu semn [3.4·10-38...3.4·1038 ] u [-3.4·10-38...-3.4·1038]
virgulă mobilă simplă precizie
double 8 octeţi cu semn [1.7·10-308...1.7·10308] u [-1.7·10-308...-1.7·10308]
virgulă mobilă dublă precizie
long double 10 octeţi cu semn
[3.4·10-4932...3.4·104932 ] u
[-3.4·10-4932...-
3.4·104932]
virgulă mobilă dubla precizie
void Tip de dată special pentru care mulţimea valorilor este vidă
Observaţii:
În cazul tipului de dată char, deşi a fost introdus pentru stocarea datelor de tip
alfanumeric, el poate fi folosit în calcule numerice şi logice în intervalul de valori pe care
le poate stoca.
În cazul datelor de tip char, int se pot folosi modificatorii de tip:
o unsigned pentru a obţine doar numere naturale,
o long pentru a modifica dimensiunea reprezentării
În limbajul C++ nu există un tip de date special pentru valorile logice. Valoarea 0 este
asociată valorii de adevăr fals, orice valoare diferită de 0 fiind asociată valorii de
adevăr adevărat.
Pentru a declara o variabilă în limbajul de programare C++ se foloseşte următoarea costrucţie
sintactică:
denumire_tip_standard variabilă;
Dacă dorim să declarăm mai multe variabile de acelaşi tip este suficient să le separăm cu
aracterul virgula. Exemplu:
Declarare variabile Efect int a,b,c; am definit trei variabile numite a,b, c de tip intreg float x; x variabilă reala simplă precizie char ch; ch variabilă de tip caracter
unsigned n; variabila n este de tip int fără semn unsigned long m; variabila m este de tip long fără semn unsigned char p; variabila p este de tip char fara semn
double d; variabila d este un numar real dublă precizie
Operatori. Expresii. Evaluarea expresiilor
Operatori aritmetici
Operatorii aritmetici se împart în două categorii:
operatori unari: se aplică asupra unui singur operand.Singurul operator aritmetic unar
definit în C++ este caracterul - scris în fata unui număr întreg sau real si care determină
semnul valorii respective.
operatori binari: se aplică asupra a doi operanzi. Operatorii binari definiţi în limbajul
C++ sunt:
Operator Semnificaţie
+ adunare
- scadere
* înmulţire
/ a/b
daca a şi b sunt două valori întregi
determină câtul împartirii
dacă a şi b sunt doua valori reale
determina rezultatul împărţirii
% determină restul împarţirii a două numere
nu se aplica valorilor float sau double
Prioritatea operatorilor este prezentată în următorul tabel:
Operator
Operatorul unar - Cel mai prioritar
Operatorii multiplicativi: *,/ ,% Prioritate medie
Operatorii aditivi:+,- Cel mai putin prioritar
Operatorii aritmetici se grupeaza de la stânga la dreapta Ordinea de evaluare este cea de
la matematică. Prioritatea operatoriloe se poate schimba daca in relaţiile matematice intervin
caractere ( , ) folosite pentru gruparea termenilor expresiilor matematice.
Exemple:
Expresie matematică Valoare obţinută
Dacă avem două variabile a=20 şi b=3 definite de tip int atunci:
a+b 20+3=23
a-b 20-3=17
b-a 3-20= -17
a/b 20/3=6
a%b 20%3=2
b/a 3/20=0
b%20 3%20=3
(a+b)/(a-b) (20+3) / (20-3)=23/17=1
(a+b)%(a-b) (20+3) % (20-3)=23%17=6
(a+b)/2 (20+3)/2=23/2=11
Expresie matematică Valoare obţinută
Dacă avem două variabile a=2.0 şi b=3.5 definite de tip float atunci: a+b 2.0+3.5=5.5
a-b 2.0-3.5=-1.5
b-a 3.5-2.0= 1.5
a/b 2.0/3.5=0.5714
a%b Operaţie nepermisă
b/a 3.5/2.0=1.75
(a+b)/(a-b) (2.0+3.5)/(2.0-3.5)=5.5/-1.5=-3.66666
(a+b)/2 (2.0+3.5)/2=5.5/2=2.75
Operatori relaţionali şi de egalitate
Operatorii relaţionali sunt operatori binari şi desemnează relaţia de ordine în care se
găsesc cei doi operanzi. Rezultatul aplicării unui operator relaţional este 1 (adevărat) dacă cei
doi operanzi sunt în relaţia indicată de operator, şi 0(fals), altfel. Tabelul cu operatorii
relaţionali din limbajul C++ este:
Operator Semnificaţie = = este egal
< mai mic
<= mai mic sau egal
> mai mare
>= mai mare sau egal
!= diferit
Exemple:
Expresie
relaţională
Valoare obţinută
Dacă avem două variabile a=20 şi b=3 definite de tip int atunci: a==b 20 este egal cu 3? rezultat 0 (fals)
a!=b 20 este diferit 3? rezultat 1 (adevarat)
a<b 20 mai mic decat 3? rezultat 0(fals)
a<=b 20 mai mic sau egal cu 3? rezultat 0 (fals)
a>b 20 mai mare decat 3? rezultat 1 (adevarat)
a>=b 20 mai mare sau egal cu 3? rezultat 1 (adevarat)
Operatori logici
Operatori logici globali:
Există trei tipuri de operatori logici globali:
Operator Denumire Tip Prioritate
! Negaţie logică Operator unar
&& Conjucţie logică(şi logic) Operator binar
|| Disjuncţie logică(sau logic) Operato binar
Aşa cum ştiţi deja în limbajul C++, valoarea logică fals are asociata valoarea 0, iar orice
valoare diferită de 0 are semnificaţia de adevărat. Prin urmare efectul operatorilor logici este
acelaşi ca în matematică şi este prezentat în tabele următoare: a !a a b a && b a b a || b
0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
Exemple:
Expresie logică Valoare obţinută
x%3 1,daca x se divide la 3
0, daca x nu se divide la 3
!(x%2) 1,daca x se divide par
0, daca x impar
(x>=a)&&(x<=b) 1, daca x apartine intervalului [a,b]
0, daca x nu apartine intervalului [a,b]
(x<a)||(x>b) 1, daca x nu apartine intervalului [a,b]
0,daca x apartine intervalului [a,b]
!((x>=a)&&(x<=b))
Se va transforma in relaţia
(x<a)||(x>b)şi deci rezultatul va fi:
1, daca x nu apartine intervalului [a,b]
0,daca x apartine intervalului [a,b]
(a==b+1)||(b==a+1) 1, daca a şi b sunt numere consecutive
0, altfel
Operatori logici la nivel de bit:
Aceşti operatori se aplică doar datelor de tip întreg şi au ca efect aplicarea operaţiilor
logice cunoscute(negaţie, conjuncţie, disjuncţie şi disjuncţie exclusivă) bit cu bit. Aceştia
sunt prezentaţi în următorul tabel:
Operator Semnificaţie Tip Prioritate Obs. ~ complementaritate (negaţie bit cu bit) unar
<< deplasare spre stanga cu b pozţiţii (a<<b) binar a*2b
>> deplasare spre dreapta cu b pozitii (a>>b) binar a/2b
& conjuncţie logică(şi logic) bit cu bit binar
^ dijuncţie logica exclusivă (sau exclusiv) bit cu bit binar | disjunţie logică(sau logic) bit cu bit binar
Operatorii de delasare au ca efect deplasarea reprezentării binare a primului operand spre
stânga (<<) sau spre dreapta (>>) iar numărul de poziţii care se deplasează este precizat de al
doilea operand. La deplasarea la stânga, poziţiile rămase libere în dreapta se completează cu 0.
La deplasarea spre dreapta, poziţiile rămase libere în stânga se completează cu 0 (daca operandul
stâng este un întreg pozitiv) sau cu 1 (dacă operandul este negativ).
Efectul operaţiilor la nivel de bit este prezentat mai jos: a ~a a b a&b a b a^b a b a|b
0 1 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 1 0 1 1
1 0 0 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1
Exemplu: Fie două numere întregi a şi b reprezentate pe 1 octet:
21. Scrieţi algoritmul în pseudocod pentru următoarele scheme logice şi identificaţi structurile de
control care le alcătuiesc:
22. Fie următorii algoritmi scriş în limbaj pseudocod:
Se cere:
a. Realizaţi schema logică pentru fiecare algoritm;
b. Care sunt structurile repetitive întalnite în fiecare
algoritm?
c. Câte structuri alternative identificaţi în fiecare
algoritm dat?
a.
┌cât timp C1 execută
| ┌daca C2 atunci
| | ┌executa
| | | B1
| | |cat timp C3;
| | └■
| |altfel
| | ┌cat timp C4 executa
| | | B2
| | └■
| └■
| B3
| ┌pentru i=vi,vf,+1
| | B4
| └■
└■
┌dacă C1 atunci
| ┌dacă C2 atunci
| | B1
| |altfel
| | B2
| └■
| ┌cât timp C3 execută
| | B3
| | ┌dacă C4 atunci
| | | B4
| | └■
| └■
└■
┌execută
| B1
| ┌pentru i=v1,vf,+1
| | B2
| └■
| ┌dacă C1 atunci
| | ┌cât timp C2 execută
| | | B3
| | └■
| |altfel
| | B4
| └■
|cât timp C3
└■
3. Care este rezultatul afişat după execuţia următorului algoritm?
i=1
┌cât timp i<=5 execută
| j=1
| ┌cât timp j<=i execută
| | scrie „*‟
| | j=j+1
| └■
| i=i+1
| salt la rând nou
└■
4. Scrieţi programul C++ si precizaţi care este efectul următorului algoritm scris în limbaj
pseudocod, dacă valoarea citită pentru variabila n este 7:
citeşte n
s=0
i=1
┌cât timp i<=n execută
| s=s+i
| i=i+1
└■
scrie s
5. Care este efectul următorului program?
#include<iostream.h>
#include<conio.h>
int i,n;
void main()
{clrscr();
n=10;
for(i=1;i<=n;i++)
{ cout<<i<<" ";
n--;
}
getch();
}
a. 1 2 3 4 5 6 7 8 9 10 b. 1 2 3 4 5
c. 10 9 8 7 6 5 4 3 2 1 d. 5 4 3 2 1
6. Fie următoarea secvenţă de program:
#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
for(char i='a';i<='f';i++)
cout<<i<<" ";
getch();
}
Pe ecran se va afişa:
a. A B C D E F b. i i i i i i
c. a f a f a f d. a b c d e f
7. Fie următoarea secvenţă de program:
#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
for(int i=5;i<=5;i++)
cout<<i<<" ";
getch();
}
După execuţia programului pe ecran se va afişa:
a. 5;
b. 6;
c. Nimic, exista erori de compilare;
d. Nici un răspuns nu este corect.
8. Care vor fi valorile afişate ale variabilelor a şi b după executarea următorului program C++:
#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
int a=1,b=2;
while(b<10)
b++;
a=a*b;
cout<<a<<" "<<b;
getch();
}
a. 10 10 b. 11 11
c. 9 10 d. 10 9
9. Care va fi valoarea afişată a variabilei a după execuţia următorului program C++:
#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
int a=1,b=8;
while(b>1)
{a=a+b;
b=b-3;
};
cout<<a<<" "<<b;
getch();
}
a. 32 b.34
c. 16 d. nici un răspuns nu este corect
10. De câte ori se execută instrucţiunile cuprinse între cuvintele execută-cât timp din
umătorul algoritm:
m=1
x=1
┌execută
| m=m*x
| x=x+8
|cât timp m>=x;
└■
a. de două ori b. niciodată
c. o singură dată d. de opt ori
11. Precizaţi care este valoarea variabilei a, după execuţia următoarei secvenţe de algoritm:
m=5
a=20
┌execută
| a=a-m
| m=m+1
|cât timp m<=a;
└■
a. 15 b. 2
c. 0 d. 9
12. Rescrieţi următoarele secvenţe de program C++, astfel încât buclele repetitive să fie înlocuite
cu instrucţiunea care implementeză structura repetitivă cu test iniţial:
S=0;n=9;
for(int i=1;i<=n;i++)
s=s+i;
cout<<”s=”<<s;
for(int i=10;i>= -2;i--)
cout<<”i=”<<i<<endl;
for(int i=1;i<=n;i++)
{ for(int j=1;j<=n;j++)
cout<<”*”;
cout<<endl;
}
for(int i=5; i<=10;i++)
cout<<i<<” ”;
cout<<end;
13. Rescrieţi următoarele secvenţe de program C++, astfel încât buclele repetitive să fie înlocuite
cu instrucţiunea care implementeză structura repetitivă cu test final:
int i=2;
int ok=1;
while(i<n/2 && ok)
if(n%i==0)
ok=0;
else
i++;
for(int i=100;i>=1;i--)
if(i%2==0)
cout<<i<<” ”;
int s=0;
while(n!=0)
{ s=s+n%10;
n=n/10;
};
for(char i='a';i<='f';i++)
cout<<i<<" ";
14. Rescrieţi următoarele secvenţe de program C++, astfel încât buclele repetitive să fie înlocuite
cu instrucţiunea care implementeză structura repetitivă cu număr fix de paşi:
int p=1, i=1;
while(i<n)
{ p=p*i;
i++;
};
char ch=‟a‟;
while (ch<=‟z‟)
{cout<<ch<<” ”;
ch++;
};
int i=1;
do{
int j=1;
do{
cout<<”*”;
j++;
}while(j<=n);
cout<<endl;
i++;
}while(i<=n);
int i=1;
while(i<=n)
{ int j=1;
do{
cout<<”*”;
j++;
}while(j<=n);
cout<<endl;
i++;
}
15. Specificaţi de câte ori se vor repeta instrucţiunile din bucla repetitivă şi care va fi valoarea
variabilei i la sfârşitul următoarei secvenţe de algoritm. Scrieţi programul C++
corespunzător algoritmului dat.
i=1, s=0(numere întregi)
┌cât timp (i<=5) execută
| s=s+i
| i=i+1
└■
a. se obţine o buclă infinită b. de 5 ori şi i=6
c. de 6 ori si i=6 d. de 5 ori si i=5
16. Specificaţi de câte ori se vor repeta instrucţiunile din bucla repetitivă şi care va fi valoarea
variabilei i la sfârşitul următoarei secvenţe de algoritm. Scrieţi programul C++
corespunzător algoritmului dat.
i=0 (numar intreg)
┌cât timp i<1 execută
| i=i+1
└■
a. o singură dată şi i=1 b. de două ori şi i=1
c. nu se execută niciodată şi i=0 d. se obţine o buclă infinită
17. Specificaţi de câte ori se vor repeta instrucţiunile din bucla repetitivă şi care vor fi valoarile
variabilelor s şi c la sfârşitul următoarei secvenţe de algoritm. Scrieţi programul C++
corespunzător algoritmului dat.
c=100, s=0 (numere întregi)
┌execută
| s=s+c
| c=s-10
|cât timp s<=c
└■
a. o singură dată şi s=90, c=100 b. o singură dată şi s=100, c=90
c. o singură dată şi s=90, c=90 d. se obţine o buclă infinită
18. Fie următoarea secvenţă scrisă în limbaj pseudocod:
citeşte n
i=1
┌cât timp i<=n execută
| scrie „# # ”
| i=i+1;
└■
Care trebuie să fie valoarea variabilei n astfel încât să se afişeze pe ecran „# # # # # #” ?
a. 2 b.4
c.3 d.1
19. Fie următoarea secvenţă de algoritm:
citeşte a,b
┌pentru i=a,b,+1
| ┌dacă i%2 == 0 atunci
| | scrie i, “ “
| └■
└■
a. Ce va afişa dacă pentru variabilele a şi b se vor citi valorile 10 respectiv 20?
b. Daţi un set de valori de intrare pentru care algoritmul nu afisează nimic
c. Scrieţi un program C++ corespunzator algoritmului dat.
20. Fie următoarea secvenţă de algoritm:
┌execută
│ citeşte a,b
│cât timp (a<b sau b=0)
└■
nr=0
┌cât timp c>b execută
│ a=a-b
│ nr=nr+1
└■
scrie nr,” “,a
a. Ce se va afişa decă valorile iniţile ale variabileor a şi b sunt 54 si 10.
b. Daţi un set de date de intrare pentru care se va afişa 3 şi 0.
c. Scrieţi programul C++ corespunzător algoritmului dat.
21. Fie următoarea secvenţă de algoritm:
citeşte x (număr natural)
n=0
┌cât timp x≠0 execută
│ y=x; c=0
│ ┌cât timp y>0 execută
│ │ ┌dacă y%10>c atunci
│ │ │ c=y%10
│ │ └■
│ │ y=y/10
│ └■
│ n=n*10+c
│ citeşte x
└■
scrie n
Se cere:
a. Scrieţi valoarea ce se va afişa dacă se citesc, în această ordine, numerele 12, 7,
354, 9, 1630, 0.
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod.
22. Fie următoarea secvenţă de algoritm:
citeşte a,b,c (numere naturale nenule)
┌dacă a>b atunci
│ t=a; a=b; b=t
└■
┌cât timp a≤b execută
│ ┌dacă c%a=0 atunci
│ │ scrie a
│ └■
│ a=a+1
└■
Se cere:
a. Scrieţi care sunt valorile ce se vor afişa pentru a=10, b=20 şi c=6;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod.
23. Fie următoarea secvenţă de algoritm:
citeste n,m (numere naturale)
┌cât timp n≤m execută
│ n=n+1
│ m=m-1
└■
┌cât timp m<n execută
│ m=m+1
│ n=n-1
└■
scrie n
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc numerele n=6 şi m=12;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
d. Scrieţi două perechi distincte de numere ce pot fi introduce pentru n şi m astfel
încât să se afişeze valoarea 10, în urma executării algoritmului, pentru fiecare
dintre perechi.
24. Fie următoarea secvenţă de algoritm:
citeste n (număr natural)
m=0
p=1
┌cât timp n>0 execută
│ c=n%10
│ ┌dacă c>0 atunci
│ │c=c-1
│ └■
│ m=m+c*p
│ p=p*10
│ n=n/10
└■
scrie m
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc numerele n=5172;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
25. Fie următoarea secvenţă de algoritm:
citeşte x (număr natural)
s=0
f=2
┌cât timp x>1 execută
│ p=0
│┌cât timp x%f=0 execută
││ x=x/f
││ p=p+1
│└■
│┌dacă p≠0 atunci
││ s=s+p
│└■
│ f=f+1
└■
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc numerele x=140;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
26. Fie următoarea secvenţă de algoritm:
s=0
citeşte v (valoare naturală)
┌cât timp v ≠ 0 execută
│ a = v%10
│ b = [v/10]%10
│ s = s + a*10 + b
│ citeşte v
└■
scrie s
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc, în ordine, numerele 114, 123, 517,
3312, 14, 412, 22, 0;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
27. Fie următoarea secvenţă de algoritm:
citeşte n,k (numere naturale, k≤9)
i = k
┌cât timp i > 0 execută
│ n = n/10
│ i = i-1
└■
z = n%10
scrie z
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc numerele n=32506 şi k=3;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
28. Fie următoarea secvenţă de algoritm:
citeşte x (număr natural nenul)
┌cât timp x>0 execută
│ citeşte y (număr natural)
│┌dacă x>y atunci
││ scrie x%10
││altfel
││ scrie y%10
│└■
│ x = y
└■
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc, în ordine, numerele 17 22 13 101
2 7 5 0;
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
29. Fie următoarea secvenţă de algoritm:
citeste n,k
(numere naturale nenule)
t=0
┌cât timp n≥1 execută
│┌dacă n>k atunci
││ t=t+1
│└■
│ n=n-t
└■
scrie t
Se cere:
a. Scrieţi valoarea care se afişează dacă se citesc n=7 si k=2
b. Scrieţi programul C/C++ corespunzător algoritmului dat;
c. Desenaţi schema logică corespunzătoare algoritmului scris în pseudocod;
Algoritmi care prelucrează cifrele unui număr natural
Există nenumărate aplicaţii în practică, când ni se solicită informaţii despre cifrele din
care este construi un număr, despre natura sau numărul lor. În acest caz cifrele numărului vor fi
separate, una câte una, de la ultima cifră(cifra unităţilor) spre prima cifră. După fiecare
prelucrare din numărul iniţial vom elimina ultima cifră, algoritmul conţinuând în acelaşi mod, în
funcţie de numărul de cifre din numărul dat.
Şablonul de rezolvare al problemelor care prelucrează cifrele unui număr natural are
următoarea formă:
citeşte numărul de prelucrat
iniţializarea variabilelor de manevră
┌cât timp numărul dat mai are cifre neprelucrate execută │ - extrage ultima cifră din număr
│ - prelucrază această cifră conform enunţului din problemă
│ - elimină din numărul de prelucrat ultima lui cifră
└■
afişează rezultatul
Aplicaţii rezolvate
1. Se dă un număr natural n. Se cere să se scrie un algoritm care calculează suma cifrelor numărului dat.
Rezolvarea acestei probleme va urmări şablonul de rezolvare prezentat mai sus, tinând
cont de faptul că atunci când avem de calculat o sumă de termeni, variabila care va conţine
rezultatul se va iniţializa cu valoarea zero.
Algoritmul este:
citeşte n număr natural şi reprezintă numărul de prelucrat
s=0 va conţine, la final, suma cifrelor numărului n, iniţial va avea
valoarea zero
┌cât timp n>0 execută
│ c = n%10 extrag ultima cifră din numarul n
│ s = s+c adun cifra separată la suma cifrelor numărului n
│ n = n/10 elimin din numărul n ultima lui cifră
└■
scrie “suma cifrelor este ”, s
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,s,c;
void main()
{clrscr();
cout<<"n="; cin>>n;
while(n>0)
{ c=n%10;
s=s+c;
n=n/10;
}
cout<<"suma cifrelor este "<<s;
getch();
}
2. Se dă un număr natural n. Să se precizeze din câte cifre este
alcătuit.
Algoritmul de rezolvare urmăreşte şablonul prezentat, doar că în acestă situaţie problema
se simplifică. Nu mai avem nevoie de cifra să o păstrăm în variabila c, doar vom număra de
câte ori putem împărţi numărul la 10, obţinând astfel numărul de cifre
Algoritmul este:
citeşte n număr natural şi reprezintă numărul de prelucrat
nr=0 va conţine numărul cifrelor numărului n, iniţial va avea
valoarea zero
┌cât timp n>0 execută
│ nr = nr+1 număr că am separat o cifră din numărului n
│ n = n/10 elimin din numarul n ultima lui cifra
└■
scrie “suma cifrelor este ”, s
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,nr;
void main()
{clrscr();
cout<<"n="; cin>>n;
while(n>0)
{ nr++;
n=n/10;
}
cout<<"numărul cifrelor este "<<nr;
getch();
}
3. Se dă un număr natural n. Se cere să se calculeze suma
cifrelor pare din numarul dat.
Algoritmul este: citeşte n număr natural şi reprezintă numărul de prelucrat
s=0 va conţine, la final, suma cifrelor pare din numărului n, iniţial
va avea valoarea zero
┌cât timp n>0 execută
│ c = n%10 // extrag ultima cifră din numărul n
│ ┌dacă c%2 == 0 atunci // dacă ultima cifră este pară
│ │ s = s+c // adun cifra separată la sumă
│ └■
│ n = n/10 //elimin din numarul n ultima lui cifră
└■
scrie “suma cifrelor este ”, s
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,s,c;
void main()
{clrscr(); cout<<"n="; cin>>n;
while(n>0)
{ c=n%10;
if (c%2==0)
s=s+c;
n=n/10;}
cout<<"suma cifrelor pare este "<<s;
getch();
}
4. Se dă un număr natural n. Se cere să se determine cifra maximă
din numarul dat.
Atunci când avem de determinat valoarea maximă dintre un şir de numere, vom iniţializa
variabila care va conţine maximul cu cea mai mică valoare posibilă. În cazul nostru trebuie să
determinăm cifra maximă dintre cifrele unui număr dat, şi vom iniţializa cifra maximă cu
valoarea zero, apoi vom extrage câte o cifră din număr şi o vom compara cu valoarea cifrei
maxime. În situaţia în care am găsit o valoare mai mare vom actualiza informaţia din cifra
maximă, cu ultima cifră extrasă din număr. Algoritmul continuă în acelaşi mod până când au fost
prelucrate toate cifrele numărului dat.
Algoritmul este: citeşte n număr natural şi reprezintă numărul de prelucrat
cif_max=0 va conţine, la final, cifra maximă din numărului n, iniţial
va avea valoarea zero
┌cât timp n>0 execută
│ c = n%10 // extrag ultima cifră din numărul n
│ ┌dacă c >= cif_max atunci // dacă ultima cifră este mai mare decât
│ │ cif_max = c // cifra maximă, atunci păstrez valoarea ei
│ └■
│ n = n/10 //elimin din numarul n ultima lui cifră
└■
scrie “cifra maxima este ”, cif_max
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,c,cif_max;
void main()
{clrscr();
cout<<"n=";cin>>n;
while (n>0)
{c = n%10;
if( c>cif_max)
cif_max = c;
n = n/10;
}
cout<<"cifra maxima este ";
cout<<cif_max;
getch();
}
5. Se dă un număr natural n. Se cere să se determine numărul
obţinut din n, dar care are cifrele în ordinea inversă.
Algoritmul este:
citeşte n // număr natural şi reprezintă numărul de prelucrat
m=0 // va conţine, la final, cifrelor numărului n în ordine inversă,
iniţial va avea valoarea zero
┌cât timp n>0 execută
│ c = n%10 // extrag ultima cifră din numarul n
│ m = m*10+c // adun cifra separată la numărului m modificând şi
│ semnificaţia cifrelor(cifra unităţilor va deveni cifra
│ zecilor, cifra zecilor va deveni cifra sutelor, etc.)
│ n = n/10 // elimin din numărul n ultima lui cifră
└■
scrie “numărul cu cifrele inversate este ”, m
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,c,m;
void main()
{clrscr();
cout<<"n=";cin>>n;
while (n>0)
{ c=n%10;
m=m*10+c;
n=n/10;
}
cout<<"numarul cu cifrele inversate
este "<<m;
getch();
}
6. Se dă un număr natural n. Se cere să se verifice dacă are
toate cifrele pare.
Atunci când avem de a verifica îndeplinrea unei condiţii de către toate elementele unui şir
vom proceda astfel:
vom presupune că toate elementele şirului îndeplinesc condiţia cerută;
vom verifica dacă există cel mult un număr din şir care nu verifică condiţia dată.
În situaţia nostră vom presupune iniţial că toate cifrele numărului dat sunt pare şi vom separa
apoi câte o cifră din număr şi îi vom verifica paritatea. Dacă în numărul iniţial există cel mult o
cifră pară, atunci vom ajunge la concluzia ca nu toate cifrele numărului dat sunt pare.
Algoritmul este:
citeşte n // număr natural şi reprezintă numărul de prelucrat
ok = 1 // presupun că toate cifrele numărului sunt pare, iniţial variabila
ok va avea valoarea unu
┌cât timp n>0 şi ok = 1 execută // numărul mai are cifre şi preupunerea
│ făcută rămâne valabilă
│ c = n%10 // extrag ultima cifră din numărul n
│ ┌dacă c%2 = 1 atunci // dacă ultima cifra extrasă este impară atunci
│ │ ok = 0 // presupunerea făcută nu este adevarată!
│ └■ // rezultă că nu toate cifrele lui n sunt pare
│ n = n/10 // elimin din numărul n ultima lui cifră
└■
┌daca ok = 1 atunci
│ scrie “Toate cifrele numarului dat sunt pare! ”
│altfel
│ scrie “NU toate cifrele numarului dat sunt pare! ”
└■
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,c,0ok;
void main()
{clrscr();
cout<<"n=";cin>>n;
ok=1;
while (n>0 && ok)
{ c=n%10;
if (c%2==1)
ok=0;
n=n/10;
}
sau:
if (ok==1)
cout<<"Toate cifrele numarului dat
sunt pare ";
else
cout<<"NU toate cifrele numarului
dat sunt pare ";
getch();
}
7. Se dă un număr natural n. Se cere să se verifice dacă numărul
dat conţine cel putin o cifră pară.
Atunci când trebuie să verificam îndeplinrea unei condiţii de către cel puţin un element din
şir vom proceda astfel:
vom presupune că niciunul din elementele şirului nu îndeplinesc condiţia cerută;
vom verifica dacă există cel puţin un număr din şir care verifică condiţia dată.
În situaţia nostră vom presupune iniţial că nici una din cifrele numărului dat nu este pară şi
vom separa apoi câte o cifră din număr şi îi vom verifica paritatea. Dacă în numărul iniţial există
cel puţin o cifră pară, atunci vom ajunge la concluzia ca în cifrele numărului dat există cel puţin
o cifră pară.
Algoritmul este:
citeşte n // număr natural şi reprezintă numărul de prelucrat
ok = 0 // presupun că toate cifrele numărului sunt impare, iniţial
variabila ok va avea valoarea zero, nici o cifră nu îndeplineşte
condiţia cerută
┌cât timp n>0 şi ok = 0 execută // numărul mai are cifre şi preupunerea
│ făcută rămâne valabilă
│ c = n%10 // extrag ultima cifră din numărul n
│ ┌dacă c%2 = 0 atunci // dacă ultima cifra extrasă este pară atunci
│ │ ok = 1 // presupunerea făcută nu este adevarată!
│ └■ // rezultă că nu toate cifrele lui n sunt impare
│ n = n/10 // elimin din numărul n ultima lui cifră
└■
┌dacă ok = 1 atunci
│ scrie “Exista cel putin o cifra pară! ”
│altfel
│ scrie “NU există cifre pare, toate cifrele sunt impare! ”
└■
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,c,ok;
void main()
{clrscr();
cout<<"n=";cin>>n;
while (n>0 && !ok)
{ c=n%10;
if (c%2==0)
ok=1;
n=n/10;}
if (ok==1)
cout<<"Exista cel putin o cifra para!";
else
cout<<"NU exista cifre pare, toate
cifrele sunt impare ";
getch();
}
sau:
Aplicaţii practice
1. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se calculeze suma
cifrelor impare. Exemplu: dacă n=2345 atunci suma cifrelor impare este s=5+3=8
2. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine câte
cifre impare conţine numărul dat. Exemplu: numărul n=3445 are două cifre impare (3 şi 5)
3. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se calculeze
produsul cifrelor pare. Exemplu: dacă n=6542 atunci produsul cifrelor pare este 2*4*6=48
4. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se calculeze
produsul cifrelor impare. Exemplu: dacă n=6543 atunci produsul cifrelor impare este 3*5=15
5. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine cifra
minimă. Exemplu: dacă n=6143 atunci cifra minimă este 1
6. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se verifice dacă
numărul de cifre pare este egal cu numărul de cifre impare. Exemplu: dacă n=61432, atunci el are 3 cifre pare(2, 4, 6) şi 2 cifre impare
(3, 1), de unde rezultă că numărul de cifre pare nu este egal cu numărul de
cifre impare.
7. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se verifice dacă
numărul conţine cel puţin o cifră de zero. Exemplu: dacă n=61432, atunci el nu conţine nici o cifră egală cu zero, dar
dacă valoarea iniţială a numărului n este n=12003 atunci se va afişa numărul
conţine cifre de zero.
8. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se verifice dacă
cifrele numărului sunt în ordine crescătoare. Exemplu: dacă n= 344567 atunci el are cifrele în ordine crescătoare, iar dacă
n=12432 atunci el nu are cifrele în ordine crescătoare.
9. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se verifice dacă
cifrele numărului sunt în ordine descrescătoare. Exemplu: dacă n= 988754 atunci el are cifrele în ordine descrescătoare, iar
dacă n=55243 atunci el nu are cifrele în ordine descrescătoare.
10. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se verifice dacă
numărul este palindrom (numărul iniţial este egal cu numărul cu cifre inversate). Exemplu: dacă n=98789 este palindrom, iar numărul 123 nu este palindrom,
123≠321
11. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine dacă
toate cifrele sale sunt egale. Exemplu: dacă n=22222 are toate cifrele egale, iar numărul n=11121 nu are
toate cifrele egale.
12. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine dacă
numărul n are toate cifrele egale cu x, citit de la tastatură.
Exemplu: dacă n=22222 şi x=2 atunci n are toate cifrele egale cu x, iar
numărul n=22222 şi x=5 atunci nu are toate cifrele egale cu x.
13. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se afişeze pe
ecran histograma cifrelor. (pentru fiecare cifră care apare în număr se va afişa un număr de *
egal cu frecvenţa de apariţie a cifrei respective în numărul iniţial) Exemplu: dacă n=223158555 atunci se va afişa pe ecran următoarea histogramă :
0:
1:*
2:**
3:*
4:
5:****
6:
7:
8:*
9:
14. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine care
este cea mai mică bază în care poate fi scris numărul dat. Exemplu: dacă n=22315555, atunci cifra maximă este 5 şi rezultă că cea mai
mică bază în care este scris numărul este 6. De la matematică cunoaştem că un
număr scris în baza b poate să conţină cifre din intervalul [0,b-1].
15. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se să se determine
cel mai mare număr care se poate obţine prin eliminarea unei cifre din număr(nu se va
modifica poziţia cifrelor în număr). Exemplu: dacă n=67324, prin eleiminarea unei cifre din acest numa se vor
obţine numerele: 6732, 6734, 6724, 6324 şi 7324, iar pe ecran se va afişa
7324.
16. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se afişeze cifra de
rang k, dat de la tastatură(rangul unei cifre este numărul său de ordine, numerotând cifrele de
la dreapta la stânga începând cu zero. Exemplu: dacă n=67324 şi k=2 atunci pe ecran se va afişa cifra 3, ea este
cifra de rang doi din numărul n, dat iniţial.
17. Să se scrie un program care calculează „cifra de control” a unui număr întreg efectuând
repetat suma cifrelor sale, până se obţine un număr format dintr-o singură cifră. Exemplu: dacă n=67324 cifra lui de control este 4 (67324 are suma cifrelor
4+2+3+7+6=22, numarul 22 are suma cifrelor 2+2=4)
18. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine toate
numerele care se pot obţine adăugând prima cifră la sfârşitul numărului. Exemplu: dacă n=67324 se obţine următorul şir de numere: 73246, 32467, 24673,
46732, şi 67324.
19. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se afişeze o
piramidă formată din cifrele numărului dat. Exemplu 1: dacă n=67324 se va afişa
3
732
67324
Exemplu 2: dacă n=673124 se va afişa:
31
7312
673124
20. Se citeşte de la tastatură un număr natural n de cel mult 9 cifre. Se cere să se determine dacă
numărul are aspect de „deal” sau de „vale”, Exemplu 1: dacă n=12321 se va afişa DEAL!, cifrele urcă până la 3, după
care coboară
Exemplu 2: dacă n=32123 se va afişa: VALE!, cifrele numărului coboară până
la 1, după care urcă
Algoritmi care determină divizorii unui număr. Numere prime.
Descompunere în factori primi.
Determinarea cmmdc şi a cmmmc dintre două numere
De la matematică putem spune că un număr natural d este divizorul lui n, dacă şi numai
dacă, restul împărţirii lui n la d este egal cu zero:
┌dacă n % d = 0 atunci
│ scrie d „îl divide pe” n
│altfel
│ scrie d „nu îl divide pe ” n
└■
Dacă vom nota cu Dn mulţimea divizorilor numărului n atunci dacă n=12 putem scrie:
D12={1, 2, 3, 4, 6, 12}, unde 1 şi 12 se numesc divizori improprii ai lui 12, iar 2, 3, 4, 6 sunt
divizorii proprii ai lui 12.
Algoritmul pentru determinarea divizorilor unui număr n dat de la tastatură este:
citeşte n (număr natural)
scrie “Divizorii numărului ”, n, “sunt:”
┌pentru d=1, n, +1
│ ┌dacă n%d=0 atunci
│ │ scrie d, ” ”
│ └■
└■
Algoritmul pentru determinarea divizorilor proprii a unui număr n, dat de la tastatură
este:
citeşte n (număr natural)
scrie “Divizorii proprii a numărului ”, n, “sunt:”
┌pentru d=2, n/2, +1
│ ┌dacă n%d=0 atunci
│ │ scrie d, ” ”
│ └■
└■
Un număr natural care are exact doi divizori se numeşte număr prim, iar numerele
naturale care nu sunt numere prime se numesc numere compuse. Plecând de la această definiţie,
algoritmul care verifică dacă numărul natural n, dat de la tastatură este prim are următoarea
formă :
citeşte n (număr natural)
nr=0
┌pentru d=1,n,+1
│ ┌dacă n%d=0 atunci
│ │ nr=nr+1
│ └■
└■
┌dacă nr=2 atunci
│ scrie n, ”este număr prim”
│altfel
│ scrie n, ”nu este număr prim”
└■
Matematic s-a demonstrat că, dacă numărul n nu are nici un divizor propriu mai mic sau
egal cu n , atunci numărul este prim. Folosind această operaţie se micşorează numărul de paşi
în a verifica dacă n este prim sau nu. Algoritmul în acest caz se poate scrie şi aşa:
citeşte n (număr natural)
ok=1 // presupun numărul dat ca fiind un număr prim
d=2
┌cât timp d<= n şi ok = 1 execută
│ ┌dacă n%d=0 atunci // am găsit un divizor propriu în [2, n ]
│ │ ok=0 // atunci n nu este prim
│ │altfel
│ │ d=d+1
│ └■
└■
┌dacă ok = 1 atunci
│ scrie n, ”este număr prim”
│altfel
│ scrie n, ”nu este număr prim”
└■
Observaţie:
a. numărul 1 nu este număr prim, dar nu este nici număr compus;
b. numărul 2 este singurul număr prim şi par.
Orice număr natural nenul, care nu este număr prim poate fi scris ca un produs de numere
naturale prime. Scrierea unui număr natural ca un produs de numere naturale prime se numeşte
descompunere în factori primi a numărului natural respectiv. Exemple:
Algoritmul care determină descompunerea în factori primi a numărului natural n are
următoarea formă:
citeşte n (număr natural) // numărul care se va descompune în factori primi
scrie ”Numărul ”, n, ” descompus în factori primi este egal cu: ”
d = 2 // primul factor la care incercăm sa împărţim pe n
┌cât timp n>=1 execută
│ s=0 //număr de câte ori factorul d îl divide pe n
│ ┌cât timp n%d=0 execută
│ │ s=s+1
│ │ n=n/d
│ └■
│ ┌dacă s ≠ 0 atunci
│ │ scrie d,” la puterea ”, s
│ └■
│ d=d+1
└■
Din punct de vedere matematic, cel mai mare divizor comun a două numere naturale
a şi b este un număr natural d, care:
divide şi pe a şi pe b:
este divizibil cu orice divizor a lui a şi b.
24200│22*52
242│2
121│11
11│11
1│1
Deci 24200= 23*52*112
Pentru a afla cel mai mare divizor comun al două sau mai multor numere naturale mai
mari decât 1 se procedează astfel:
se descompun numerele în factori primi
se iau toţi factorii primi comuni, o singură dată, la puterea cea mai mică şi se
înmulţesc între ei.
Exemplu:
Dacă a = 420 atunci descompunerea în factori primi este 420=22*3*5*7 şi dacă b = 504
atunci descompunerea în factori primi este 504=23*3
2*7, de unde rezultă că cel mai mare
divizor comun dintre cele două numere, notat cmmdc(420, 504)= 22*3*7=84
Pentru a scrie un algoritm care determină valoarea celui mai mare divizor comun dintre
două numere după modelul matematic de determinare este destul de complicat. Există algoritmi
mai simpli pentru realizrea acestui lucru:
Algoritmul lui Euclid1:
Varianta 1: Folosind operaţia de împărţire
Se citesc cele două numere naturale a şi b, iar în situaţia în care a nu este mai mare decât
b se interschimbă valorile celor două variabile. Se împarte a la b pănă la obţinerea unui rest egal
cu zero. Dacă restul obţinut în urma împărţirii lui a la b nu este zero atunci valoarea lui b va fi
transferată în variabila a, valoarea restului va fi transferat în b si se va relua algoritmul prin
calcularea restului împărţirii lui a la b, dar cu noile valori ale variabilelor a şi b. Valoarea celui
mai mare divizor comun dintre a şi b, notată cmmdc(a,b), va fi egală cu ultimul rest diferit de
zero(care va fi păstrat în variabila b).
Algoritmul în pseudocod este:
citeşte a,b // două numere naturale pentru care calculez cmmdc
┌dacă a<b atunci //interschimb valoarea lui acu valoarea lui b
│ aux=a
│ a=b
│ b=aux
└■
r=a%b // determin restul impartirii lui a la b
┌cât timp r≠ 0 execută
│ a=b
│ b=r
│ r=a%b
└■
scrie ”cmmdc dinte ”, a,” si ”, b, ” este ”,b //ultimul rest diferit de zero
Varianta 2: Folosind operaţia de scădere
Se citesc cele două numere naturale a şi b pentru care se doreşte să se calculeze valoarea
celui mai mare divizor comun. Algoritmul în acest caz este mai simplu şi presupunerea scăderii
variabilei de valoare mai mică din variabila de valoare mai mare, păstrând rezultatul obţinut în
variabila din care am scăzut. Această operaţie de scădere repetată va continua în acealaşi mod cât
timp valorile variabilelor a şi b sunt diferite. Valoarea comună la care se ajunge este chiar
valoarea celui mai mare divizor comun dintre numerele date iniţial.
1 „Algoritmul lui Euclid este străbunicul tuturor algoritmilor, deoarece este cel mai vechi algoritm netrivial care a
supravieţuit până în ziua de azi.” Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical
Algorithms, 2nd edition (1981), p. 318.
Algoritmul în pseudocod este:
citeşte a,b //două numere naturale pentru care calculez cmmdc
┌cât timp a ≠ b execută //dacă numerele sunt diferite atunci până când ajung
│ //egale din cel mai mare numar il scad pe cel mai mic
│ ┌dacă a > b atunci
│ │ a = a-b
│ │altfel
│ │ b = b-a
│ └■
└■
scrie ”cmmdc dinte ”,a,” si ”,b,” este ”,a //valoarea comuna dintre a si b
Două sau mai multe numere naturale care au cel mai mare divizor comun al lor egal cu 1
se numesc numere prime între ele.
Matematic, cel mai mic multiplu comun a două numere naturale a şi b este un număr
natural m, care:
este multiplu al lui a şi al lui b;
se divide cu orice multiplu al numerelor a şi b.
Cel mai mic multiplu comun dintre două numere naturale a şi b, notat cmmmc(a,b) se
calculează cu relaţia:
),(
*),(
bacmmdc
babacmmdc
deci algoritmul de determinare a cmmmc(a,b) este:
citeşte a,b // numere naturale
// determină cmmdc(a,b) cu una din variantele Algoritmului lui Euclid
scrie ”cmmdc dintre”, a, ” si ”, b, ” este:”
c=a*b
//deoarece valorile iniţiale ale variabilelor a şi b se alterează după
//rularea algoritmului lui Euclid voi calcula produsul lor inainte de a le
//strica valoarea
┌cât timp a ≠ b execută
│ ┌dacă a > b atunci
│ │ a = a-b
│ │altfel
│ │ b = b-a
│ └■
└■
scrie c/a //a=b după incheierea algoritmului de determinare a cmmdc si
//reprezinta chiar valoarea determinată
Aplicaţii rezolvate
1. Se citeşte de la tastatură un număr natural n. Se cere să se
calculeze suma divizorilor săi.
Exemplu: dacă n=8 divizorii săi sunt {1, 2, 4, 8} deci va trebui să afişăm valoarea 15= 1+2+4+8
Algoritmul în pseudocod este:
citeşte n //număr natural
s=0 // iniţializez suma divizorilor lui n cu zero
┌pentru d=1,n,+1 // caut posibilii divizori a lui n în intervalul [1,n]
│ ┌dacă n%d = 0 atunci //dacă d este divizor a lui n atunci
│ │ s=s+d //il adaug la suma
│ └■
└■
scrie ” suma divizorilor lui ”,n,” este ”,s
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,s;
void main()
{ clrscr();
cout<<"n="; cin>>n;
for(int d=1;d<=n;d++)
if(n%d==0)
s=s+d;
cout<<"Suma divizorilor lui"<<n;
cout<<" este "<<s;
getch();
}
2. Se citeşte de la tastatură un număr natural n. Se cere să se calculeze numărul divizorilor săi.
Exemplu: dacă n=8 divizorii săi sunt {1, 2, 4, 8} deci va trebui să afişăm valoarea 4
Algoritmul în pseudocod este:
citeşte n //număr natural
nr=0 // iniţializez numărul divizorilor lui n cu zero
┌pentru d=1,n,+1 // caut posibilii divizori a lui n în intervalul [1,n]
│ ┌dacă n%d = 0 atunci //dacă d este divizor a lui n atunci
│ │ nr=nr+1 //număr ca am gasit un divizor
│ └■
└■
scrie ” numărul divizorilor lui ”,n,” este ”,nr
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,nr;
void main()
{ clrscr();
cout<<"n="; cin>>n;
for(int d=1;d<=n;d++)
if(n%d==0)
nr++ş
cout<<"Numarul divizorilor lui"<<n;
cout<<" este "<<nr;
getch();
}
3. Se citeşte de la tastatură un număr natural n. Se cere să se afişeze pe ecran numerele prime mai mici sau egale cu n.
Exemplu: dacă n = 20 atunci trebuie afişate valorile 2 3 5 7 11 13 17 19
Algoritmul în pseudocod este:
citeşte n //număr natural
┌dacă n<=1 atunci
│ scrie ”Nu exista numere prime mai mici sau egale cu 1”
│altfel
│ scrie ”Numerele prime mai mici sau egale cu ”, n,” sunt:”
│ ┌pentru x=2,n,+1 // consider fiecare numar x din intervalul [2,n]
│ │ // verific daca numarul x este prim
│ │ ok=1, d=2
│ │ ┌cât timp d<=radical din x şi ok = 1 execută
│ │ │ ┌dacă x%d=0 atunci
│ │ │ │ ok=0 // atunci x nu este prim
│ │ │ │altfel
│ │ │ │ d=d+1
│ │ │ └■
│ │ └■
│ │ ┌dacă ok = 1 atunci // dacă x este prim atunci îl afişez
│ │ │ scrie x, ” ”
│ │ └■
│ └■
│
└■
Program C++ #include<iostream.h>
#include<conio.h>
#include<math.h>
int n,s;
void main()
{ clrscr(); cout<<"n="; cin>>n;
if (n<=1)cout<<"Nu exista numere prime mai mici sau egale cu 1!";
else
{cout<<"Numere prime mai mici sau egale cu "<<n<<" sunt :"<<endl;
for(int x=2;x<=n;x++)
{ int d=2,ok=1;
while (d<=sqrt(x) && ok)
if (x%d==0)
ok=0;
else
d++;
if(ok)cout<<x<<" ";
}
}
getch();
}
Rezultat afişat pe ecran
sau
4. Se dă un număr natural n. Se cere să se determine factorul la
puterea cea mai mare care apare în descompunerea în factroi
primi a numărului dat.
Exemplu: dacă n=24200, atunci descompunerea în factrori primi a lui este 24200=23*5
2*11
2, se
observă că factorul 2 apare la cea mai mare putere în descompunere, deci pe ecran trebuie afişată
valoarea 2.
Algoritmul în pseudocod este:
citeşte n // număr natural
f_max=0 // factorul maxim initial este 0
p_max=0 // puterea acestui factor este initial tot 0
d=2 // primul posibil factor din descompunere este 2
┌cât timp n>=1 execută
│ s=0 //număr de câte ori factorul d îl divide pe n
│ ┌cât timp n%d=0 execută
│ │ s=s+1
│ │ n=n/d
│ └■
│ ┌dacă s ≠ 0 atunci//daca d a fost factor vad daca are cea mai mare putere
│ │ ┌dacă s > p_max atunci
│ │ │ p_max=s; //actualizez puterea maxima
│ │ │ f_max=d; //pastrez factorul la putrea maxima
│ │ └■
│ └■
│ d=d+1
└■
scrie “Factorul care apare la puterea maxima in descompunerea in foactori
primi este ”, f_max
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,s,d,p_max,f_max;
void main()
{ clrscr();
cout<<"n="; cin>>n;
d=2;
while(n>1)
{ s=0;
while(n%d==0)
{s++;
n=n/d;
}
if(s>p_max)
{ p_max=s;
f_max=d;
}
d++;
}
cout<<"factorul la puterea maxima este ”;
cout<<f_max;
getch();
}
5. Se citesc de la tastatură n numere naturale. Se cere să se
determine cel mai mare divizor comun dintre cele n numere.
Exemplu: dacă n=4 şi numerele citite sunt 12, 48, 96 şi 192 atunci cel mai mare divizor comun
al lor este 12.
Pentru a determina acest lucru vom proceda astfel:
Citim iniţial n ca să stim câte numere vom prelucra
Citim primele două numere
Determinam cmmdc dintre primele doua numere citite
Pentru celelalte n-2 numelre procedăm astfel
o Citim un număr
o Determinăm cmmdc dintre numarul citit si cmmdc determinat anterior
Algoritmul în pseudocod este:
citeşte n // număr natural care precizează câte numere vom prelucra
//citeşte primele două numere şi determină cmmdc dintre ele
citeste a,b
┌cât timp a ≠ b execută //dacă numerele sunt diferite atunci până când ajung
│ //egale din cel mai mare numar il scad pe cel mai mic
│ ┌dacă a > b atunci
│ │ a = a-b
│ │altfel
│ │ b = b-a
│ └■
└■
┌pentru i=3,n,+1
│ citeste b //citeste următorul număr
│ ┌cât timp a ≠ b execută
│ │ ┌dacă a > b atunci
│ │ │ a = a-b
│ │ │altfel
│ │ │ b = b-a
│ │ └■
│ └■
└■
scrie ”cmmdc-ul numerelor citite este ”, a
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
int n,a,b;
void main()
{clrscr();
cout<<"n="; cin>>n;
cout<<"dati un numar:"; cin>>a;
cout<<"dati un numar:"; cin>>b;
while(a!=b)
if(a>b)
a=a-b;
else
b=b-a;
for(int i=3;i<=n;i++)
{
cout<<"dati un numar:"; cin>>b;
while(a!=b)
if(a>b)
a=a-b;
else
b=b-a;
}
cout<<"cmmdc dintre numerele date este ",a;
getch();
}
Aplicaţii practice
1. Se dau două numere naturale a şi b. Dacă cele două numere sunt prime între ele, atunci să se calculeze suma cifrelor celor
două numere, altfel să se descompună în factori primi numărul
mai mare.
Exemplu: Dacă a= 84 şi b=180, nu sunt numere prime între ele, cmmdc(84,180)=12 şi pe ecran
se va afişa descompunerea în factori primi al numărului mai mare 22*3
2*5.
Dacă a=85 şi b=87, sunt prime între ele şi pe ecran va fi afişat 28=8+5+8+7
2. Afişaţi toate numere prime din intervalul [a, b], unde a şi b sunt două numere naturale mai mici de 10000, şi a<=b.
Exemplu: dacă a a=10 şi b=20 numerele prime din intervalul [10,20] sunt 11, 13, 17 şi 19.
3. Se citeşte un număr natural n,(n<=10000) care nu este număr prim. Se cere să se determine care este cel mai mare număr
prim, dar mai mic decât n şi care este cel mai mic număr prim
dar mai mare cu n.
Exemplu: dacă n este 100, cel mai mare numar prim mai mic decăt 100 este 97, iar cel mai mic
număr prim mai mare decât 100 estr 101.
4. Să se determine toate numerele perechile de numere prime
gemene mai mici decât un număr natural n, citită de la
tastatură (n<=10000). Două numere formează o pereche de numere
prime gemenene.
Exemple: dacă n=20 atunci se vor afişa perechile (3, 5), (5, 7), (11, 13), (17, 19).
5. Se citeşte de la tastaură un număr natural n(n<=10000). Se
cere să se afişeze primele n numere prime.
Exemplu: dacă n=10 atunci primele 10 numere prime sunt 2,3,5,7,11,13,17,19, 23,29.
6. Se citeşte de la tastaură un număr natural n, (n<=10000). Se cere să calculeze suma numerelor divizibile la 3 mai mici sau
egale cu n.
Exemplu: dacă n=16 atunci se va afişa 45, s= 3+6+9+12+15=45.
7. Determinaţi şi afişaţi pe ecran toate numere naturale care
împărţite la 24, 30,18 dau restul 7.
Exemplu: dacă n=2000 se vor afişa numerele 367, 727, 1087, 1447, 1807.
8. Se dau două numere naturale a şi b. Să se afişeze toţi
divizorii comuni celor două numere.
Exemplu: dacă a=180 şi b=84 atunci se vor afisa 1, 2, 3, 4, 6, 12.
9. Se citesc două numere naturale a şi b. Se cere să se determine
dacă sunt numere prime între ele.
Exemplu: Dacă a= 84 şi b=180, nu sunt numere prime între ele, cmmdc(84,180)=12 iar dacă
a=85 şi b=87, sunt prime între ele.
10. Se citeşte de la tastatură un număr natural n, Să se
determine cel mai mic număr natural are are are exact n
divizori.
Exemplu: dacă n=4 atunci se va afişa 6 care are 4 divizori 1, 2, 3, 6.
11. Un număr natural este perfect dacă el este egal cu suma
divizorilor săi mai mici decât el. Scrieţi un program care
verifică dacă un număr este perfect sau nu.
Exemplu: daca n este 6 atunci el este numar perfect 6=1+2+3, daca n este 8 atunci el nu este
număr perfect 1+2+4=7.
12. Se citeşte un număr natural n (n<=1000). Se cere să se
afişeze mulţimea numerelor naturale care sunt prime cu n.
Exemplu: dacă n=20 atunci mulţimea numerelor prime cu 20 este {3, 7, 9, 11, 13, 17, 19}
13. Se citeşte un număr natural n (n<=1000). Se cere să se
afişeze mulţimea divizorilor săi şi numărul de divizori
proprii.
Exemplu: dacă n=12 atunci mulţimea divizorilor este {1, 2, 3, 4, 6, 12} şi el are 4 divizori
proprii.
14. Se citesc două numere naturale a şi b, care reprezintă
numărătorul şi numitorul unei fracţii b
a. Scrieţi un program
care are drept scop aducerea la forma ireductibilă a fracţiei
date.
Exemplu: dacă a=10 şi b=100. cmmdc(10,100)= 10 rezultă fracţia 10
1.
15. Se citesc n numere naturale de la tastatură. Să se
determine cu câte zerouri se sfârşeşte produsul acestora, fără
a efectua produsul lor.
Exemplu: dacă n=5 şi numerele citite sunt în ordine 23, 48, 15, 25, 34 atunci produsul lor se
termină în 3 zerouri.
16. Două numere întregi x şi y sunt prietene, dacă şi numai
dacă suma divizorilor numărului x este egală cu suma
divizorilor numărului y. Scrieţi un program care afişează
toate numerele prietene din intervalul [a,b].
Exemplu: dacă a=10 şi b=25 numerele prietene sunt (10, 17), (14, 15), (14,23), (15, 23), (16,25).
17. Orice număr par mai mare decât 4 se poate scrie ca sumă de
numere prime. Scrieţi un program care citeşte de la tastatură
un număr natural, par n şi îl descompune ca sumă de numere
prime.
Exemplu: dacă n=292 atunci el se formează din 283+7+2.
18. Se citesc de la tastatură două numere naturale notate n şi
k. Se cere să se afişeze toate numerele mai mic sau egale cu n
care au exact k divizori.
Exemplu: dacă n=10 şi k=2 se vor afisa 2, 3, 5, 7.
19. Se citesc de la tastatură n numere naturale. Se cere să se
determine câte dintre numere citite sunt numere prime şi să se
calculeze suma numerlor care nu sunt prime.
Exemplu: dacă n=7 şi se vor citi numerele 2, 4, 5, 6, 11, 15 atunci se va afişa pe ecran mesajul
„sunt 3 numere prime, iar suma numerelor care nu sunt prime este 25”.
20. Se consideră trei numere naturale n,a şi b (a≤ b≤ n). Să se
creeze un program care permite afişarea factorilor primi ce
aparţin intervalului [a, b] şi a puterilor la care aceştia
apar în descompunerea lui n.
Exemplu: dacă n=36 a=1 şi b=10 se vor afisa: 22 şi 3
2
Conversii între baze de numeraţie
Toate calculele pe care le efectuăm în ziua de azi sunt efectuate în sistemul de numeraţe
zecimal, sau altfel spus în baza 10 de numeraţie. În continuare vom prezenta un algoritm simplu,
didactic, care realizează conversii de numere în una din bazele de numeraţie b 10,2 . În general
un număr scris în baza b are următoarea formă generală:
xn-1xn-2 ...x1x0, x-1x-2...x-m= x*bn-1+x*bn-2
+ ...x*b1+x*b0
+x*b-1+x*b-2
+...x*b-m =
1n
mi
i
i bx ,
unde xi [0,b-1].
Exemplu: dacă b=10 atunci numărul 123,45=1*102+2*10
1+3*10
0+4*10
-1+5*10
-2 .
Conversia din baza 10 în baza b
Trecerea unui număr de la o bază la alta presupune aflarea unei secvenţe unice de resturi
conform algoritmului următor:
numărul se împarte la bază şi se reţine restul obţinut. Acesta constituie ultima
cifră din reprezentarea în acea bază;
câtul obţinut în urma acestei prime împărţiri este din nou împărţit la bază şi se
reţine iaraşi restul. Acest rest constituie a doua cifră, în ordinea de la dreapta la
stânga, a reprezentării în baza aleasă.
algoritmul continuă până când câtul obţinut este zero. Ultimul rest al împărţirii la
bază va reprezenta cea mai semnificativă cifră a numărului în baza în care s-a
facut conversia.
Tabelul următor prezinta paşii acestui algoritm pentru trecerea numarului 25 în baza 2:
Nr. bază
25:2= 25 2 (25)10=(11001)2
rest 1 12 2
0 6 2 Observaţie:
0 3 2 pe fond galben sunt notate
câturile obţinute la fiecare
împărţire la bază 1 1 2
1 0
Pentru ascrie un algoritm care să realizeze această conversie vom proceda astfel:
o citim numărul de transformat
o citim baza în care dorim să facem conversia
o începem să împărţim numărul dat la bază, iar cu resturile obţinute formăm un nou
număr(care de fapt va fi scris după regula sistemului zecimal)
Algoritm în pseudocod:
//conversia din baza 10 în baza b din [2,10]
citeşte n,b // numere naturale, n-numărul de transformat, b-baza
m=0 // va conţine rezultatul conversiei
p=1 // puterile lui 10 iniţial 100=1
┌cât timp n≠0 execută
│ r=n%b // calculez restul împărţirii numărului la bază
│ m=m+r*p // formez valoarea noului număr
│ p=p*10 // cresc puterea lui 10
│ n=n/b // calculez câtul împărţirii numărului la bază
└■
scrie m // valoarea numărului în baza b
Această variantă de algoritm este una didactică şi se utilizează pentru conversii de
numere naturale relativ mici, valoarea variabilei p creşte exponenţial şi nu poate depăşi 10 cifre.
Pentru numere mai mari se vor utiliza alţi algoritmi şi alte tipuri de date pe care îî veţi studia mai
târziu.
Conversia din baza 10 în baza b
De exemplu dacă baza de numeraţie este 2 şi valoarea numărului n=(110011)2 atunci
transformarea lui în baza 10 se face astfel:
(110011)2=1*20+1*2
1+0*2
2+0*2
3+1*2
4+1*2
5=1+2+16+32=(51)10
Operaţia de trecere a unui număr scris în baza b la baza 10 se realizează după următorul
algoritm în pseudocod:
//conversia unui număr n scris baza b, în baza 10
citeşte n,b // n – numărul de transformat, b baza în care este scris n
p=1 // b0=1
m=0 // va contine numarul în baza 10
┌cât timp n≠0 execută
│ c=n%10 // extrag cate o cifra din numarul dat
│ m=m+c*p // formez numarul adunând cifrele extrase din n cu puteri ale
│ // bazei
│ p=p*b // cresc puterea bazei
│ n=n/10 // elimin ultima cifra din n
└■
scrie m // valoarea numărului în baza 10
Pentru a realiza conversia unui număr din baza b1 în baza b2 vom proceda astfel:
o transformăm numărul din baza b1 în baza 10;
o transformam numărul obţinut anterior din baza 10 în baza b2.
Aplicaţii rezolvate
1. Se dă un număr natural n, scris în baza 10. Sa se verifice dacă numărul de cifre de zero este egal cu numărul de cifre de
1 în reprezentarea numărului în baza doi.
Exemplu: dacă n=(49)10 =(110001)2 are trei cifre de 1 şi trei cifre de zero, deci pe ecran trebuie
afişat „Da, numar egal de cifre de 0 şi 1”;
dacă n=(54)10 =(110110)2 are patru cifre de 1 şi două cifre de zero, deci pe ecran trebuie afişat
„Nu, numar diferit de cifre de 0 şi 1”.
Algoritmul în pseudocod este:
citeşte n //număr natural care trebuie transformat în baza 2
m=0 //conţine rezultatul conversiei numărului n în baza 2
nr0=0, nr1=0 //nr0-număr de cifre de 0 şi nr1-număr de cifre de 1 din m
p=1 //100=1
┌cât timp n≠0 execută
│ r = n%2 // determin restul împarţirii lui n la 2, poate fi 0 sau 1
│ ┌dacă r = 0 atunci
│ │ nr0=nr0+1 //număr ca am gasit o cifra de 0
│ │altfel
│ │ nr1=nr1+1 //număr ca am gasit o cifră de 1
│ └■
│ m=m+r*p // formez numărul în baza 2
│ p=p*10 // cresc puterea lui 10
│ n=n/2 // împart n la baza 2
└■
scrie m // afişez valoarea lui n în baza 2
// afişez rezultatul
┌dacă nr0 = nr1 atunci
│ scrie ”Da, are număr egal de cifre de 0 şi 1!”
│altfel
│ scrie ”Nu, numarul de cifre de 0 şi 1 este diferit”
└■
Program C++ Rezultat afişat pe ecran #include< iostream.h>
#include<conio.h>
long n,m,nr0,nr1,r,p;
void main()
{ clrscr();
cout<<"n="; cin>>n;
p=1;
while(n!=0)
{r=r%2;
if(r==0)
nr0++;
else
nr1++;
m=m+r*p;
p=p*10;
n=n/2;
}
cout<<"numarul in baza 2 este "<<m;
cout<<endl;
if(nr0==nr1)
cout<<"Da are un numar egal de
cifre de 0 si 1";
else
cout<<"Nu, are numar diferit
de cifre de 0 si 1";
getch();
}
sau:
2. Se citeşte un număr natural n scris în baza b1. Secieţi un
program care să transforme numărul în baza b2 (b1, b2 numere
naturale din [2,10]) .
Exemplu: dacă n=2301, b1= 4, iar b2= 9 atunci rezultatul va fi: (216)9 adică:
(2301)4=(177)10=(216)9
Algoritmul în pseudocod este:
citeşte n,b1,b2
// transformăm numărul n din baza b1 în baza 10
p=1
m=0 // contine rezultatul conversiei lui n din baza b1 în baza 10
┌cât timp n≠0 execută
│ r = n%10
│ m = m+r*p
│ p = p*b1
│ n = n/10
└■
// transformăm numărul m din baza 10 în baza b2
p=1
n=0 // contine rezultatul conversiei lui m din baza 10 în baza b2
┌cât timp m≠0 execută
│ r = n%b2
│ m = m+r*p
│ p = p*10
│ n = n/b2
└■
scrie n // afişez rezultatul
Program C++ Rezultat afişat pe ecran #include<iostream.h>
#include<conio.h>
long n,m,r,p,b1,b2;
void main()
{ clrscr();
cout<<"Numarul de transformat n=";
cin>>n;
cout<<"Baza in care este scris numarul b1=";
cin>>b1;
cout<<"Baza in care fac conversia b2=";
cin>>b2;
//conversia lui n din b1 in baza 10
p=1;
while(n!=0)
{r=n%10;
m=m+r*p;
p=p*b1;
n=n/10;
}
cout<<"numarul in baza 10 este "<<m<<endl;
//conversia lui m din baza 10 in b2
p=1;
while(n!=0)
{r=m%b2;
n=n+r*p;
p=p*10;
m=m/b2;
}
cout<<"numarul in baza "<<b2<<" este "<<n;
getch();
}
Aplicaţii propuse
1. Se dă un număr natural n. Să se determine dacă este palindrom în baza doi. În caz negativ să se precizeze câte cifre are
numărul iniţial în baza opt.
Exemplu: Un număr natural este palindrom dacă şi numai dacă el este egal cu numărul obţinut
prin inversarea cifrelor sale. Atunci dacă n=(51)10=(110011)2 atunci el este palindrom în baza 2,
iar dacă numărul iniţial este n=(54)10=(110110)2=(66)8 se observă că el nu este palindrom în baza
doi şi conţine două cifre în baza 8.
2. Se citeşte de la tastatură un număr natural scris în baza 2. Să se verifice dacă în baza 10 reprezintă un număr prim.
Exemplu: dacă numărul iniţial este n=(10011)2=(19)10 atunci în baza 10 el este un număr prim,
iar dacă iniţial citim numărul n=(1001110)2=(78)10 atunci observăm uşor că el nu este număr
prim în baza 10.
3. Se dă un număr natural n (n≤125) citit de la tastatură. Să se afişeze toate numerele mai mici decât n, care în baza doi
conţin patru cifre de unu. Să se precizeze la sfârşit câte
numere au îndeplinit condiţia cerută.
Exemplu: dacă n=35 se vor afişa numerele: 15, 23, 27, 29, 30 sunt 5 numere care îndeplinesc
condiţia cerută
4. Se citesc două numere naturale n1 scris în baza b1 şi n2 scris
în baza b2,unde b1,b2<10. Să se determine care număr este mai
mare.
Exemplu: (245)6<(131)9
5. Se citeşte un număr natural n şi o bază b. Să se verifice dacă numărul poate fi scris în baza b.
Exemplu: dacă n=216 şi b=9 atunci rezultatul este „Da”, iar dacă n=216 şi b=5 atunci rezultatul
este „Nu”
6. Se citeşte un număr natural scris în baza 2, deci format numai din cifre de 0 şi 1 (n≤11111). Să se afişeze valoarea lui în
