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# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Colorarea hartii folosind metoda Greedy.
Fiind data o harta cu n tari, se cere o solutie de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari ce au frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.
Exemplu:
colorare.in
6
alb verde galben rosu
1 2
1 3
1 4
1 5
1 6
2 3
2 5
2 6
3 4
3 5
4 5
5 6
colorare.out
1 alb
2 verde
3 galben
4 verde
5 rosu
6 galben


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

int A[101][101];// A[i][j]==1 pt tari vecine, 0 altfel
int X[101],n;//X[i]=indicele culorii tarii i
char C[5][21];//culorile

void afisare()
{
    for(int i=1;i<=n;i++)
        fout<<i<<" "<<C[X[i]]<<"\n";//afisez tara si culoarea
    fout<<endl;
}

int valid(int k)
{//1 daca tara k poate fi colorata cu X[k], 0 altfel
    for(int i=1;i<k;i++)//pt tarile colorate deja
        if(A[i][k]==1 && X[i]==X[k]) return 0;//exita tara invecinata care are aceeasi culoare=>0
    return 1;
}

int alege(int k)
{//alege culoarea minima valida
    for(int i=1;i<=4;i++)//am 4 culori
        {
            X[k]=i;//plasez culoarea
            if(valid(k)) return i;//daca e buna o returnez
        }
    return 0;//daca nu putem colora
}

void colorare()
{//plaseaza in X[i] culoarea tarii i
    for(int i=1;i<=n;i++)
        X[i]=alege(i);//culoarea minima
}

int main()
{
    int t1,t2;
    fin>>n;//citesc nr de tari
    for(int i=1;i<=4;i++)
        fin>>C[i];//citesc culorile
    while(fin>>t1>>t2)//pereche de tari vecine
    {
        A[t1][t2]=1;//pun 1 in matrice
        A[t2][t1]=1;
    }
    colorare();
    afisare();
    return 0;
}

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