6 mai - stânga/dreapta cu Gorgan + Temă grafică/9 mai

1) Să se afişeze intervalele în care se face căutarea unui element într-un vector ordonat folosind algoritmul de căutare binară.

#include<iostream>
using namespace std;

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

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

void eliminare(int a[],int n,int i)
{int j;
for(j=i;j<n-1;j++)
    a[j]=a[j+1];
}
   
int main()
{int n,a[100],st,dr,s,j,i,s1,s2;
cout<<"n=";
cin>>n;
cout<<"s=";
cin>>s;
cout<<"Citire vector"<<endl;
for(i=0;i<n;i++)
    cin>>a[i];
ordonare(a,n);
cout<<"Afisare vector"<<endl;
for(i=0;i<n;i++)
    cout<<a[i]<<" ";
cout<<endl<<"Intervale"<<endl;
binar(a,s,0,n-1);
}

2) n copii sunt înşiraţi la ora de sport. Gorgan vrea să aleagă un conducător în felul următor:
- dacă spune dreapta, copiii din dreapta rămân pe loc şi ceilaţi pleacă la vestiare
- dacă spune stânga, copiii din stânga rămân pe loc şi ceilalţi pleacă la vestiare
- copilul din mijloc pleacă şi el la vestiare (dacă numărul de copii este impar)
- ultimul rămas este conducătorul
Cunoscându-se numărul de pe tricouri: 1,2,...,n, să se spună dacă elevul cu numărul y poate deveni conducător şi să se afişeze ce spune profesorul în acest caz. 

#include<iostream>
using namespace std;

void afisare(int a[], int n)
{int i;
for(i=1;i<=n;i++)
    cout<<a[i]<<" ";
}

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

void eliminare(int a[],int &n,int i)
{int j;
for(j=i;j<=n;j++)
    a[j]=a[j+1];
n--;
}
 
int main()
{int n,a[100],st,dr,s,j,i,s1,s2,y,t,g;
cout<<"n=";cin>>n;
cout<<"y=";cin>>y;
for(i=1;i<=n;i++)
    a[i]=i;
cout<<"Afisare elevi"<<endl;
for(i=1;i<=n;i++)
    cout<<a[i]<<" ";
cout<<endl<<endl<<"GORGAN says"<<endl;

while(a[1]!=y || n>1)
{
cout<<n<<" "<<endl;
afisare(a,n);
cout<<endl<<endl;
if(n%2==1 && y==n/2+1)
    {cout<<"Nu poate fi conducator"; return 0;}
if(binar(a,y,1,n)==-1)
    {cout<<"Nu poate fi conducator"; return 0;}
if(binar(a,y,1,n)<=n/2)
    cout<<"stanga "<<endl;
else if(binar(a,y,1,n)>n/2)
    cout<<"dreapta "<<endl;

if(binar(a,y,1,n)<=n/2)
    n=n/2;
else if(binar(a,y,1,n)>n/2)
        {if(n%2==1)
            g=n/2+1;
        else g=n/2;
        for(t=1;t<=g;t++)
            eliminare(a,n,1);
        }
        //afisare(a,n);
}

afisare(a,n);
}

3) Temă grafică

#include<graphics.h>
#include<iostream>
using namespace std;

void patrat(int xs,int ys,int l, int n)
{if(n)
{patrat(xs+3*l/4,ys-l/4,l/2,n-1);
patrat(xs+3*l/4,ys+3*l/4,l/2,n-1);
if(n%2==0)
    setfillstyle(1,2);
else setfillstyle(1,10);
delay(10);
bar(xs,ys,xs+l,ys+l);}
}

int main()
{initwindow(800,800);
patrat(20,250,200,10);
delay(100000);
}

4) Sa se modifice algoritmul de cautare binara astfel incat sa se afiseze mesaul DA sau NU in functie de rezultatul cautarii.

#include<iostream>
using namespace std;
char* binar(int a[],int x, int st, int dr)
{int m;
if(st>dr)
    return "NU";
m=(st+dr)/2;
if(a[m]>x)
{return binar(a,x,st,m-1);}
else if(a[m]<x) {return binar(a,x,m+1,dr);}
    else return "DA";
}

int main()
{int y,n,a[100],i;
cout<<"y=";cin>>y;
cout<<"n=";cin>>n;
for(i=0;i<n;i++)
    cin>>a[i];
cout<<binar(a,y,0,n-1);
}

5) Sa se afiseze stanga sau dreapta.

#include<iostream>
using namespace std;
void binar(int a[],int x, int st, int dr)
{int m;
if(st>dr)
    cout<<"NU";
m=(st+dr)/2;
if(a[m]>x)
{cout<<"stanga";binar(a,x,st,m-1);}
else if(a[m]<x) {cout<<"dreapta";binar(a,x,m+1,dr);}
    else cout<<"DA";
}

int main()
{int y,n,a[100],i;
cout<<"y=";cin>>y;
cout<<"n=";cin>>n;
for(i=0;i<n;i++)
    cin>>a[i];
binar(a,y,0,n-1);
}

6) Sa se afiseze modul de calculare a cmmdc a n numere naturale folosind algoritmul DI.

#include <iostream>
using namespace std;
int x[100],n;

void DI(int st, int dr){
int s1,s2,m;
if(st==dr)
{cout<<x[dr]; return;}
m=(st+dr)/2;
cout<<"cmmdc(";
DI(st,m);
cout<<",";
DI(m+1,dr);
cout<<")";
}

int main(){
int i,st=0,dr;
cin>>n;
for(i=0;i<n;i++)
cin>>x[i];
dr=n-1;
DI(st,dr);
return 0;
}