Acest algoritm constituie un exemplu clasic de aplicare a tehnicii de programare Divide et Impera.
Avem de sortat un sir de n elemente. Se imparte vectorul in doi vectori de dimensiune egala pana se obtin vectori de dimensiune unu sau doi. Daca dimensiunea este unu, atunci vectorul este sortat, iar daca dimensiunea este doi si daca primul element este mai mare decat al doilea atunci cele doua elemente se interschimba; altfel vectorul este deja sortat. Apoi se interclaseaza vectorii, priviti ca liste, obtinand tot un vector sortat. Se repeta interclasarea pana obtinem un vector de dimensiune n, sortat.
#include <iostream>
using namespace std;
int x[100],n;
void divizeaza(int s,int d,int &m)
{
m=(s+d)/2;
}
void interclaseaza(int s,int d,int m)
{
int i=s,j=m+1,k=1,v[100];
while(i<=m&&j<=d)
{
if(x[i]<x[j])
{
v[k]=x[i];i++;
}
else{v[k]=x[j];j++;}
k++;
}
if(i<=m)
while(i<=m)
{v[k]=x[i];i++;k++;}
else
while(j<=d)
{
v[k]=x[j];j++;k++;
}
for(k=1,i=s;i<=d;k++,i++)
x[i]=v[k];}
void mergesort(int s,int d)
{int m;
if(s<d)
{
divizeaza(s,d,m);
mergesort(s,m);
mergesort(m+1,d);
interclaseaza(s,d,m);
}
}
int main()
{
int i; cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"x["<<i<<"]=";cin>>x[i];
}
mergesort(1,n);
cout << "vectorul sortat" << endl;
for(i=1;i<=n;i++)
cout<<x[i]<<" ";
return 0;
}
-------------------------------------------------
Trei probleme de logica:
1. Un om vrea sa mearga de la Tulcea la Bucuresti. El nu cunoaste drumul. Ajunge la o intersectie
unde se afla doi oameni. Primul spune doar adevarul al doilea spune doar minciuni. Pe care trebuie sa il
intrebe si ce intrebare trebuie sa puna ca sa afle care este drumul corect ?
2. Pe malul unei ape se afla o capra o varza si un lup. Un om poate traversa raul cu barca dar poate
duce un singur lucru o data. In ce ordine trebuie sa treaca cele trei lucruri pe malul celalalt ?
3. Un rege bogat vinde toata averea si pleaca pe mare. El este atacat de un pirat fioros care ii fura comoara.
Piratul ingroapa comoara si face o harta. El ajunge pe o insula unde se afla fiica regelui. Cum face aceasta
ca sa intre in posesia comorii ?
incepe program >
piratul se apropie de insula ;
piratul pierde harta >
harta ajunge pe tarm ;
o furtuna se isca in larg >
corabia naufragiaza ;
corabia naufragiaza >
piratul pierde harta ;
piratul se apropie de insula >
o furtuna se isca in larg ;
harta ajunge pe tarm >
termina program ;