Setul 9
Problema 1 (Conectarea oraşelor cu cost minim)
Se consideră n oraşe. Pentru diferite perechi de oraşe (i, j), 0<i<n, 0<j<n se cunoaşte costul conectării lor directe c[i][j]. Nu toate perechile de oraşe pot fi conectate; pentru perechile care nu pot fi conectate nu se precizează costul. Se cere să se construiască o reţea prin care oricare două oraşe să fie conectate între ele direct sau indirect şi costul total al conectării să fie minim.
Se poate arăta că reţeaua de conectare cerută este un arbore. Problema mai este cunoscută şi ca problema determinării arborelui parţial de cost minim într-un graf. Pentru această problemă există un algoritm greedy de rezolvare numit algoritmul lui Prim. În literatura de specialitate există argumentarea matematică a faptului că acest algoritm găseşte întotdeauna soluţia optimă de conectare a oraşelor.
Se construieşte arborele parţial minim în manieră greedy, adăugând câte un nod la fiecare pas. La început de tot arborele parţial este vid, nu conţine nici un nod. Primul pas constă în adăugarea unui nod arbitrar în arbore. Pe urmă, la fiecare pas se caută muchia de cost minim care porneşte dintr-un nod deja adăugat la arbore şi ajunge într-un nod care nu este în arbore. Se adaugă în arbore nodul în care sfârşeşte muchia găsită.
Să considerăm spre exemplu o reţea de 7 oraşe numerotate de la 0 la 6. Costurile de conectare a oraşelor sunt redate în figură.
Arborele minim este redat cu linii îngroşate. El a fost construit pas cu pas, conform procedeului descris mai sus. Iniţial arborele a fost vid. La primul pas s-a adăugat un nod arbitrar, şi anume nodul 0.
Pe urmă s-a ales muchia de cost minim care pleacă din nodul 0 către celelalte noduri. Muchia de cost minim a fost (0,2) de cost 10. Nodul 2 a fost adăugat în arbore.
La următorul pas s-a ales muchia de cost minim care pleacă din nodurile 0 sau 2 către celelalte noduri. Muchia aleasă a fost (2,1) de cost 9. Nodul 1 a fost adăugat în arbore.
La următorul pas s-a ales muchia de cost minim care pleacă din nodurile 0, 2 sau 1 către nodurile încă neintroduse în arbore. Muchia aleasă a fost (1,5) de cost 3. Nodul 5 a fost adăugat în arbore.
Următoarea muchie aleasă a fost (5,4) de cost 2. Nodul 4 a fost adăugat în arbore. Apoi a fost aleasă muchia (4,6) de cost 2 şi nodul 6 a fost adăugat şi el în arbore.
Pe urmă a fost aleasă muchia (1,3) de cost 4 şi nodul 3 a fost introdus în arbore. În acest moment algoritmul s-a încheiat deoarece toate oraşele au fost conectate la reţea. Costul total al conectării a fost 10 + 9 + 3 + 2 + 2 + 4 = 30.
Fisierul cu date de intrare pentru graful din figură este următorul:
7 0 20 10 0 0 0 0 20 0 9 4 0 3 0 10 9 0 10 0 0 0 0 4 10 0 0 0 0 0 0 0 0 0 2 2 0 3 0 0 2 0 3 0 0 0 0 2 3 0
#include<stdio.h>
#include<stdlib.h>
#define N_MAX 30
#define MINIM 1000
int n;
int dist[N_MAX][N_MAX];
int vizitat[N_MAX];
int oras_sters[N_MAX];
void alege(int *min,int *i_min,int *j_min)
{
int i,j;
*min=MINIM;
*j_min=-1;
for(i=0;i<n;i++)
if(vizitat[i])
for(j=0;j<n;j++)
if(!oras_sters[j]&&dist[i][j]<*min&&dist[i][j])
{*i_min=i;
*j_min=j;
*min=dist[i][j];
}
if(*min==MINIM)
*min=0;
}
int main()
{
printf("Hello world!\n");
FILE *f=fopen("bac.txt","rt");
int i,j,gata=0,min,i_min,j_min,cost_total=0;
int arbore[N_MAX][2];
int count=0;
if(f==NULL)
{
printf("Eroare la deschiderea fisierului");
exit(1);
}
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
fscanf(f,"%d",&dist[i][j]);
for(i=1;i<N_MAX;i++)
{vizitat[i]=0;
oras_sters[i]=0;
}
vizitat[0]=1;
oras_sters[0]=1;
while(!gata)
{
alege(&min,&i_min,&j_min);
cost_total=cost_total+min;
vizitat[j_min]=1;
oras_sters[j_min]=1;
arbore[count][0]=i_min;
arbore[count][1]=j_min;
count++;
if(count>=n)
gata=1;
}
printf("Cost total: %d\n",cost_total);
for(i=0;i<count-1;i++)
{ for(j=0;j<2;j++)
printf("%d ",arbore[i][j]);
printf("\n");
}
fclose(f);
return 0;
}
Problema 2 (Cele mai apropiate puncte de pe o dreaptă)
Se dau N puncte în plan, situate pe o dreaptă paralelă cu axa OX. Să se determine perechea de puncte care sunt cel mai apropiate unul de altul. Dacă există mai multe asemenea perechi, se va determina una din ele.
Datele de intrare se citesc din fişierul puncte.in. Pe prima linie din fişier apare N, numărul de puncte. Pe a doua linie apar N valori reale, reprezentând coordonatele X ale celor N puncte. Coordonatele Y ale punctelor nu se precizează, deoarece toate punctele au aceeaşi coordonată Y. În fişier punctele apar sortate crescător în ordinea coordonatei X.
Programul va scrie în fişierul puncte.out două valori reale reprezentând coordonatele celor mai apropiate două puncte.
Rezolvarea divide and conquer se face în felul următor:
se împarte mulţimea de puncte în două jumătăţi;
punctele fiind sortate după coordonata X, avem trei variante posibile:
fie perechea pe care o căutăm se află în prima jumătate;
fie perechea se află în a doua jumătate;
fie un punct al perechii se află în prima jumătate şi celălalt punct în a doua jumătate;
în manieră divide and conquer rezolvăm subproblemele pentru cele două jumătăţi;
memorăm distanţa minimă găsită pentru prima jumătate şi pentru a doua jumătate;
verificăm dacă există o pereche de puncte cu un punct din prima jumătate şi un punct din a doua jumătate astfel încât să obţinem o distanţă mai mică: se poate demonstra faptul că singura variantă în care am putea obţine o distanţă mai mică este folosind cel mai din dreapta punct din prima jumătate împreună cu cel mai din stânga punct din a doua jumătate;
în final păstrăm distanţa cea mai scurtă din cele trei variante.
Rezolvare majoritar gresita
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int t1,t2;
void punct(int *a,int n)
{
int i,j,min1=0,min2=0,t3,t4;
for(i=a[0];i<n/2;i++)
if(pow(a[i]-a[i+1],2)<min1)
{min1=pow(a[i]-a[i+1],2);
t1=a[i];
t2=a[i+1];
}
for(i=a[n/2];i<n-1;i++)
if(pow(a[i]-a[i+1],2)<min2)
{min2=pow(a[i]-a[i+1],2);
t3=a[i];
t4=a[i+1];
}
if(min1>min2)
{min1=min2;
t1=t3;
t2=t4;
}
}
int main()
{
printf("Hello world!\n");
FILE *f=fopen("bac.txt","rt");
FILE *g=fopen("bac.out","w");
int i,N;
if(f==NULL)
{
printf("Eroare la deschiderea fisierului de citire");
exit(1);
}
if(g==NULL)
{
printf("Eroare la deschiderea fisierului de scriere");
exit(1);
}
fscanf(f,"%d",&N);
int x[N];
for(i=0;i<N;i++)
fscanf(f,"%d",&x[i]);
punct(x,N);
// for(i=0;i<N;i++)
// printf("%d ",x[i]);
fprintf(g,"%d %d",t1,t2);
fclose(f);
return 0;
}