Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (11)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Se da un arbore prin vectorul de tip tata. Calculati si afisati distante dintre oricare doua varfuri ale arborelui sub forma unei matrici.
Distanta dintre doua varfuri este egala cu lungimea lantului care le uneste.
Exemplu:
date.in
6
2 0 2 1 3 1
date.out
0 1 2 1 3 1
1 0 1 2 2 2
2 1 0 3 1 3
1 2 3 0 4 2
3 2 1 4 0 4
1 2 3 2 4 0

#include<fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int n,t[100],a[100][100],p[100];

void citire()
{ fin>>n;
  for(int i=1;i<=n;i++)
      fin>>t[i];
}

void df(int s, int v, int niv)
{
   a[s][v]=a[v][s]=niv;
   p[v]=1;
   for(int i=1;i<=n;i++)
        if((t[i]==v || i==t[v]) && !p[i]) df(s,i,niv+1);
}

void afis()
{
    for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++) fout<<a[i][j]<<" ";
           fout<<endl;
       }
}

int main()
{
  citire();
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=n;j++) p[j]=0;
      df(i,i,0);
  }
  afis();
  fin.close();
  fout.close();
  return 0;
}


sau cu Roy-Floyd

#include<fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int inf=1<<20;
int n,t[100],a[100][100];

void citire()
{ fin>>n;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
       if(i!=j) a[i][j]=inf;
  for(int i=1;i<=n;i++)
  {
      fin>>t[i];
      if(t[i]!=0) a[i][t[i]]=a[t[i]][i]=1;
  }
}

void rf()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j && a[i][j]>a[i][k]+a[k][j])
                   a[i][j]=a[i][k]+a[k][j];
}

void afis()
{
    for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++) fout<<a[i][j]<<" ";
           fout<<endl;
       }
}

int main()
{
  citire();
  rf();
  afis();
  fin.close();
  fout.close();
  return 0;
}

19 nov 2018
Site-ul conține 868 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian