11 mai - interclasare + TEMĂ/12

#include<iostream>
using namespace std;

void interclasare(int a[], int b[], int c[], int &k, int n, int m)
{int i,j;
i=j=k=0;
while(i<n && j<m)
    {
    if(a[i]<=b[j])
        {c[k]=a[i];i++;k++;}
    else {c[k]=b[j];j++;k++;}
    }
while(i<n)
    {c[k]=a[i];i++;k++;}
while(j<m)
    {c[k]=b[j];j++;k++;}
}

int main()
{int a[100],b[100],c[100],n,m,i,j,k;
cout<<"n=";cin>>n;
for(i=0;i<n;i++)
    cin>>a[i];
cout<<"m=";cin>>m;
for(j=0;j<m;j++)
    cin>>b[j];
interclasare(a,b,c,k,n,m);
for(i=0;i<k;i++)
    cout<<c[i]<<" ";
}

1) Se da un şir X sortat crescăţor. Se dă un şir Y neordonat. Pentru fiecare element din şirul Y să se determine dacă acesta apare în şirul X şi să se numere câte apeluri ale funcţiei de căutare binară s-au făcut.

#include<iostream>
using namespace std;
int a[100],m[100],mm,apel[100]={0},i,nr,limita;

void ordonare(int x[], int n)
{int i,j;
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(x[i]>x[j])
            swap(x[i],x[j]);
}

int binar(int v[],int x, int st, int dr, int &y)
{int m;
if(st>dr)
    return -1;
m=(st+dr)/2;
if(v[m]>x)
    {y++;return binar(v,x,st,m-1,y);}
else if(v[m]<x) {y++;return binar(v,x,m+1,dr,y);}
    else return m;
}

int main()
{
cout<<"nr de elemente ale lui X=";cin>>nr;
for(i=0;i<nr;i++)
    cin>>a[i];
ordonare(a,nr);
cout<<"nr de elemente ale lui Y=";cin>>mm;
for(i=0;i<mm;i++)
    cin>>m[i];
for(i=0;i<mm;i++)
    if(binar(a,m[i],0,nr-1,apel[i])==-1)
        apel[i]=-1;
    else binar(a,m[i],0,nr-1,apel[i]);
cout<<endl;
for(i=0;i<mm;i++)
    if(apel[i]==-1)
        cout<<m[i]<<" nu apare in sirul y"<<endl;
    else cout<<"Pentru "<<m[i]<<" au fost necesare "<<apel[i]<<" apeluri"<<endl;
}

2) Se dau 2 şiruri, X şi Y, neordonate. Să se determine folosind DI pentru fiecare element din Y de câte ori apare în X.

#include<iostream>
using namespace std;

void ordonare(int x[], int n)
{int i,j;
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(x[i]>x[j])
            swap(x[i],x[j]);
}

int binar(int v[],int x, int st, int dr)
{int m;
if(st>dr)
    return -1;
m=(st+dr)/2;
if(v[m]>x)
    {return binar(v,x,st,m-1);}
else if(v[m]<x) {return binar(v,x,m+1,dr);}
    else return m;
}

int DI(int x[],int p,int st, int dr)
{int m,s1,s2;
if(st==dr && x[dr]==p)
    return 1;
else if(st==dr)
    return 0;
m=(st+dr)/2;
s1=DI(x,p,st,m);
s2=DI(x,p,m+1,dr);
return s1+s2;
}

int main()
{int x[100],y[100],i,j,m,n,p,r,t,k;
cout<<"nr X=";cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
sort(x,n+x);
cout<<"nr Y=";cin>>m;
for(i=0;i<m;i++)
    cin>>y[i];
for(i=0;i<m;i++)
    cout<<y[i]<<" apare de "<<DI(x,y[i],0,n-1)<<" ori in sirul X"<<endl;
}