Exercitii rezolvate
A. Fie declarările: int a[20]; float b[30];
1. Precizați care dintre elementele din lista de mai jos sunt corecte din punct de vedere sintactic:
a. cin>>a[22];
b. cin>>b;
c. b[6]=20;
d. cout<<a[2] % b[2];
e. a[5]+1=0;
f. cout<<b[1];
g. b[2]=a[10];
h. cout<<a;
i. cout<<a[2]%5;
j. cout<<int(b[1]);
Soluție: sunt corecte, din punct de vedere sintactic variantele: a, c, f, g, h, i, j. Trebuie făcute observațiii asupra sintaxelor de la punctele a și h, care, deși, neintuitive, sunt permise de compilator.
B. Interpretați secvențele de cod următoare și răspundeți cerințelor formulate !
1. Ce va afișa secvența:
s=0;
for(i=0;i<5;i++)
for(j=i+1;j<5;j++)
if(a[i][j] %2) s=s+a[i][j];
cout<<n;
for (i=1;i<=n;i++) cin>>a[i];
m=a[1];
for(i=1;i<=n;i++)
if (a[i]% 2 !=0)
if (m>=a[i]) m=a[i]; cout<<m;
daca ar fi citite, în ordine, valorile: 8,1,7,10,3,12,1,2,6 ?
Soluție: Secvența determină valoarea minimă dintre elementele impare ale vectorului. Prin urmare, valoarea afișată va fi 1
3. Ce va afișa secvența:
s = 0;
for(i = 0; i < 4; i++)
s+=a[i][n-i-1];
cout<<s;
dacă matricea a ar avea conținutul de mai jos
2 3 4 1
3 5 4 2
4 5 3 2
3 5 4 3
Soluție: Secvența determină suma elementelor aflate pe diagonala secundară a matricei. Valoarea afișată va fi: 13
C. Scrieți programe C++ pentru rezolvarea următoarelor probleme !
1. Se citește un număr natural n de cel mult 9 cifre. Formați și afișați cel mai mare numar posibil din cifrele sale. Exemplu: n=3972032. Ar trebui afișat: 9733220
Soluție:
#include <iostream>
using namespace std;
//functia ordonare sorteaza, folosind metoda bulelor, un sir x, dat ca parametru
void ordonare(int x[10], int n) {
int pozitie, i, inv, aux;
do {
inv=0;
for(i=0;i<n-1;i++) if(x[i]<x[i+1])
{ aux=x[i]; x[i]=x[i+1]; x[i+1]=aux; inv=1; } }
while(inv); }
int main()
{
int cifre[10],i,j;
long n;
cin>>n; i=0;
//formam, pas cu pas, sirul cifrelor numarului dat
while(n)
cifre[i]=n%10; i++; n/=10; }
//sortam descrescator sirul cifrelor
ordonare(cifre, i);
for(j=0;j<i;j++) cout<<cifre[j];
return 0; }
2. Scrieţi un program C++ care citeşte de la tastatură un număr natural n şi apoi cele n elemente, numere naturale cu cel mult 4 cifre fiecare, ale unui tablou unidimensional a. Programul afişează pe linii separate permutările circulare ale tabloului.
Soluție: #include <iostream> using namespace std; int main() { int i,j,aux,n,a[100]; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=1;i<=n;i++) { aux=a[0]; for(j=1;j<n;j++) a[j-1]=a[j]; a[n-1]=aux; for(j=0;j<n;j++) cout<<a[j]<<’ ’; cout<<’\n’; } return 0; }
3. Se citeşte de la tastatură un număr natural n (n≤1000000000) şi apoi n cifre separate prin spaţii. Se cere să se afişeze pe ecran cele n cifre citite, în ordine crescătoare, separate prin câte un spaţiu.
Exemplu: pentru n=19 şi cifrele 3 3 0 9 2 1 2 1 3 7 1 5 2 7 1 0 3 2 3 se va afişa pe ecran 0 0 1 1 1 1 2 2 2 2 3 3 3 3 3 5 7 7 9.
Soluție: #include <iostream> using namespace std; int main() { int i,j,n,c,frecv[10]; //initializam vectorul f, folosit pentru a determina frecventa cu care apar cifrele for(i=0;i<10;i++) frecv[i]=0; cin>>n; for(i=0;i<n;i++) {cin>>c; frecv[c]++;} for(i=0;i<10;i++) { if(frecv[i]) for(j=1;j<=frecv[i];j++) cout<<i; } return 0; }
4. Se citesc de la tastatură două numere naturale nenule n şi m (2≤m≤100, 2≤n≤100), iar apoi se construieşte în memorie şi se afişează o matrice A cu n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) cu proprietatea că fiecare element Aij memorează cea mai mică dintre valorile indicilor i şi j (1≤i≤n, 1≤j≤m). Matricea se va afişa pe ecran astfel: fiecare linie a matricei pe o linie separata a ecranului, elementele fiecărei linii vor fi separate prin câte un spaţiu. Exemplu: pentru n=4 şi m=5 se va afişa matricea de mai jos. 1 1 1 1 1 1 2 2 2 2 1 2 3 3 3 1 2 3 4 4
Soluție: #include <iostream> using namespace std; int main() { int i,j,m,n,mat[100][100]; cin>>m>>n; for(i=1;i<=m;i++) for(j=1;j<=n;j++) mat[i][j]=i<j?i:j; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) cout<<mat[i][j]<<' '; cout<<'\n'; } return 0; }
5. Se consideră tabloul bidimensional cu n linii şi n coloane ce conţine numere naturale cu cel mult patru cifre fiecare. Scrieţi programul C/C++ care citeşte de la tastatură numărul natural n (2≤n≤23) şi cele n*n elemente ale tabloului şi apoi afişează pe ecran elementele primului pătrat concentric, separate prin câte un spaţiu. Pătratul este parcurs în sensul acelor de ceasornic începând din colţul său stânga-sus, ca în exemplu. Primul pătrat concentric este format din prima şi ultima linie, prima şi ultima coloană a tabloului. Exemplu: pentru n=5 şi tabloul alăturat,
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 se va afişa:
1 2 3 4 5 1 6 2 7 6 5 4 3 7 2 6
Soluție: #include <iostream> using namespace std; int main() { int i,j,m,n,mat[100][100]; cin>>m>>n; for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>mat[i][j]; for(i=1;i<=n;i++) cout<<mat[1][i]<<' '; for(i=2;i<=m;i++) cout<<mat[i][n]<<' '; for(i=n-1;i>=1;i--) cout<<mat[m][i]<<' '; for(i=m-1;i>1;i--) cout<<mat[i][1]<<' '; return 0; }
----------------------------------------------
https://www.edusoft.ro/fisiere/aplicatii_c_cpp_patrut.pdf
citeşte n - fie direct, de exemplu cin >> n
fie primind ca parametru, main(int n)
fie ciclând pe mai multe valori: for(n = 10; n < 20; n++)
determină A; dacă A % 4 != 0 atunci "exit(0)" (nu există soluţie)
alocă memorie (în Heap) pentru tabloul st[]
expand(0) - declanşează mecanismul backtracking de generare a soluţiilor
https://www.edusoft.ro/fisiere/aplicatii_c_cpp_patrut.pdf
Exerciţii de programare în C, C++
Enunţ, analiză, schema programului
Putem obţine suma 1 pentru numerele 1..n?
Adună sau scade între ele numerele 1, 2, ..., n încât să rezulte 1.
Adună sau scade între ele numerele 1, 2, ..., n încât să rezulte 1.
Analiză, reformulare
Fie A şi B suma numerelor 1..n care se vor aduna, respectiv se vor scădea. Avem A + B = suma tuturor 1..n = n*(n+1) / 2 şi pe de altă parte se cere ca A - B = 1.
Rezultă că A = ( n*(n+1) + 2 ) / 4 şi A trebuie să fie întreg - deci putem reformula astfel:
Să se determine toate sistemele de numere distincte 1..n care să aibă suma A.
Să se determine toate sistemele de numere distincte 1..n care să aibă suma A.
Exemplu
n = 5 => A = 8 => (1, 2, 5), (1, 3, 4), (3, 5)
(1, 2, 5) corespunde soluţiei 1 + 2 - 3 - 4 + 5 (= 1)
n = 40 => A = 410.5 => nu există soluţie
(1, 2, 5) corespunde soluţiei 1 + 2 - 3 - 4 + 5 (= 1)
n = 40 => A = 410.5 => nu există soluţie
Ilustrarea algoritmului - metoda backtracking
n = 5 => A = 8 => există soluţii. Descriem generarea soluţiilor în acest caz.
Folosim un vector cu 5 elemente ST[]: __ __ __ __ __ în care vom constitui soluţiile.
Soluţie va fi orice sistem de valori (ST[0], ST[1], ..., ST[_id]) unde _id < 5, astfel încât
1 <= ST[0] < ST[1] < ... < ST[_id] <= 5 şi suma acestor valori este egală cu A=8.
1 <= ST[0] < ST[1] < ... < ST[_id] <= 5 şi suma acestor valori este egală cu A=8.
primul pas ST[]: 1 __ __ __ __ (punem 1 pe rangul 0 din ST[]) extindem ST[]: 1 2 __ __ __ (1 + 2 < 8 => soluţie parţială posibil de extins) avans ST[]: 1 2 3 __ __ (1 + 2 + 3 < 8) avans ST[]: 1 2 3 4 __ (1 + 2 + 3 + 4 > 8 => imposibil de ajuns la o soluţie) revenire ST[]: 1 2 4 __ __ (1 + 2 + 4 < 8 => extindem) avans ST[]: 1 2 4 5 __ (1 + 2 + 4 + 5 > 8 => imposibil => revenire) revenire ST[]: 1 2 5 __ __ (1 + 2 + 5 = 8 => scrie soluţia => revenire) revenire ST[]: 1 3 __ __ __ (1 + 3 < 8 => avansăm) avans ST[]: 1 3 4 __ __ (1 + 3 + 4 = 8 => scriem soluţia şi revenim) revenire ST[]: 1 3 5 __ __ (1 + 3 + 5 > 8 => revenim) revenire ST[]: 1 4 __ __ __ (1 + 4 < 8 => avansăm) avans ST[]: 1 5 __ __ __ (1 + 5 < 8 => revenim, fiindcă nu putem extinde cu 6) revenire ST[]: 2 __ __ __ __ avans ST[]: 2 3 __ __ __ (2 + 3 < 8 => avansăm) avans ST[]: 2 3 4 __ __ (2 + 3 + 4 > 8 => revenim) revenire ST[]: 2 4 __ __ __ (2 + 4 < 8 => avansăm) avans ST[]: 2 4 5 __ __ (2 + 4 + 5 > 8 => revenim) revenire ST[]: 2 5 __ __ __ (2 + 5 < 8 => revenim, neputând extinde cu 6) revenire ST[]: 3 __ __ __ __ avans ST[]: 3 4 __ __ __ avans ST[]: 3 4 5 __ __ revenire ST[]: 3 5 __ __ __ (scriem soluţia) revenire ST[]: 4 __ __ __ __ avans ST[]: 4 5 __ __ __ (imposibil) revenire ST[]: 5 __ __ __ __ (aici încheiem: extinderea/revenirea sunt imposibile)
Schema programului
Variabilele necesare:
nA = n*(n+1) + 2; dacă A % 4 != 0 atunci "nu există soluţie"st[] tablou pentru constituirea soluţiilor (prin metoda backtracking)
Funcţiile necesare:
is_good(index) - testează dacă valoarea curentă 1..n plasată în st[] la indexul curent 0..n-1 poate conduce la o soluţieout_sol(index) - scrie soluţia obţinută în st[] (între rangurile 0..index)expand(index) - înscrie în st[index] valoarea curentă 1..n şi testează is_good(index), procedând în consecinţă: dacă s-a obţinut o soluţie atunci out_sol(index); altfel, dacă suma valorilor înscrise în st[] până la rangul index este mai mică decât A atunci se avansează la rangul următor, prin reapelare: expand(index+1)main() - firul principal de execuţie decurge după schema următoare:citeşte n - fie direct, de exemplu cin >> n
fie primind ca parametru, main(int n)
fie ciclând pe mai multe valori: for(n = 10; n < 20; n++)
determină A; dacă A % 4 != 0 atunci "exit(0)" (nu există soluţie)
alocă memorie (în Heap) pentru tabloul st[]
expand(0) - declanşează mecanismul backtracking de generare a soluţiilor
Implementare (în orele de "laborator")
"Implementare" înseamnă transformarea planului de rezolvare (conturat mai sus) într-un program executabil. Întâi trebuie să scriem (folosind un editor de text) un program-sursă în C sau în C++. Acesta va trebui apoi să fie compilat (folosind un compilator de C sau C++); compilatorul este un program utilitar independent care transformă instrucţiunile din textul-sursă care îi este prezentat, în instrucţiuni executabile ("cod maşină"). Dacă este cazul, folosim apoi un "link-editor" - un utilitar care "leagă" fişierul-obiect (sau "codul maşină") furnizat de compilator cu alte fişiere-obiect preexistente (corespunzătoare directivelor de includere existente în program). În final se obţine "programul executabil", care va putea fi lansat (în principiu…) ca oricare altă aplicaţie existentă.
Această cale - editor de text => compilator => link-editor - constituie o metodologie unitară de lucru, fundamentală (aceeaşi pentru oricare sistem de operare, limbaj, compilator, interpretor). Dar - în special pentru C, C++ - au fost create şi diverse "medii de programare" IDE, care oferă o interfaţă grafică din care programatorul poate realiza toate operaţiile folosind meniurile, mousul şi diverse combinaţii de taste. De obicei, nu are importanţă pe ce cale obţinem executabilul; dar constatăm că aceia care s-au deprins să depindă de IDE rămân eventual cu impresia că singurul lucru pe care-l au de făcut este să scrie programul şi să tasteze apoi CTRL-F9; mai grav este că rămân cu impresia greşită că pentru a folosi executabilul realizat trebuie să încarce întâi IDE, apoi să folosească meniul OPEN pentru a deschide în editorul încorporat programul-sursă respectiv şi să tasteze în final CTRL-F9 pentru a şi executa programul.
Cea mai proastă "tehnică" pe care am văzut-o este aceasta: deschide calculatorul (şi aşteaptă să se încarce Windowsul); click pe iconiţa "Borlandc" (se deschide IDE-ul Borland C++ 3.1); între timp, deschide caietul/manualul la programul de "implementat", aşează-l verticat lângă ecran şi începe să scrii (echivalent: unul dictează, celălalt scrie); când ai terminat de copiat programul în calculator, mai tastezi CTRL-F9 şi gata… (trecem la altă problemă, că pe asta am înţeles-o; "algoritmul este important, nu programul; informatică înseamnă algoritmi"-punct). Cu asemenea obicei şi cu asemenea concepţii reducţioniste, poţi cel mult să înveţi să dactilografiezi (fără caractere româneşti!) - nicidecum nu vei reuşi să înveţi să programezi procedând astfel (punct!).
Mai departe descriem (sau imaginăm) lucrul în laborator, pe două sau trei ore, cu o grupă de elevi...
Pornim calculatoarele şi intrăm fiecare în IDE Borland C++ 3.1; eliminăm cărţile şi caietele. Presupunem că fiecare a înţeles problema pe care ne-am propus să o rezolvăm; o amintim verbal împreună cu "planul de rezolvare". Deschidem fiecare un fişier .CPP şi înscriem întâi un "comentariu", conţinând un enunţ simplificat al problemei; apoi, încercăm să redăm planul nostru de rezolvare - inserând declaraţii preliminare ale datelor şi funcţiilor necesare şi definind apoi cât mai sumar un main() corespunzător:
/* Adună sau scade între ele numerele 1, 2, ..., n încât să rezulte 1. fie A şi B suma numerelor 1..n care se vor aduna, respectiv se vor scădea A + B = suma tuturor 1..n = n*(n+1) / 2 A - B = 1 deci A = ( n*(n+1) + 2 ) / 4 şi A trebuie să fie întreg reformulare: Determină sistemele de numere distincte 1..n care să aibă suma A = (n*(n+1)+2)/4. exemplu: n = 5 => A = 8 => (1, 2, 5), (1, 3, 4), (3, 5) n = 7 => nu există soluţie */ #include <fstream.h> int n, A; int* st; ofstream F("con.txt"); // iniţial, prevedem afişare pe ecran void scrie(int); // n = 5: +1+2-3-4+5 etc. int is_good(int); // este SOLUTIE? este POSIBIL avansul? void solve(int); // backtracking void main() { cin >> n; A = n * (n + 1) + 2; if ( A % 4 ) { F << "Nu exista solutie pe n = " << n << '\n'; exit(0); // necesita stdlib.h } A /= 4; st = new int[n]; solve(0); } void solve(int h) { } int is_good(int h) { } void scrie() { }
Salvăm acest fişier preliminar şi compilăm (prin ALT+F9); constatăm că avem o eroare de compilare: la definiţia funcţiei scrie() - deocamdată "vidă" - am uitat să indicăm parametrul prevăzut în declaraţia iniţială a ei; corectăm:
void scrie(int h) { apoi salvăm fişierul şi recompilăm. Desigur, ne amintim să inserăm şi declaraţia de includere pentru sdtlib.h (pentru funcţia exit()).
Odată încheiată această primă etapă (nu mai avem erori de compilare), trecem să ne ocupăm de fiecare funcţie - dar în aceeaşi manieră "sumară"; de exemplu, rezumăm scrie() doar la valorile din st[] ("1 2 5", nu cum vom dori în final: "+1+2-3-4+5"). Procedăm aşa (scriem rezultatul pe ecran, nu într-un fişier pe disc; etc.) fiindcă scopul imediat trebuie să fie acela de a ne asigura o funcţionare corectă a programului.
Deja am subliniat că
is_good() trebuie să furnizeze unul din 3 răspunsuri posibile, referitor la valorile înscrise în st[]: acestea constituie o soluţie (suma lor este A), respectiv nu constituie încă o soluţie (suma lor este mai mică decât A), respectiv că este imposibil ca ele să conducă la o soluţie (suma lor fiind deja mai mare ca A). O tehnică tipică pentru modelarea unei astfel de situaţii constă în prevederea unor constante "simbolice" corespunzătoare cazurilor respective: în secţiunea de declaraţii din fişierul nostru inserăm:#define SOLUTIE 2 // numerele puse în st[] până la nivelul h au suma A #define POSIBIL 4 // respectiv, au suma < A #define IMPOSIBIL 0 // respectiv, au suma > A
Astfel, funcţia solve() poate fi scrisă astfel:
void solve(int h) { int k; for(k = 1; k <= n; k++) { st[h] = k; int result = is_good(h); if(result == POSIBIL) solve(h + 1); else { if(result == SOLUTIE) scrie(h); } } }
După ce înscriem această funcţie la locul cuvenit, salvăm fişierul, compilăm, corectăm-recompilăm dacă este cazul şi trecem să scriem şi celelalte funcţii:
int is_good(int h) { if(!h) // pe nivelul 0 se poate pune orice 1..n return POSIBIL; if(st[h-1] >= st[h]) // valoarea de pe nivelul h trebuie return IMPOSIBIL; // să fie mai mare decât pe nivelul anterior int s = 0; // suma valorilor puse în st[] până la nivelul h for(int i = 0; i <= h; i++) s += st[i]; if(s == A) return SOLUTIE; if(s < A) return POSIBIL; return IMPOSIBIL; } void scrie(int h) { int i; for(i = 0; i <= h; i++) F << st[i] << ' '; F << '\n'; }
Salvăm fişierul, compilăm, corectăm dacă este cazul. Programul este acum complet şi ar trebui să funcţioneze; prin urmare, lansăm execuţia (CTRL-F9), tastăm 5 (adică n=5) şi ne uităm pe ecran (ALT-F5). Rezultatul pare a fi corect; mai facem eventual câteva teste (între care desigur şi un caz imposibil, ca n = 7). După ce ne convingem astfel că programul funcţionează corect, putem să regândim funcţia de scriere a soluţiei (anume, sub forma: +1+2-3-4+5):
void scrie(int h) { static int* pm = new int[n]; // 'static' asigura ca tabloul pm[] va fi instantiat o singura data int i; for(i = 0; i < n; i++) // reiniţializează pm[] cu 0 ("minus") pm[i] = 0; for(i = 0; i <= h; i++) pm[ st[i] - 1 ] = 1; // înregistrează valorile cu "plus" (1) for(i = 0; i < n; i++) if(pm[i]) F << "+ " << (i+1) << " "; else F << "- " << (i+1) << " "; F << '\n'; }
Declaraţia static asigură că tabloul "local" pm[] va fi instanţiat o singură dată (şi nu la fiecare apelare a funcţiei scrie()); putem verifica aceasta, inserând "cout << pm << '\n';" imediat după declaraţia tabloului - la execuţia programului vom vedea că este scrisă aceeaşi adresă (a tabloului pm[]) la fiecare nouă apelare a funcţiei scrie().
De asemenea, putem să ne gândim şi la un main() mai interesant şi eventual, mai util decât "scurtătura" de care ne-am servit iniţial pentru a pune programul la punct; de exemplu, să găsim soluţiile pentru mai multe valori n:
void main() { for(n = 5; n < 21; n++) { F << "n = " << n << '\n'; A = n * (n + 1) + 2; if ( A % 4 ) { F << "Nu exista solutie pe n = " << n << '\n'; continue; } A /= 4; st = new int[n]; solve(0); } }
iar în acest caz să observăm că nu mai este necesar stdlib.h (fiindcă nu este cazul să mai folosim exit()).
Pentru reproducerea programului în forma finală, putem folosi diverse utilitare source highlight, care marchează cuvintele cheie, declaraţiile, comentariile, etc. dintr-un program-sursă, folosind diverse atribute de culoare şi de font (furnizând un fragment HTML):
/* Adună sau scade între ele numerele 1, 2, ..., n încât să rezulte 1. fie A şi B suma numerelor 1..n care se vor aduna, respectiv se vor scădea A + B = suma tuturor 1..n = n*(n+1) / 2 A - B = 1 deci A = ( n*(n+1) + 2 ) / 4 şi A trebuie să fie întreg reformulare: Să se determine toate sistemele de numere distincte 1..n care să aibă suma A. exemplu: n = 5 => A = 8 => (1, 2, 5), (1, 3, 4), (3, 5) n = 40 => nu există soluţie */ #include <fstream.h> // pentru compilator Borland C++ 3.1 int n, A; int* st; ofstream F("conn.txt", ios::app); #define SOLUTIE 2 // numerele puse în st[] până la nivelul h au suma A #define POSIBIL 4 // respectiv, au suma < A #define IMPOSIBIL 0 // respectiv, au suma > A void scrie(int); // n = 5: +1+2-3-4+5 etc. int is_good(int); // returnează SOLUTIE sau POSIBIL sau IMPOSIBIL void solve(int); // backtracking void main() { for(n = 5; n < 21; n++) { F << "n = " << n << '\n'; A = n * (n + 1) + 2; if ( A % 4 ) { F << "Nu exista solutie pe n = " << n << '\n'; continue; } A /= 4; st = new int[n]; solve(0); } } void solve(int h) { int k; for(k = 1; k <= n; k++) { st[h] = k; int result = is_good(h); if(result == POSIBIL) solve(h + 1); else { if(result == SOLUTIE) scrie(h); } } } int is_good(int h) { if(!h) // pe nivelul 0 se poate pune orice 1..n return POSIBIL; if(st[h-1] >= st[h]) // valoarea de pe nivelul h trebuie return IMPOSIBIL; // să fie mai mare decât pe nivelul anterior int s = 0; // suma valorilor puse în st[] până la nivelul h for(int i = 0; i <= h; i++) s += st[i]; if(s == A) return SOLUTIE; if(s < A) return POSIBIL; return IMPOSIBIL; } void scrie(int h) { static int* pm = new int[n]; int i; for(i = 0; i < n; i++) // reiniţializează pm[] cu 0 ("minus") pm[i] = 0; for(i = 0; i <= h; i++) pm[ st[i] - 1 ] = 1; // înregistrează valorile cu "plus" (1) for(i = 0; i < n; i++) if(pm[i]) F << "+ " << (i+1) << " "; else F << "- "<< (i+1) << " "; F << '\n'; }
În cazul de faţă, am folosit programul GNU source-highlight de la http://www.gnu.org/software/src-highlite/. Revizuind în 2018, am folosit peste tot Pygments.
OBSERVAŢIE (1)
S-a întâmplat ca pe unul dintre calculatoarele din laborator să nu se poată folosi IDE Borland C++ 3.1 decât pentru editarea programului sursă şi pentru compilare (dintr-un motiv sau altul, CTRL-F9 se încheia cu ceva de genul "Link-editor error"). Desigur că putem să ne ocupăm cu depistarea cauzei, să resetăm, etc. - dar de ce numai aşa?
Putem proceda şi astfel: lansăm CMD.EXE (interpretorul de comenzi din Windows), ne poziţionăm în directorul D:\borlandc\BIN şi apelăm compilatorul BCC, transmiţându-i numele fişierului de compilat: d:\borlandc\bin> bcc pm1n.cpp. Cu această sintaxă, BCC va compila programul sursă indicat şi va apela automat şi editorul de legături; fişierul executabil rezultat poate fi lansat direct: d:\borlandc\bin> pm1n.exe după care n-avem decât să deschidem (în Notepad, de exemplu) fişierul conn.txt creat prin execuţia programului, pentru a vedea rezultatele.
OBSERVAŢIE (2)
Ştiţi cam câte compilatoare de C sau C++ au fost create pâna azi? Cam 50 (vezi C_compiler). Există unul care să fie cotat de specialişti drept "cel mai bun"? Se pare că da: compilatorul (mai precis, familia de compilatoare) GCC (GNU_Compiler_Collection), care este inclus drept compilatorul standard pe multe sisteme de operare (între care, Linux) şi care poate fi instalat şi pe Windows folosind cygwin.
Faţă de programul pentru Windows Borland C++ 3.1 redat mai sus, o versiune pentru compilatorul GCC de C++ ar trebui să sufere numai vreo trei modificări:
- #include <fstream> în loc de #include <fstream.h> - declaraţia suplimentară 'using namespace std' - main() returnează un int (în loc de void main())
Standardul ANSI C++ prevede ca extensia ".h" să fie folosită numai pentru fişiere header C (nu C++) - de aici necesitatea primei modificări.
De asemenea, se prevede spaţiul comun de nume
std care conţine informaţiile necesare despre numele existente în fişierele-header incluse (de exemplu, numele cout trebuie referit prin std::cout - şi în loc să se caute în fişierul "fstream" se va căuta direct în spaţiul de memorie "std"); declaraţia using namespace std permite evitarea prefixării cu std:: a numelor respective ("prefixarea" fiind transferată în seama compilatorului).
Prin urmare, porţiunea iniţială a programului va fi acum:
#include <fstream> using namespace std;
iar funcţia main() va trebui scrisă sub forma:
int main() {
// instrucţiuni
return 0;
}
Efectuând cele trei modificări prezentate mai sus, programul sursă rezultat va putea fi compilat şi executat pe un sistem Linux prin următoarele comenzi scrise într-un terminal:
vb@debian:~/lar$ g++ -o pm1ncc pm1n.cpp // obţine executabilul 'pm1ncc' vb@debian:~/lar$ ./pm1ncc // lansează 'pm1ncc', obţinând fişierul 'conn.txt' vb@debian:~/lar$ cat conn.txt // afişează fişierul 'conn.txt'
Pe prima linie s-a apelat compilatorul g++ (pentru C++), care face parte din pachetul GCC.
OBSERVAŢIE (3)
În programul prezentat mai sus ne-a scăpat un aspect de principiu: am alocat memorie pentru tabloul
st[], dar am omis să şi "dealocăm" zona respectivă (folosind delete [] st).
C-ul permite adresarea directă a memoriei (prevăzând de exemplu, lucrul cu "pointeri") lăsându-l pe programator să aloce/dealoce memoria conform necesităţilor (ceea ce şi facilitează scrierea programelor de sistem - inclusiv a sistemelor de operare în întregime - în limbajul C); în schimb, în celelalte limbaje moderne de nivel înalt programatorul este scutit să se mai preocupe de aspectele alocării/dealocării dinamice a memoriei (sarcina fiind preluată aproape total de către compilatorul/interpretorul respectiv).
Nu mai redăm aici "reparaţia" cuvenită programului de mai sus; ni se pare mai interesant să redăm o a treia versiune, de data aceasta în C (nu C++), în care să ţinem seama şi de aspectul semnalat mai înainte (alocare / dealocare).
Versiunea C a programului
Lucrând în C (nu C++) nu mai putem angaja obiecte "fstream" (precum "cout"); va trebui să folosim în loc, fişierul
stdio.h care oferă de exemplu funcţia C printf(). Iar pentru alocarea/dealocarea memoriei trebuie să folosim funcţiile malloc() şi free() din stdlib.h. În plus, în C nu mai dispunem de modificatorul static.
Exceptând rescrierile datorate diferenţelor tocmai semnalate, programul este identic celui de mai sus (şi în fond, n-am făcut decât să-l modificăm pe cel redat mai sus).
/* "pmin1.c" - versiune pentru compilator de C Adună sau scade între ele numerele 1, 2, ..., n încât să rezulte 1. fie A şi B suma numerelor 1..n care se vor aduna, respectiv se vor scădea A + B = suma tuturor 1..n = n*(n+1) / 2 A - B = 1 deci A = ( n*(n+1) + 2 ) / 4 şi A trebuie să fie întreg reformulare: Să se determine toate sistemele de numere distincte 1..n care să aibă suma A. exemplu: n = 5 => A = 8 => (1, 2, 5), (1, 3, 4), (3, 5) n = 40 => nu există soluţie */ #include <stdio.h> #include <stdlib.h> /* pentru malloc(), free() (în C++ aveam new, delete) */ int n, A; int* st = 0, *pm = 0; /* în C++ puteam folosi 'static' (cu 'pm' în scrie()) */ #define SOLUTIE 2 /* numerele puse în st[] până la nivelul h au suma A */ #define POSIBIL 4 /* respectiv, au suma < A */ #define IMPOSIBIL 0 /* respectiv, au suma > A */ void scrie(int); /* n = 5: +1+2-3-4+5 etc. */ int is_good(int); /* returnează SOLUTIE sau POSIBIL sau IMPOSIBIL */ void solve(int); /* backtracking */ int main() { for(n = 5; n < 10; n++) { printf("N = %u\n", n); A = n * (n + 1) + 2; if ( A % 4 ) { printf("Nu exista solutie pe N = %u\n", n); continue; } A /= 4; if(st) { /* eliberează memoria alocată anterior */ free(st); /* în C++ puteam folosi: delete[] st; */ free(pm); } st = (int*) malloc(n * sizeof(int)); /* la c++: st = new int[n]; */ pm = (int*) malloc(n * sizeof(int)); /* rezervă în "heap" n int */ solve(0); } return 0; } void solve(int h) { int k; for(k = 1; k <= n; k++) { st[h] = k; int result = is_good(h); if(result == POSIBIL) solve(h + 1); else { if(result == SOLUTIE) scrie(h); } } } int is_good(int h) { int i; if(!h) /* pe nivelul 0 se poate pune orice 1..n */ return POSIBIL; if(st[h-1] >= st[h]) /* valoarea de pe nivelul h trebuie */ return IMPOSIBIL; /* să fie mai mare decât pe nivelul anterior */ int s = 0; /* suma valorilor puse în st[] până la nivelul h */ for(i = 0; i <= h; i++) s += st[i]; if(s == A) return SOLUTIE; if(s < A) return POSIBIL; return IMPOSIBIL; } void scrie(int h) { int i; for(i = 0; i < n; i++) /* reiniţializează pm[] cu 0 ("minus") */ pm[i] = 0; for(i = 0; i <= h; i++) pm[ st[i] - 1 ] = 1; /* înregistrează valorile cu "plus" (1) */ for(i = 0; i < n; i++) if(pm[i]) printf( " + %u", (i+1) ); else printf( " - %u", (i+1) ); printf("%c", '\n'); }
Apelând dintr-un terminal compilatorul gcc şi apoi lansând executabilul:
vb@debian:~/lar$ gcc -o pm1n pm1n.c vb@debian:~/lar$ ./pm1n
vom obţine rezultatele pe dispozitivul standard de ieşire (ecranul). Lansând executabilul respectiv, dar acum cu redirectarea scrierii către un fişier:
vb@debian:~/lar$ ./pm1n > rezultate.txt
se obţine fişierul pe disc "rezultate.txt" care poate fi vizualizat folosind comanda
cat rezultate.txt.
Sub Windows se poate folosi analog, compilatorul BCC (din linia de comandă):
C:\borlandc\bin\bcc pmin1.c C:\borlandc\bin\pmin1.exe C:\borlandc\bin\pmin1.exe > rezult.txt
Să observăm că de data aceasta avem un program care poate rula fără nici o adaptare suplimentară şi sub GCC şi sub BCC; dar desigur, "poate rula" se referă la programul sursă (care trebuie compilat pe Linux cu GCC şi respectiv pe Windows cu BCC) şi nu la executabil (în mod normal, executabilul produs de BCC sub Windows nu va putea fi executat ca atare pe Linux - şi invers)
https://www.youtube.com/watch?v=IHNWxxYio6o pentru copii
https://www.youtube.com/watch?v=IHNWxxYio6o pentru copii
No comments:
Post a Comment