Laborator 2
Problema 1
Se da un fisier continand date despre optiunile unor studenti cu privire la un set de materii optionale. Acest fisier poate fi vizualizat aici. Fisierul contine 10.000 de linii, fiecarui elev revenindu-i 2 linii consecutive din fisier. Pe prima linie din cele doua se afla numele studentului iar pe cea de a doua se afla o serie de 4 coduri reprezentand tot atatea optiuni. Cunoscand ca sunt in total 5.000 de studenti si ca numele nici unui student nu ocupa mai mult de 35 de caractere, se cere:
· Sa se citeasca datele din fisier intr-un tablou de 5.000 de elemente de forma < nume , optional1, optional2, optional3, optional4 >
· Stiind ca studentii sunt ordonati alfabetic dupa nume, sa se aplice un algoritm de cautare optim, din cele studiate in cadrul acestui laborator si sa se contorizeze numarul de comparatii pentru gasirea studentului MATEI STEFAN.
· Sa se aplice algoritmul de cautare liniara pentru localizarea tuturor studentilor care au ales un anumit optional, dat de la tastatura si sa se afiseze numele acestora
Problema 2
Se da un fisier continand date despre optiunile unor studenti cu privire la un set de materii optionale. Acest fisier poate fi vizualizat aici. Fisierul contine 10.000 de linii, fiecarui elev revenindu-i 2 linii consecutive din fisier. Pe prima linie din cele doua se afla numele studentului iar pe cea de a doua se afla o serie de 4 coduri reprezentand tot atatea optiuni. Cunoscand ca sunt in total 5.000 de studenti si ca numele nici unui student nu ocupa mai mult de 35 de caractere, se cere:
· Sa se citeasca datele din fisier intr-un tablou de 5.000 de elemente de forma < nume , optional1, optional2, optional3, optional4 >
· Stiind ca studentii sunt ordonati alfabetic dupa nume, sa se aplice algoritmul de cautare binara performanta pentru cautarea studentului PARASCHIV ION si sa se contorizeze comparatiile care se fac pentru localizare.
· Sa se aplice un algoritm de cautare pentru localizarea tuturor studentilor care au ales un anumit optional, sa se afiseze numele acestora si sa se afiseze numarul comparatiilor facut pentru localizarea primului student cu aceasta optiune.
Problema 3
Se da un fisier continand date despre rezultatele unor elevi la admiterea in liceu. Acest fisier poate fi descarcat aici. Fisierul contine 10.000 de linii, fiecarui elev revenindu-i 2 linii consecutive din fisier. Pe prima linie din celedoua se afla numele elevului iar pe cea de a doua se afla media de intrare sub forma unui numar real intre 1.0 si 10.0. Cunoscand ca sunt in total 5.000 de elevi si ca numele nici unui elev nu ocupa mai mult de 35 de caractere, se cere:
Sa se citeasca datele din fisier intr-un tablou de 5.000 de elemente de forma < nume , medie >
Stiind ca elevii sunt ordonati descrescator dupa medie, sa se aplice algoritmul de cautare binara pentru a localiza elevul care a obtinut media 9.7 si sa se contorizeze comparatiile care se fac pentru localizare
Sa se aplice algoritmul de cautare prin interpolare pentru a localiza elevul care a obtinut media 9.7 si sa se contorizeze comparatiile care se fac pentru localizare
Rezolvare Problema 1&2
#include <stdio.h>
#include <stdlib.h>
char NumeStudent[]="MATEI STEFAN",mesaj[]="Studentul nu se afla in lista";
struct student
{
char nume[36];
char op1[3];
char op2[3];
char op3[3];
char op4[3];
}s[5000];
void citire()
{
FILE *f;
f=fopen("studenti.txt","r");
if(f==NULL)
{
printf("Eroare la deschiderea fisierului de intrare");
exit(1);
}
int i;
for(i=0;i<5000;i++)
{
fgets(s[i].nume,35,f);
strtok(s[i].nume,"\n");
fscanf(f,"%s %s %s %s\n",&s[i].op1,&s[i].op2,&s[i].op3,&s[i].op4);
}
fclose(f);
}
void CautareBinara()
{
int st=0,dr=4999,m,gasit=0,nrcmp=0;
while((st<=dr)&&(!gasit))
{
m=(st+dr)/2;
if(strcmp(s[m].nume,NumeStudent)==0)
gasit=1;
else
{
nrcmp++;
if(strcmp(s[m].nume,NumeStudent)<0)
st=m+1;
else
dr=m-1;
}
}
if(gasit)
printf("Cautarea binara: %d %s\nNumar comparatii: %d\n\n",m,s[m].nume,nrcmp);
else
printf("Cautarea binara\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
}
void BinarPerformant()
{
int st=0,dr=5000,nrcmp=0,m;
while(st<dr)
{
m=(st+dr)/2;
if(strcmp(s[m].nume,NumeStudent)<0)
st=m+1;
else
dr=m;
nrcmp++;
}
if(dr>=5000)
printf(mesaj);
else
if(strcmp(s[dr].nume,NumeStudent)==0)
printf("Cautarea binara performanta: %d %s \nNumar comparatii: %d\n\n",dr,s[dr].nume,nrcmp);
else
printf("Cautarea binara performanta\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
}
void CautareLiniara(char opt[3])
{
int i=0,gasit=0;
FILE *g;
g=fopen("optionale.txt","w");
if(g==NULL)
{
printf("Eroare la deschiderea fisierului de iesire");
exit(1);
}
fprintf(g,"Studenti cu optionalul %s:\n",opt);
while(i<5000)
{
if(strcmp(s[i].op1,opt)==0 || strcmp(s[i].op2,opt)==0 || strcmp(s[i].op3,opt)==0 || strcmp(s[i].op1,opt)==0 )
{
fprintf(g,"%d %s\n",i,s[i].nume);
gasit=1;
}
i++;
if(!gasit&&i==5000)
fprintf(g,"Nu exista studenti cu optionalul cerut");
}
fclose(g);
}
int main()
{
printf("Hello world!\n");
citire();
CautareBinara();
BinarPerformant();
char optional[3];
printf("Numele optionalului cautat: ");
scanf("%s",&optional);
CautareLiniara(optional);
return 0;
}
Rezolvare Problema 3
#include <stdio.h>
#include <stdlib.h>
char mesaj[]="Nu exista niciun student cu media ceruta";
struct student
{
char nume[36];
float media;
}s[5000];
void citire()
{
FILE *f;
f=fopen("studenti_A3.txt","r");
if(f==NULL)
{
printf("Eroare la deschiderea fisierului de intrare");
exit(1);
}
int i;
for(i=0;i<5000;i++)
{
fgets(s[i].nume,35,f);
strtok(s[i].nume,"\n");
fscanf(f,"%f ",&s[i].media);
}
fclose(f);
}
void CautareBinara(float nota)
{
int st=0,dr=4999,m,gasit=0,nrcmp=0;
while((st<=dr)&&(!gasit))
{
m=(st+dr)/2;
if(s[m].media==nota)
gasit=1;
else
{
nrcmp++;
if(s[m].media>nota)
st=m+1;
else
dr=m-1;
}
}
if(gasit)
printf("Cautarea binara: %d %s\nNumar comparatii: %d\n\n",m,s[m].nume,nrcmp);
else
printf("Cautarea binara\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
}
void BinarPerformant(float nota)
{
int st=0,dr=5000,nrcmp=0,m;
while(st<dr)
{
m=(st+dr)/2;
if(s[m].media>nota)
st=m+1;
else
dr=m;
nrcmp++;
}
if(dr>=5000)
printf("Cautarea binara performanta\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
else
if(s[m].media==nota)
printf("Cautarea binara performanta: %d %s \nNumar comparatii: %d\n\n",dr,s[dr].nume,nrcmp);
else
printf("Cautarea binara performanta\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
}
void Interpolare(float nota)
{
int m,st=0,dr=4999,nrcmp=0;
do{
m=st+((nota-s[st].media)*(dr-st))/(s[dr].media-s[st].media);
if(nota<s[m].media)
st=m+1;
else
dr=m-1;
nrcmp++;
}while((st<dr)&&(s[m].media!=nota)&&(s[dr].media!=s[st].media)&&(nota>=s[st].media)&&(nota<=s[dr].media));
if((s[m].media==nota)&&(m<5000))
printf("Cautarea prin interpolare: %d %s \nNumar comparatii: %d\n\n",m,s[m].nume,nrcmp);
else
printf("Cautarea prin interpolare\n%s\nNumar comparatii: %d\n\n",mesaj,nrcmp);
}
void Liniara(float media)
{
printf("Cautarea liniara: ");
int i,gasit=0;
for(i=0;i<5000;i++)
if(media==s[i].media)
{ gasit=1;
printf("%d %s %f\n",i,s[i].nume,s[i].media);
}
if(!gasit)
printf("%s",mesaj);
}
/*void Cautare_componenta_marcaj(int x)
{
int i=0;
a[n]=x;
while(a[i]!=x)
i++;
if(i==N)
printf("Nu exista elementul cautat");
else
printf("Elementul a fost gasit pe pozitia %d",i);
}
void Cautare_Liniara(int x)
{
int i=0;
while((i<n-1)&&(a[i]!=x))
i++;
if (a[i]!=x )
printf("Elementul cautat nu exista");
else
printf("Elementul cautat se afla pe pozita %d",i);
}
*/
int main()
{
printf("Hello world!\n");
float media;
printf("Media pe care o vreti sa o cautati: ");
scanf("%f",&media);
citire();
CautareBinara(media);
BinarPerformant(media);
Interpolare(media);
Liniara(media);
return 0;
}