c++

/*Problema 17 - Metoda 1

Se da un graf neorientat cu n noduri.  Numarul de noduri si muchiile grafului se citesc din fisierul "graf.txt".

Sa se verifice daca graful este complet si sa se afiseze un mesaj adecvat.

Daca graful nu este complet si se afiseaza muchiile care ar trebui adaugate astfel  оncвt  graful sa devina complet.

Exemplu: Daca fisierul "graf.txt" are urmatorul continut:

5

1 3

1 4

1 5

2 4

3 5

Se va afisa mesajul "Graful nu este complet" dupa care se vor afisa muchiile lipsa:

1 2

2 3

2 5

3 4

4 5

*/

#include<iostream.h>

#include<fstream.h>

ifstream f("graf.txt");

int n,m,i,j,a[10][10];//m nr de muchii

void citeste()

{

//citesc numarul de noduri n

f>>n;

//initializez matricea de adiacenta cu 0

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               a[i][j]=0;

//citesc muchiile din fisierul de intrare graf.txt

while(!f.eof())

{

int m=0;//numar cate muchii are graful

f>>i>>j;//citesc muchia

a[i][j]=a[j][i]=1;

if(a[i][j]==1)

                m++;

//completez matricea de adiacenta cu valori de 1 acolo unde exista muchii

}

}

void matrice_adiacenta()

{

int i,j;

cout<<"Matricea de adiacenta este:"<<endl;

for(i=1;i<=n;i++)

{

                for(j=1;j<=n;j++)

                               cout<<a[i][j]<<" ";

cout<<endl;

}

cout<<endl;

}

//Un graf este complet daca numarul de muchii este egal cu n*(n-1)/2

void graf_complet()

{

if(m==n*(n-1)/2)

                cout<<"Graful este complet";

else

                cout<<"Graful nu este complet";

cout<<endl;

}

void muchii_lipsa()

{

//parcurg matricea de adiacenta de deasupra diagonalei principale

cout<<"Muchiile care lipsesc pentru ca graful sa devina complet sunt: "<<endl;

for(i=1;i<=n-1;i++)

                for(j=i+1;j<=n;j++)

                               if(a[i][j]==0)

                                               cout<<i<<" "<<j<<endl;

               

}

int main()

{

citeste();

matrice_adiacenta();

graf_complet();

muchii_lipsa();

return 0;

f.close();

}

/*Problema 18

Se da un graf neorientat cu n noduri.  Numarul de noduri si muchiile grafului se citesc din fisierul „graf.txt”.

Sa se verifice daca graful este regulat. In situatia in care graful nu este regulat sa se afiseze nodurile terminale

si numarul de noduri izolate. (Un graf neorientat se numeste regulat daca toate nodurile sale au acelasi grad).

Exemplu: Daca fisierul „graf.txt” are urmatorul continut:

5

1 3

1 5

2 4

3 5

Se va afisa mesajul “Graful nu este regulat” dupa care se vor afisa nodurile terminale: 2, 4 si numarul de noduri izolate: 0 */

#include<iostream.h>

#include<fstream.h>

ifstream f("graf.txt");

int n,a[10][10];

void citeste()

{

int i,j;

f>>n;//citesc numarul de noduri din fisier

//initializez matricea de adiacenta cu 0

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               a[i][j]=0;

//citesc muchiile din fisier

while(!f.eof())//cat timp nu s-a ajuns la sfarsitul fisierului

{

f>>i>>j;

a[i][j]=a[j][i]=1;

}

f.close();

}

void afisare_matrice_adiacenta()

{

int i,j;

for(i=1;i<=n;i++)

{

                for(j=1;j<=n;j++)

                                cout<<a[i][j]<<" ";

cout<<endl;

}

cout<<endl;

}

//determin gradul unui nod x

int grad(int x)

{

int i,gr=0;

                for(i=1;i<=n;i++)

                if(a[i][x]==1)

                               gr++;

return gr;

}

//verific daca graful este regulat

//Un graf neorientat se numeste regulat daca toate nodurile sale au acelasi grad

int regulat()

{

int i,g,ok=1;//pp ca graful e regulat

g=grad(1);//determin gradul primului nod in vederea compararii cu celelalte

//daca toate sunt egale cu gradul primului nod atunci graful este regulat

for(i=1;i<=n;i++)

                if(g!=grad(i))

                               ok=0;//noduri cu grade diferite

return ok;          

}

void afisare_regulat()

{

if(regulat()==1)

                cout<<"\nGraful este regulat";

else

                cout<<"\nGraful nu este regulat";

}

void noduri_terminale()

{

int i;

cout<<"\nNodurile terminale sunt: ";

for(i=1;i<=n;i++)

       if(grad(i)==1)

                                  cout<<i<<" ";

}

void noduri_izolate()

{

int i,nr=0;

for(i=1;i<=n;i++)

                if(grad(i)==0)

                               nr++;

cout<<"\nNumarul nodurilor izolate este "<<nr;

}

int main()

{

citeste();

afisare_matrice_adiacenta();

afisare_regulat();

noduri_terminale();

noduri_izolate();

return 0;

}

/*

Fisierul text „graf.in” contine pe prima linie un numar natural n reprezentand numarul de varfuri ale unui graf neorientat,

 iar pe fiecare din urmatoarele n randuri cate n valori de 0 si 1 separate prin spatii, reprezentand elementele unei linii a matricei de adiacenta corespunzatoare grafului.

a)Sa se scrie o functie grad ce primeste ca parametru un numar natural x si returneaza gradul varfului x.

b)Sa se scrie programul C++ care citeste datele din fisier si care afiseaza in fisirul text „graf.out”, pe primul rand, separate

prin cate un spatiu varfurile terminale ale grafului, sau mesajul „Nu exista”, daca in graf nu sunt varfuri terminale, folosind apeluri

utile ale subprogramului grad.

Exemplu: Daca fisierul ”graf.in”  are forma:

     5

     0 0 1 0 1

     0 0 0 1 1

     1 0 0 0 0

     0 1 0 0 0

     1 1 0 0 0 

atunci fisierul „graf.out” va contine numerele 3 si 4.

*/

#include<fstream.h>

ifstream f("graf.in");

ofstream g("graf.out");

int k,n,a[10][10],d[10],i,j;

void citeste()

{

//citesc numarul de noduri

f>>n;

//citesc matricea de adiacenta din fisier              

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               f>>a[i][j];

f.close();

}

void scrie()

{

g<<"Matricea de adiacenta este:";

g<<"\n";

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

                g<<a[i][j]<<" ";

g<<"\n";

}

g<<"\n";

}

int grad(int x)

{

int gr=0;

for(j=1;j<=n;j++)

                if(a[x][j]==1)

                               gr++;

return gr;

}0

void varf_terminal()

{

int gasit=0;//pp ca nu sunt noduri terminale

g<<"\nVarfurile terminale sunt: ";

for(i=1;i<=n;i++)

                if(grad(i)==1)

                               {

                               g<<i<<" ";

                               gasit=1;

                               };

                if(gasit==0)

                               g<<"Nu exista varfuri terminale in graf!";

}

int main()

{

citeste();

scrie();

varf_terminal();

return 0;

}

/*

Fisierul text "muchii.txt" contine pe prima linie un numar natural n reprezentвnd numarul de vвrfuri ale unui graf neorientat, pe al doilea

rвnd un numar natural m reprezentвnd numarul de munchii ale unui graf neorientat, iar pe fiecare din urmatoarele m rвnduri cвte doua

 numere naturale, separate pritr-un spatiu, reprezantвnd extremitatile unei muchii a grafului.

a)            Sa se scrie o functie grad ce primeste ca parametru un numar natural x si returneaza gradul vвrfului x.

b)           Sa se scrie programul C++ care citeste datele din fisier, construieste matricea de adiacenta asociata grafului, si care afiseaza

 оn fisirul text "grade.txt", separate prin cвte un spatiu vвrfurile de grad maxim ale grafului, folosind apeluri utile ale subprogramului grad.

Exemplu: Daca fisierul "muchii.txt"  are forma:

     5

     6

     1 2

     2 3

     2 4

     3 4

     3 5

     4 5

atunci fisierul "grade.txt" va contine numerele 2, 3 si 4.

Descriere solutie

Gradul unui vвrf x reprezinta numarul muchiilor incidente cu vвrful x.

Pentru determinarea vвrfurilor de grad maxim se memoreaza gradele vвrfurilor оntr-un vector, fiecare element d[i]

a vectorului va memora gradul vвrfului i. Se determine elementul maxim din vector, apoi se afiseaza pozitiile ocupate

оn vector de valoarea maxima.

*/

#include<fstream.h>

ifstream f("muchii.txt");

ofstream g("grade.txt");

int n,m,i,j,a[10][10],d[20];

void citeste()

{

int k;

f>>n>>m;//citesc numarul de vrfuri si numarul de muchii din fisier

//initializez matricea de adiacenta cu 0

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               a[i][j]=0;

//incrementez vectorul gradelor cu 0

for(k=1;k<=m;k++)

                d[k]=0;

//citesc muchiile din fisier si construiesc matricea de adiacenta

for(k=1;k<=m;k++)       

                {

                f>>i>>j;

                a[i][j]=1;a[j][i]=1;

                d[i]++;d[j]++;

                }

}

void afisare_vector_grade()

{

g<<"Vectorul gradelor este:";

for(i=1;i<=n;i++)

                g<<d[i]<<" ";

g<<"\n";

}

void afisare_matrice()

{

g<<"\nMatricea de adiacenta este:";

g<<"\n";

for(i=1;i<=n;i++)

                {

                for(j=1;j<=n;j++)

                               g<<a[i][j]<<" ";

                g<<"\n";

                }

g<<"\n";

}

//determin maxim din vectorul gradelor

int grad_max()

{

int max;

max=d[1];

for(i=2;i<=n;i++)

                if(d[i]>max)

                               max=d[i];

return max;

}

//afisez nodurile de grad maxim

void afisare_grad_max()

{

int k;

g<<"\nVarfurile cu grad maxim sunt:";

for(k=1;k<=n;k++)

                if(d[k]==grad_max())

                               g<<k<<" ";

}

int main()

{

citeste();

afisare_vector_grade();

afisare_matrice();

g<<"Gradul maxim este:"<<grad_max();

afisare_grad_max();

return 0;

}

#include<fstream.h>

ifstream f("adiacenta.in");

ofstream g("noduri.out");

int n,a[10][10];

void citeste()

{

int i,j;

f>>n;

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               f>>a[i][j];

f.close();

}

//Gradul extern al unui nod x reprezinta numarul arcelor care ies din nodul  x

int grad_extern(int x)

{

int j,gr=0;

for(j=1;j<=n;j++)

                if(a[x][j]==1)

                               gr++;

return gr;

}

//gradul intern al unui nod x reprezinta numarul arcelor care intra оn nodul x (segmentul x ------ j)

int grad_intern(int x)

{

int i,gr=0;

for(i=1;i<=n;i++)

                if(a[i][x]==1)

                               gr++;

return gr;

}

void afisare_grad()

{

int i;

g<<"Nodurile care au gradul intern egal cu gradul extern sunt:";

for(i=1;i<=n;i++)

                if(grad_intern(i)==grad_extern(i))

                               g<<i<<" ";

                              

}

int main()

{

citeste();

afisare_grad();

g.close();

return 0;

}

/*

Problema 26

Fi?ierul text "arce.txt" con?ine pe prima linie un num?r natural n reprezentвnd num?rul de noduri ale unui graf orientat, pe al doilea rвnd un num?r natural m reprezentвnd num?rul de arce ale unui graf orientat, iar pe fiecare din urm?toarele m rвnduri cвte dou? numere naturale separate prin spa?ii, reprezentвnd arcele corespunz?toare unui graf orientat.

a)            S? se scrie o func?ie grad_intern ce prime?te ca parametru un num?r natural x ?i returneaz? gradul intern al nodului x.

Func?ia grad_extern prime?te ca parametru un num?r natural x ?i returneaz? gradul extern al nodului x.

b)           S? se scrie programul C++ care cite?te datele din fi?ier, construie?te matricea de adiacen?? asociat? grafului, ?i care afi?eaz? оn fi?irul text "izolate.txt", separate prin cвte un spa?iu nodurile izolate ale grafului, sau mesajul "Nu exist?", dac? оn graf nu sunt noduri izolate, folosind apeluri utile ale subprogramelor grad_intern ?i grad_extern.

Exemplu: Dac? fi?ierul "arce.txt"  are forma:

     5

     3

     1 2

     2 1

     2 4

atunci fi?ierul "izolate.txt" va con?ine numerele 3 ?i 5.

*/

#include<fstream.h>

ifstream f("arce.txt");

ofstream g("izolate.txt");

int n,m,a[20][20];

void citeste()

{

int i,j,k;

f>>n>>m;//citesc numarul de vrfuri si numarul de muchii din fisier

//initializez matricea de adiacenta cu 0

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               a[i][j]=0;

//citesc muchiile din fisier si construiesc matricea de adiacenta

for(k=1;k<=m;k++)       

                {

                f>>i>>j;

                a[i][j]=1;

                }

}

//cerinta a)

int grad_extern(int x)

{

    int j,k=0;

    for(j=1;j<=n;j++)

        k=k+a[x][j];

    return k;

}

//cerinta a)

int grad_intern(int x)

{

    int i,k=0;

    for(i=1;i<=n;i++)

        k=k+a[i][x];

    return k;

}

void afisare_matrice()

{

int i,j;

g<<"Matricea de adiacenta este:";

g<<"\n";

for(i=1;i<=n;i++)

                {

                for(j=1;j<=n;j++)

                               g<<a[i][j]<<" ";

                g<<"\n";

                }

g<<"\n";

}

void afisare_grade_izolate()

{

                int i,ok=0;//pp ca nu exista noduri izolate

                g<<"Nodurile izolate ale grafului sunt:";

for(i=1;i<=n;i++)

                if(grad_extern(i)==0&&grad_intern(i)==0)

                               {

                               g<<i<<" ";ok=1;//am gasit un nod izolat}

                }

                if(ok==0)

                               g<<"Nu exista!";

}

int main()

{

                citeste();

                afisare_matrice();

                afisare_grade_izolate();

    f.close();

    g.close();

    return 0;

}

/*Problema 27.

Se citesc numere naturale din fisierul text "numere.txt".

Sa se afiseze numerele care au proprietatea de palindrom (numarul citit de la dreapta la stвnga este egal

cu numarul citit de la sвnga la dreapta) si suma cifrelor sa fie para. Se vor folosi: un subprogram palin care va implementa

un algoritm de determinare a proprietatii de numar palindrom si un subprogram care sa calculeze suma cifrelor unui numar natural.

Exemplu: Pentru numerele 12, 12321, 565, 45, 18, 121 se va afisa  565, 121.

*/

#include<fstream.h>

ifstream f("numere.txt");

ofstream g("numere.out");

int v[10],n,i;

void citeste()

{

i=1,n=0;

while(!f.eof())

{

f>>v[i];i++;n++;

}

}

int nrinv(int n)

{

int ninv=0;

while(n!=0)

{

ninv=ninv*10+n%10;

n=n/10;

}

return ninv;

}

int suma_cifre(int n)

{

int s=0;

while(n!=0)

{

s=s+n%10;

n=n/10;

}

return s;

}

void palin()

{

g<<"Numerele palindrom cu suma cifrelor para sunt: ";

for(i=1;i<n;i++)

                if(v[i]==nrinv(v[i])&&suma_cifre(v[i])%2==0)

                               g<<v[i]<<" ";    

}

int main()

{

citeste();

palin();

return 0;

}

#include<fstream.h>

#include<math.h>

ifstream f("date.in");

ofstream g("date.out");

int n,i,j,a[10][10];

void citeste()

{

f>>n;

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               f>>a[i][j];

f.close();

}

void afisare_matrice()

{

g<<"\nMatricea este: "<<"\n";

for(i=1;i<=n;i++)

                {

                for(j=1;j<=n;j++)

                               g<<a[i][j]<<" ";

                g<<"\n";

                }

}

int nrprim(int n)

{

int d,prim=1;//pp ca nr este prim

for(d=2;d<=sqrt(n);d++)

                if(n%d==1)

                               prim=0;

return prim;

}

 

void afisare_prime()

{

int s=0,k=0;

g<<"Numerele prime de deasupra diagonalei principale sunt:";

for(i=1;i<=n-1;i++)

                for(j=i+1;j<=n;j++)

                               if(nrprim(a[i][j]==1)&&(a[i][j]>0)&&(a[i][j]!=1))

                                               {

                                               g<<a[i][j]<<" ";

                                               k++;//numar elementele prime

                                               s=s+a[i][j];//construiesc suma elementelor prime

                                               }

g<<"\nMedia aritmetica a numerelor prime aflate deasupra diagonalei principale este "<<float(s)/k<<".";                      

}

int main()

{

citeste();

afisare_matrice();

afisare_prime();

f.close();

g.close();

return 0;

}

#include<fstream.h>

ifstream f("date.in");

ofstream g("date.out");

int a[10][10], n,i,j;

void citeste()

{

for(i=1;i<=n;i++)

                for(j=1;j<=n;j++)

                               f>>a[i][j];

}

int nrinv(int n)

{

int ninv=0;

while(n)

{

ninv=ninv*10+n%10;

n=n/10;

}

return ninv;

}

void palindrom()

{

int nr=0;

for(i=1;i<=n-1;i++)

                for(j=1;j<=n-1;j++)

                               if(i+j<n+1&&nrinv(a[i][j])==a[i][j])

                               nr++;

if(nr)

                g<<nr;

else

                g<<"Nu exista!";

}

int main()

{

f>>n;

if(n>=1&&n<=50)

{

citeste();

palindrom();

}

else

                g<<"Numarul "<<n<<" nu respecta restrictia problemei!";

return 0;

}