SDA Lucrarea 1

După acest laborator veți putea folosi IDE-ul Netbeans pentru a scrie și depana programe în C. Totodată veți relua și recapitula noțiunile legate de pointeri în C.

Utilizarea IDE-ului CLion

CLion este un mediu integrat de dezvoltare (IDE) care permite dezvoltarea de programe în limbajele C și C++. CLion nu instalează și compilator pentru C/C++, acesta trebuie instalat manual, în prealabil.

Atenție: Imaginea de Linux folosită la Programarea Calculatoarelor are deja instalat compilatorul de C.

Instalarea GCC

Instalarea GCC în Linux

Pentru instalarea compilatorului de C (GCC) în distribuțiile de Linux provenite din Ubuntu (Ubuntu, Kubuntu, Xubuntu, Mint, LMDE, etc.) se poate folosi comanda:

apt-get install -y build-essential

Instalarea GCC în Windows

Pentru compilarea de programe cu GCC în Windows, aveți nevoie de instalarea acestui compilator care poate fi făcută prin instalarea unuia din următoarele două suite de programe:

• Cygwin - Tutorial de instalare aici.
• MinGW - Tutorial de instalare aici.

Atenție: Nu uitați ca la instalare să bifați în lista de pachete și compilatorul de C (gcc), make și git.

Instalarea CLion

De la adresa https://www.jetbrains.com/clion/download/#section=linux puteți descărca kitul de instalare pentru sistemul vostru de operare. După instalare, urmaţi următorii paşi de configurare, în funcţie de suita de programe aleasă:

• Configurare CLion cu Cygwin
• Configurare CLion cu MinGW

Realizarea unui proiect

Odată pornit, CLion oferă posibilitatea de a deschide un proiect existent, sau de a crea unul nou. Vrem să realizăm un proiect nou, aşadar se va alege New Project.

Observație: Se poate realiza un nou proiect atunci când altul este deja deschis folosind meniul File - New Project .

Mai departe se va selecta categoria C++ Executable şi se va introduce locaţia proiectului.

Atenție: În imagine se observă că locaţia introdusă este /home/student/projects/NewProject. Se recomandă ca directorul în care se realizează proiectul să aibă numele proiectului, sau un nume sugestiv (în imagine NewProject)

Componentele IDE-ului CLion

La crearea unui nou proiect, IDE-ul CLion generează automat fişierul main.cpp. Acesta conţine un exemplu program ce va fi rescris de către utilizator.

Secţiunile marcate în imagine reprezintă:

1. Zona verde - Project view indică toate fişierele şi directoarele ce alcătuiesc proiectul.
2. Zona albastră - Editor este fereastra de vizualizare şi editare a textului
3. Zona roşie - Toolbar oferă acces rapid pentru operaţiile uzuale. Dintre acestea, cel mai des vom folosi:
   • Build
   • Run
   • Debug
4. Zona galbenă - Run este zona în care se introduc datele de intrare şi se în care vor fi afişate datele de ieşire.

Exemplu de program în modul debug

Copiați codul de mai jos înlocuind programul deja existent în fișierul main.c:

 1#include <stdio.h>
 2
 3int main(){
 4    printf("Debugging program...\n");
 5    int value = 0;
 6    value = value + 1;
 7    value++;
 8    value = value * 2;
 9    value -= 1;
10    printf("Value is now %d!\n", value);
11    return 0;
12}

Pentru a executa programul în modul debug trebuie sa introducem cel puţin un breakpoint. Astfel indicăm programului unde se va opri pentru a ne acorda control asupra execuţiei, având posibilitatea de a continua execuţia pas cu pas.

Introducem un nou breakpoint dând click în dreptul liniei de la care vrem să obţinem controlul. În cazul nostru, vom alege să indroducem un breakpoint chiar la definirea variabilei value.

Atenție: Când alegem locaţia unui breakpoint trebuie să ţinem cont de următorul aspect: în modul debug programul se va opri înainte de a executa linia în dreptul căreia a fost introdus breakpoint-ul!

În continuare, trebuie se pornim execuţia programului in modul debug . Observăm apariţia ferestrei Debug (chenarul albastru, Imaginea 5) ce conţine următoarele:

1. Zona galbenă - fereastra cu toate variabilele declarate, împreună cu valorile lor. Momentan nu există nicio variabilă declarată (deoarece linia asupra la care ne-am oprit nu a fost încă executată!)
2. Zona roşie - Permite trecerea între fereastra pentru procesul de depanare (Debugger) şi fereastra în care se afişează/introduc datele (Console)
3. Zona verde - Conţine comenzile pentru controlul execuţiei în modul debug (comenzi numite stepping actions):
   • Step over - Execută comenzile de pe linia curentă şi trece la următoarea linie
   • Step into - Programul va executa linia curentă iar dacă pe linia curentă există un apel de funcție, se va opri pe prima linie din funcția respectivă. Această comandă este utilă atunci cand pe linia curentă se află un apel de funcţie şi vrem sa studiem comportamentul codului din interiorul funcţiei.
   • Step out - Termină de executat funcţia în care se află linia curentă
   • Run to cursor - Execută toate instructiunile până se intâlneste cursorul.

Observație: În modul debug, linia curentă este marcată de către mediul de dezvoltare prin colorarea acesteia cu albastru.

Alte comenzi utile:

• Resume program - Continuă execuţia pâmă la următorul breakpoint (dacă nu există, se va executa până la final)
• Stop - Se opreşte definitv execuţia programului, împreună cu modul debug

Pentru a exersa utilizarea sistemului de debug, realizați următoarele operații:

1. Parcurgeti tot programul folosind Step Over și vizualizând valoarea variabilei value la fiecare pas, până la ultima linie din program, unde utilizați Resume program.
2. Reporniți aplicația în modul de debug și puneți un al doilea breakpoint pe linia cu apelul funcției printf.
3. Folosiți Resume program pentru a ajunge la al doilea breakpoint.
4. Odată ajunși acolo, folosiți Step In pentru a intra în funcția printf (neavând codul sursă, veți vedea codul de asamblare obținut din dezasamblarea fișierului obiect de către GDB).
5. Folosiți Step Out pentru a reveni în funcția main și apoi Resume program pentru a termina execuția.

Tips & Tricks

Formatare automată a codului

CLion oferă opțiunea de a formata automat codul prin selectarea Code -> Reformat Code.

Ce probleme rezolvă această formatare automată:

• alinierea liniilor în funcție de blocurile de instrucțiuni și tipurile de statements de pe fiecare linie;
• plasarea sau eliminarea de spații acolo unde este necasar.

Ce probleme NU rezolvă această formatare automată;

• lipsa acoladelor de la blocurile if și for;
• numele insuficient de sugestive pentru numele de funcții, structuri sau variabile.

Stilul conform căruia este modificat codul poate fi configurat folosind meniul File|Settings|Editor|CodeStyle

Generare automată a codului

CLion oferă posibilitatea de a genera fragmente de cod des înâlnite, precum constructori şi operatori în interiorul claselor. Această acţiune poate fi realizată folosind meniul Code|Generate.

Altele

• TODO Comments

Nu uitați de regulile următoare: Convenții de cod - C

Exemplu

Impreună cu echipa de la firmă ați inventat un nou algoritm de generare de numere pseudo-aleatoare. Pentru a valida că generatorul poate fi folosit în algoritmi criptografici (cryptographically secure) trebuie să implementați și să rulați o baterie de teste. Unul din aceste teste verifică numărul de apariții pentru fiecare secvență posibilă de doi biți: 00, 01, 10 și 11 cât și raportul între numărul de biți de 0 și de 1. Pentru ca secvența de biți să fie aleatoare, trebuie ca numărul de apariții pentru fiecare din cele patru perechi să fie aproximativ egale și în același timp numărul de biți de 0 să fie aproximativ egal cu cei de 1. Mai precis, trebuie ca raporturile R1 dintre numărul de apariții a perechii care apare de cele mai multe ori și numărul de apariții a perechii care apare de cele mai puține ori, cât și raportul R2 între numărul de apariții ale celui mai frecvent bit și numărul de apariții ale celui mai puțin frecvent bit să fie mai mici sau egale cu 110%.

Cerință

Dându-se un număr n reprezentând numărul de biți generat de RNG și secvența de n biți, să se calculeze raporturile R1 și R2 și să se decidă dacă generatorul este valid sau nu.

Date de intrare

Pe prima linie se află n, numărul de biți generați. Pe a doua linie se află o secvență continuă de n biți (valori de 0 sau 1), ne-separați prin spații.

Date de ieșire

Programul va afișa în consolă (pe stream-ul stdout) pe prima linie raporturile R1 și R2 calculate conform descrierii, valori fracționare cu două zecimale, separate prin spațiu, iar pe a doua linie valoarea 1 dacă generatorul este valid sau 0 dacă nu este.

Restricții

1. 2 ≤ n ≤ 10000, n este par

Intrare:

18

101100110111100001

Iesire:

1.50 1.25

0

Secvența are 18 biți și extragând secvențele de câte doi biți se observă că 00 apare de două ori, 01 apare de două ori, 10 apare de două ori și 11 apare de trei ori. Calculând raportul dintre maxim și minim (3/2) obținem 150%. Numărul de biți 1 este 10 și numărul de biți 0 este 8. Raportul este 10/8 = 125%. Pentru că cel puțin unul din raporturi este mai mare strict decât 110%, se afișează pe a doua linie 0 (secvența nu este aleatoare).

Input:

24

101100110111100001010010

Output:

1.00 1.00

1

În acest exemplu toate perechile apar de trei ori, deci raportul R1 este 100%. Numărul de biți 1 este 12 și este egal cu numărul de biți 0, deci și raportul R2 este 100%. Astfel, pentru că ambele raporturi sunt mai mici sau egale decât 110%, pe a doua linie se afișează 1 (secvența este aleatoare).

Problema 1 (saptamana 2)

Pentru a deveni competitivă în domeniul Blockchain și a monedelor virtuale, firma la care lucrați a dezvoltat un algoritm de hashing inovativ pentru valori numerice. Algoritmul funcționează în modul următor: asupra unui număr natural se face următoarea transformare: dacă numărul are cel puțin două cifre, se iau pe rând din număr câte două cifre vecine și se scade cea mai mică din cea mai mare. Cu cifrele astfel obținute se formează un nou număr. De exemplu, pentru numărul 5734, din cifrele 5 și 7 se obține 2, din 7 și 3 se obține 4 iar din 3 și 4 se obține 1. Formăm deci un nou număr 241, căruia i se poate aplica aceeași transformare, obținându-se 23. Din 23, prin același procedeu, obținem 1. Dacă numărul este format dintr-o singură cifră, transformarea îl lasă nemodificat. Hash-ul se calculează realizând succesiv transformarea asupra numărului original și apoi asupra rezultatului obținut, de k ori, și sumând toate rezultatele parțiale și rezultatul final (excluzând valoarea de start).

Cerință

Se dau două numere naturale N şi k și apoi încă N numere naturale. Se cere să se determine valoarea maximă a hash-ului care se va obține aplicând algoritmul de hash celor N numere folosind k pentru numărul de iterații de transformare, conform descrierii de mai sus.

Date de intrare

La intrarea programului se prezintă pe prima linie două numere naturale N și k, separate prin spațiu. Pe a doua linie se află cele N numere, separate tot prin spații. Liniile de intrare se încheie cu caracterul newline (\n), obținut prin apăsarea tastei Enter.

Date de ieșire

Programul va afișa la consolă (pe stream-ul stdout) un singur număr, reprezentând valoarea maximă dintre toate hash-urile obținute conform procedeului descris anterior.

Restricții

1. 0 < N < 10000 2. 0 ≤ ni < 100000000 (valorile asupra cărora se va aplica hash-ul). 3. 0 < k < 100

Exemple:

Intrare:

2 2 5734 1234

Ieșire:

264

Explicații: Se aplică de 2 ori succesiunea de transformări pentru fiecare din cele două valori. Astfel, din 5734 se obține 241, iar din 241 se obține 23. Adunând numerele 241 și 23 se obține rezultatul: 264. Din 1234 se obține 111 iar din 111 se obține 0. Sumând cele două valori rezultatul este 111. Valoarea maximă este 264.

Intrare:

2 3 2228 6

Iesire:

18

Se aplică transformările de 3 ori asupra celor două numere. Pentru 2228, în urma primei transformări se obțin cifrele 0, 0, 6, din care formăm secvența 006, adică numărul 6. La următoarele 2 transformări rezultă aceeași valoare, 6. Prin urmare suma obținută este: 6+6+6 = 18. Pentru valoarea 6, cele 3 transformări vor produce tot 6 iar suma va fi tot 18. Rezultatul este deci 18.

Problema 2(saptamana 2)

Doamna secretară trebuie să stabilească numărul de studenți ce vor lua bursă de merit în anul universitar următor și să identifice studentul care va lua bursa de performanță (există o singură bursă de performanță). Are la dispoziție lista tuturor studenților și notele obținute de aceștia la diversele discipline. Bursa de performanță se acordă studentului integralist cu media cea mai mare. Bursele de merit se acordă în ordinea descrescătoare a mediilor, în limita numărului maxim de burse, tuturor studenților integraliști care au media generală peste 8.00.

Cerinţă

Stabiliți ce student va lua bursă de performanță și câți studenți vor lua bursă de merit în anul universitar următor.

Date de intrare

Se vor citi de la tastatură (fluxul stdin) următoarele date:

• Trei numere întregi pozitive m, n, p separate prin spaţiu, reprezentând

• m – numărul de studenţi,

• n – numărul de discipline,

• p – numărul de burse de merit disponibile;

• 2*m linii de pe care se citesc, în ordine, în formatul:

• <NS>, un şir de caractere reprezentând numele studentului;

• <N1> <N2> ... <Nn>, n numere întregi din intervalul 1 – 10 separate prin spaţiu reprezentând notele obţinute de respectivul student la cele n discipline;

Toate liniile conţinând date de intrare sunt finalizate cu caracterul newline (tasta Enter).

Date de ieşire

Programul va afișa pe ecran (stream-ul standard de ieșire):

Pe prima linie: numărul de studenți ce vor lua bursă de merit Pe a doua linie: numele studentului care va lua bursă de performanță și media media lui (număr fracționar cu 2 zecimale) separate prin spațiu. Restricţii şi precizări

1. 0 < m, n, p < 100

Garantăm că nu vor exista studenți cu medii egale.

Intrare:

6 3 2 George Popescu 9 9 9 Dan Pop 10 4 10 Ionela Cristescu 6 8 8 Ilie David 10 10 10 Georgiana Fus 9 10 10 Cristian Oprescu 8 9 9

Ieşire:

2 Ilie David 10.00

Explicaţie:

Ilie David este studentul integralist cu cea mai mare medie, deci va primi bursa de performanță.

Dan Pop nu poate primi bursă pentru că nu este integralist.

Ionela Cristescu nu poate primi bursă pentru că are media sub 8.

Georgiana Fus, George Popescu și Cristian Oprescu îndeplinesc condițiile de a primi bursă, însă doar doi dintre ei vor fi bursieri pentru că numărul maxim de burse de merit este 2.

Intrare:

6 3 5 George Popescu 9 9 9 Dan Pop 10 4 10 Ionela Cristescu 6 8 8 Ilie David 10 10 10 Georgiana Fus 9 10 10 Cristian Oprescu 8 9 9

Ieşire:

3 Ilie David 10.00

Explicaţie:

Ilie David este studentul integralist cu cea mai mare medie, deci va primi bursa de performanță.

Dan Pop nu poate primi bursă pentru că nu este integralist.

Ionela Cristescu nu poate primi bursă pentru că are media sub 8.

Georgiana Fus, George Popescu și Cristian Oprescu vor primi cu toții bursă de merit pentru că îndeplinesc condițiile, iar numărul maxim de burse de merit este 5.

Probleme propuse

Problemele de mai jos au anumite erori care trebuie gasite si raparate folosind debugger-ul.

Problema 1

Programul de mai jos ar trebui să citească de la tastatură un șir de maxim 1024 caractere și să afișeze câte litere mici, câte litere mari și câte cifre conține acest șir. Totuși acest program are o eroare. Folosiți debugger-ul pentru a o identifica și repara.

Exemplu de intrare:

Ana a plecat la piata si a cumparat 10 saci de cartofi.

Ieșirea pentru intrarea de mai sus:

40 1 2

#include <stdio.h>

int main() {
    char c;
    unsigned uppercaseChars = 0;
    unsigned lowecaseChars = 0;    
    unsigned digits = 0;
    
    while(scanf("%c", c) != EOF) {
        if(c > 'a' || c < 'z') {
            lowecaseChars++;
        } else if(c > 'A' && c < 'Z') {
            uppercaseChars++;
        } else {
            digits++;
        }
    }
    printf("%u %u %u", lowecaseChars, uppercaseChars, digits);
    return 0;
}

Problema 2

Un tehnician a măsurat un număr mare n de rezistori şi a obţinut n valori de rezistenţe. Tehnicianul ştie că rezistorii sunt de acelaşi fel, dar pentru că sunt vechi şi codul culorilor nu mai este vizibil, doreşte să calculeze valoarea nominală a rezistenţei (R) şi dispersia valorilor, (S). Apoi, având aceste valori, el vrea să determine câte din rezistenţele testate (procentual) se încadrează în intervalul [R – S; R + S]. Rezistenţa nominală se calculează ca media aritmetică a valorilor rezistenţelor, iar formula dispersiei este dată mai jos.

Cerinţă Dându-se un număr n de rezistori şi valorile rezistenţelor acestora Ri (i = 1, ..., n), să se determine procentul rezistoarelor care au rezistenţa în intervalul [R– S; R + S].

Date de intrare Pe prima linie se află numărul întreg n. Pe următoarea linie, separate printr-un spaţiu, sunt n valori fracţionare de rezistenţe (în ohmi).

Date de ieşire Se va afişa o singură valoare fracţionară, cu exact două zecimale reprezentând procentul de rezistori cu rezistenţa în intervalul [R – S; R + S].

Restricţii şi precizări:

1 < n < 1000

1.0 <= Ri <= 10000.0

S=sqrt( pow(sum(R[i]−R),2) / n )

Exemplu:

Input = 10

76 1 20 37 19 92 61 96 37 77

Output = 50.00

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <cstdio>


int main() {
    int n;
    double values[n];
    scanf("%d", &n);
    int sum = 0;
    for(int i = 0; i < n; i++){
        scanf("%lf", &values[i]);
        sum += values[i];
    }
    double average = sum / n;
    double dispersion = 0;
    for(int i = 0; i < n; i++){
        dispersion += (values[i] - average) * (values[i] - average);
    }
    dispersion = sqrt(dispersion / n);
    int larger = 0;
    for(int i = 0; i < n; i++) {
        if(values[i] >= average - dispersion 
                && values[i] <= average + dispersion) larger++;
    }
    printf("%.2lf", 100 * larger / n);
    return 0;
}

Problema 3

Sunteți angajați de ministerul învățamântului să scrieți un program care să listeze toți elevii care au promovat examenul de bacalaureat. De la tastatură se introduce un număr n reprezentând numărul de candidați, apoi pe următoarele n linii, un nume de elev (format din exact două cuvinte: nume și prenume) și notele la cele patru materii, format fracționar, valori între 1 și 10. Să se afișeze toți studenții care au promovat examenul de bacalaureat (media mai mare ca 6, fiecare notă mai mare ca 5) în ordinea inversă a introducerii lor, împreună cu media de promovare, afișată cu fix două zecimale.

Exemplu de date de intrare:

4

Gheorghe Ghita 8 7 5.5 10

Vuia Vasile 4 10 10 10

Andreescu Andra 9 10 9 10

Elenescu Elena 5 5 5 5

Ieșirea pentru intrarea de mai sus:

Andreescu Andra 9.50

Gheorghe Ghita 7.63

#include <stdio.h>
struct studenti{
char n[128];
char m[128];
float a,b,c,d;
};
int main(){
int n,i;
struct studenti s[n];
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%s%s%f%f%f%f",&s[i].n,&s[i].m,&s[i].a,&s[i].b,&s[i].c,&s[i].d);

for(i=n;i>0;i--){
float m=(s[i].a+s[i].b+s[i].c+s[i].d)/4;
if(s[i].a>5&&s[i].b>5&&s[i].c>5&&s[i].d>5||m>=6){
printf("%s %s %.2f\n",s[i].n,s[i].m,m);
}
}
return 0;
}