Apropiere

#include<iostream>
#include<fstream>
#include<graphics.h>
using namespace std;
int main()
{initwindow(1360,950,"The Doppler Effect");
int aa,i=0,j,k,m,p,n,a=1000,b,c;
a=30;
aa=30;
b=300;
for(i=1;i<50;i++)
{
while(aa<=b-30)
{ 
    a=a+3;
    aa=aa+10;
    if(aa%4==0)
    b--;
    setcolor(4);
delay(10);
    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);
  
 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
 
 
}

while(aa>50)
{
    a=a+3;
    aa=aa-10;
    if(a%4==0)
        b--;
    setcolor(4);
    delay(10);
    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);
 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
}
a=30;
aa=30;
}
delay(500000);
}

Depărtare

#include<iostream>
#include<fstream>
#include<graphics.h>
using namespace std;
int main()
{initwindow(1360,950,"The Doppler Effect");
int aa,i=0,j,k,m,p,n,a=1000,b,c;
a=30;
aa=30;
b=100;
for(i=1;i<=50;i++){
while(aa<=b-30)
{
    a=a+5;
    aa=aa+10;
    if(a%2==0)
        b++;
    setcolor(4);

    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(1);
    setfillstyle(1,0);
    floodfill(aa,a,0);

 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
 
 
}

while(aa>0)
{
    a=a+5;
    aa=aa-10;
    if(a%2==0)
        b++;
    setcolor(4);

    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);
 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
}
a=30;
aa=30;
}
delay(500000);
}

Pe "scurt"

#include<iostream> // -1 = apropiere; 1 = departare
#include<fstream>
#include<graphics.h>
using namespace std;
int main()
{initwindow(1360,950,"The Doppler Effect");
int aa,i=0,j,k,m,p,n,a=1000,b,c;

ifstream f("date");
f>>c;
if(c==1)
{a=30;
aa=30;
b=100;
for(i=1;i<=50;i++){
while(aa<=b-30)
{ 
    a=a+5;
    aa=aa+10;
    if(a%2==0)
        b++;
    setcolor(4);

    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(1);
    setfillstyle(1,0);
    floodfill(aa,a,0);
 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
 
 
}

while(aa>0)
{
    a=a+5;
    aa=aa-10;
    if(a%2==0)
        b++;
    setcolor(4);
//    delay(10);
    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);
 
    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
}
a=30;
aa=30;
}
delay(500000);
}
else
{a=30;
aa=30;
b=500;
for(i=1;i<50;i++)
{
while(aa<=b-30)
{
    a=a+3;
    aa=aa+10;
    if(aa%4==0)
    b--;
    setcolor(4);
delay(10);
    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);
 

    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);


}

while(aa>50)
{
    a=a+3;
    aa=aa-10;
    if(a%4==0)
        b--;
    setcolor(4);
    delay(10);
    circle(aa,a,30);
    setfillstyle(1,4);
    floodfill(aa,a,4);
    delay(10);
    setfillstyle(1,0);
    floodfill(aa,a,0);

    setcolor(15);
    rectangle(b,0,b+10,750);
    delay(10);
    setcolor(0);
    rectangle(b,0,b+10,750);
}
a=30;
aa=30;
}
delay(500000);
}}

1. Fişierul BAC.TXT are pe prima linie două numere naturale n şi m (0<n<1000, 0<m<1000)
separate prin câte un spaţiu, pe linia a doua n numere întregi ordonate strict crescător, iar
pe linia a treia m numere naturale distincte. Numerele din fişier aflate pe linia a doua şi a
treia au cel mult 6 cifre fiecare şi sunt despărţite în cadrul liniei prin câte un spaţiu. Să se
scrie un program care citeşte toate numerele din fişier şi afişează pe ecran, despărţite prin
câte un spaţiu, toate numerele de pe a doua linie a fişierului care apar şi pe linia a treia a
acestuia.
Exemplu: dacă fişierul are următorul conţinut:
6 5
2 3 4 5 8 9
4 5 2 11 8
atunci se va afişa: 5 2 8 4, nu neapărat în această ordine.
a) Descrieţi în limbaj natural o metodă de rezolvare eficientă ca timp de executare. (4p.)
b) Scrieţi programul C/C++ corespunzător metodei descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
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;
}
int main()
{int n,m,a[100],p;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n>>m;
for(int i=1;i<=n;i++)
    f>>a[i];
while(f>>p)
    if(binar(a,p,1,n)!=-1)
        cout<<p<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

2. Fişierul text bac.in conţine pe prima sa linie un număr natural n (0<n<10000), iar pe
următoarea linie n numere naturale din intervalul [1,100] separate prin câte un spaţiu.
Se cere să se citescă din fişier toate numerele şi să se afişeze pe ecran numărul sau
numerele care apar de cele mai multe ori printre numerele citite de pe a doua linie a
fişierului. Numerele afişate vor fi separate prin câte un spaţiu. Alegeţi un algoritm de
rezolvare eficient atât din punctul de vedere al timpului de executare cât şi al gestionării
memoriei. .
Exemplu: dacă fişierul bac.in are următorul conţinut:
12
1 2 2 3 2 9 3 3 9 9 7 1
pe ecran se vor afişa valorile 2, 3 şi 9, nu neapărat în această ordine.
a) Explicaţi în limbaj natural metoda utilizată justificând eficienţa acesteia (4-6 rânduri) (4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
if(n>mm)
    mm=n;}
for(i=1;i<=mm;i++)
    if(v[i]==m)
        cout<<i<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

3. Se citeşte de pe prima linie a fişierului numere.in un număr natural n (0<n<10000) şi, de pe a doua linie a fişierului, n numere naturale din intervalul [1,100] şi se cere să se
afişeze pe ecran, în ordine crescătoare, despărţite prin câte un spaţiu, numărul sau
numerele întregi din intervalul [1,100] care nu apar printre numerele citite. Dacă pe a
doua linie a fişierului apar toate numerele din intervalul precizat, se va afişa mesajul NU
LIPSESTE NICIUN NUMAR. Alegeţi un algoritm de rezolvare eficient din punctul de
vedere al timpului de executare.
Exemplu: pentru fişierul numere.in cu următorul conţinut
12
4 2 3 1 6 5 7 8 9 11 10 100
se vor afişa valorile 12 13 … 99.
a) Explicaţi în limbaj natural metoda utilizată, justificând eficienţa acesteia (4-6 rânduri).
(4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
}
for(i=1;i<=100;i++)
    if(v[i]==0)
        cout<<i<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

4. Fişierul text bac.in conţine pe prima sa linie un număr natural n (0<n<10000), iar pe
următoarea linie n numere naturale din intervalul [1,100]. Se cere să se citescă din fişier
toate numerele şi să se afişeze pe ecran, în ordine descrescătoare, toate numerele care
apar pe a doua linie a fişierului şi numărul de apariţii ale fiecăruia. Dacă un număr apare de
mai multe ori, el va fi afişat o singură dată. Fiecare pereche „valoare - număr de apariţii” va
fi afişată pe câte o linie a ecranului, numerele fiind separate printr-un spaţiu, ca în exemplu.
Alegeţi un algoritm de rezolvare eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fişierul bac.in are următorul conţinut:
12
1 2 2 3 2 2 3 3 2 3 2 1
pe ecran se vor afişa, în această ordine, perechile:
3 4
2 6
1 2
a) Explicaţi în limbaj natural metoda utilizată justificând eficienţa acesteia (4-6 rânduri) (4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
if(n>mm)
    mm=n;}
for(i=mm;i>=1;i--)
    cout<<i<<" "<<v[i]<<endl;
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
} 

Problema BAC s1, s2

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int s1,s2,a,b,c1,c2,c3,c4,c5,nr=0;
clock_t x,y;
x=clock();
cin>>s1>>s2;
a=s1;b=s2;
if(s1>9)a=9;
if(s2>9)b=9;
for(c1=1;c1<=a;c1++)
{c2=s1-c1;
for(c3=0;c3<=9;c3++)
    for(c4=0;c4<=b;c4++)
    {c5=s2-c4;
    if(c5<10 && c2<10)
    {cout<<c1*10000+c2*1000+c3*100+c4*10+c5<<endl;
    nr++;}
    }
}
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
cout<<endl<<nr;
}

Câte operaţii se fac într-o secundă?

#include<iostream>
using namespace std;
int main()
{int i,j;
clock_t x,y;
i=0;
x=clock();
y=clock();
while((double)(y-x)/CLOCKS_PER_SEC<1)
    {i++;
    y=clock();}
//y=clock();
    cout<<i<<" operatii";
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

Cât a durat ordonarea unui tablou folosind 2 algoritmi de ordonare sau pe 2 cazuri diferite (favorabil/devaforabil/mediu)? --- ORDONARE CRESCĂTOARE
CAZ FAVORABIL: elementele vectorului sunt citite în ordine crescătoare - 0.015s
CAZ DEFAVORABIL: elementele vectorului sunt citite în ordine descrescătoare - 0.031s
CAZ MEDIU: elementele vectorului sunt citite în mod absolut fortuit

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int a[100],n,i,j,aux;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
clock_t x,y;
x=clock();

for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(a[i]<a[j])
        {aux=a[i];
        a[i]=a[j];
        a[j]=aux;}
       
for(i=1;i<=n;i++)
    cout<<a[i]<<" ";

y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

Creşterea timpului de execuţie la un algoritm de backtracking

Ex: Să considerăm algoritmul backtracking de generare a partiţiilor unui număr

Timpul de execuţie variază în funcţie de datele de intrare. De exemplu:

partiţiile numărului 25 se generează în 0.437s

partiţiile numărului 26 se generează în 0.875s

partiţiile numărului 27 se generează în 1.797s

partiţiile numărului 28 se generează în 3.500s

partiţiile numărului 29 se generează în 6.906s

partiţiile numărului 30 se generează în 15.313s

De asemenea, timpul de execuţie variază, în cazul în care soluţiile se şi afişează, şi în funcţie de modul de afişare. Astfel:

partiţiile numărului 10 se generează şi se afişează pe ecran în 21.453s

partiţiile numărului 10 se generează şi se afişează într-un fişier în 0.094s

#include<iostream>
#include<fstream>
using namespace std;
int x[100],n;
void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    cout<<x[i]<<"+";
cout<<"\b ";
cout<<endl;}
void back(int i,int s)
{int j;
for(j=1;j<=s;j++)
{x[i]=j;
    if(x[i]==s)
        afisare(i);
    else back(i+1,s-x[i]);
}
}
int main()
{cin>>n;
ofstream g("date");
clock_t x,y;
x=clock();
back(1,n);
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

Se citesc de la tastatură două numere naturale s1 si s2 (0<s1≤18, 0≤s2≤18) si se cere

scrierea în fisierul BAC.TXT, fiecare pe câte o linie, în ordine strict crescătoare, a tuturor

numerelor naturale cu exact 8 cifre, pentru care suma primelor două cifre este egală cu

s1, iar suma ultimelor două cifre este egală cu s2.

Problema poate fi rezolvată prin mai multe metode:

1.   Parcurgem toate numerele de 5 cifre şi verificăm dacă îndeplinesc condiţiile, după care le afişăm

2.   Generăm toate valorile posibile pentru cele 5 cifre ale numărului astfel încât condiţiile problemei să fie respectate

A doua soluţie reprezintă calea cea mai eficientă dpdv al timpului de execuţie (0.015 pentru s1=s2=18). Pentru aceleaşi date de intrare, rezolvarea problemei folosind prima metodă necesită un timp de execuţie mai mare (1,047 s). Timpul de execuţie include afişarea soluţiilor pe ecran.

Metoda eficientă

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int c,d,s1,s2,a,b,c1,c2,c3,c4,c5,c6,c7,c8,nr=0;
clock_t x,y;
cin>>s1>>s2;
x=clock();
a=s1;b=s2;
c=1;d=0;
if(s1>9){a=9;c=s1-9;}
if(s2>9){b=9;d=s2-9;}
for(c1=c;c1<=9;c1++)
{c2=s1-c1;
for(c3=0;c3<=9;c3++)
    for(c4=0;c4<=9;c4++)
        for(c5=0;c5<=9;c5++)
            for(c6=0;c6<=9;c6++)
                for(c7=d;c7<=9;c7++)
                    {c8=s2-c7;
                    //cout<<c1*10000000+c2*1000000+c3*100000+c4*10000+c5*1000+c6*100+c7*10+c8<<endl;
                    nr++;
                    }
}
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
cout<<endl<<nr;
}

PROIECT

#include<iostream>
#include<fstream>
using namespace std;
int main()
{int n,a[100],c,s,i,j;
ifstream f("date");
clock_t x,y;
x=clock();
f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
f>>c;
for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(a[i]>a[j])
            swap(a[i],a[j]);
for(i=n;i>0;i--)
{s=0;
for(j=i;j>0;j--)
    if(s+a[j]<=c)
    {s=s+a[j];
    cout<<a[j]<<" ";
    a[j]=c+1;}
    if(s+a[j]>=c)
        cout<<endl;
}
cout<<endl;
y=clock() ;
cout<<(double)(y-x)/CLOCKS_PER_SEC;
}

Problema rucsacului

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,C,m[100][100],s[100],v[100];

void citire()
{int i,j;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
    f>>s[i]>>v[i];
f>>C;}

void afisare()
{int i,j;
for(i=1;i<=n;i++)
{    for(j=1;j<=C;j++)
        cout<<setw(3)<<m[i][j];
cout<<endl;}
}

int maxim(int a,int b)
{if(a>b)return a;
else return b;
}

int main()
{citire();
int i,j;
for(i=1;i<=n;i++)
    for(j=1;j<=C;j++)
        if(s[i]==j || m[i-1][j-s[i]]!=0)
            m[i][j]=maxim(m[i-1][j],m[i-1][j-s[i]]+v[i]);
        else m[i][j]=m[i-1][j];
afisare();
}

Fisier

5
3 6
2 4
4 6
1 5
6 18
10

N piese de domino sunt aliniate pe un covor. Sa se extraga dintre acestea cat mai putine, astfel incat cele care raman sa formeze un sir care respecta regula acestui joc.

#include<iostream>
#include<iomanip>
#include<fstream>
using namespace std;
int main()
{int n,a[20],y[20],b[20],u[20],i,j,max,v,r;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
f>>a[i]>>b[i];
y[n]=1;
u[n]=-1;
for(i=n-1;i>0;i--)
{
max=0;r=-1;
for(j=i+1;j<=n;j++)
if(b[i]==a[j] && y[j]>max)
{max=y[j];
r=j;}
y[i]=max+1;
u[i]=r;
}
max=y[0];
r=0;
for(i=1;i<=n;i++)
if(y[i]>max)
{max=y[i];
r=i;}
cout<<"lungime maxima: "<<max<<endl;
cout<<"Trebuie eliminate "<<n-max<<" elemente"<<endl<<endl;
for(i=1;i<=n;i++)
cout<<setw(3)<<a[i]<<"-"<<b[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<y[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<u[i];
cout<<endl<<endl;
while(r!=-1)
{cout<<a[r]<<"-"<<b[r]<<" ";
r=u[r];
}
}

Fişier

9
1 2
2 4
2 3
2 5
4 7
3 6
4 8
7 5
5 6

Se dau n cuburi de diverse culori si laturi. Sa se afiseze cel mai lung turn care se poate construi astfel incat 2 cuburi alaturate sa aiba culori diferite si un cub sa se aseze doar pe unul mai mare decat el. 

#include<iostream>
#include<iomanip>
#include<fstream>
using namespace std;
struct cub{
int l;
char c;
}a[10];
int main()
{int n,y[20],u[20],i,j,max,v,r;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
f>>a[i].l>>a[i].c;
y[n]=1;
u[n]=-1;
for(i=n-1;i>0;i--)
{
max=0;r=-1;
for(j=i+1;j<=n;j++)
if(a[i].l>a[j].l && a[i].c!=a[j].c && y[j]>max)
{max=y[j];
r=j;}
y[i]=max+1;
u[i]=r;
}
cout<<"lungime maxima: "<<max<<endl;
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<y[i];
cout<<endl;
for(i=1;i<=n;i++)
cout<<setw(5)<<u[i];
cout<<endl<<endl;
max=y[1];
r=1;
for(i=1;i<=n;i++)
if(y[i]>max)
{max=y[i];
r=i;}
do{cout<<a[r].l<<"-"<<a[r].c<<endl;
r=u[r];
}
while(r!=-1);
}

Fişier

9
10 R
8 N
8 R
8 A
7 N
6 M
4 R
4 M
3 V

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int a[10][10],n,b[10][10],c[10][10];

void citire()
{int i,j;
ifstream f("date");
f>>n;
for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        f>>a[i][j];
}

void afisare()
{int i,j;
for(i=1;i<=n;i++)
{    for(j=1;j<=n;j++)
    if(b[i][j]!=0)
        cout<<setw(3)<<b[i][j];
cout<<endl;}
cout<<endl;
}

int maxim(int a,int b)
{if(a>b)
    return a;
else return b;
}

int max2(int a[])
{int i,maxim=a[1];
for(i=1;i<=n;i++)
    if(a[i]>maxim)
        maxim=a[i];
    return maxim;
}

int main()
{int i,j,p;
citire();
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        b[i][j]=maxim(b[i-1][j-1],b[i-1][j])+a[i][j];
afisare();
cout<<endl;
for(i=n;i>0;i--)
    {p=max2(b[i]);
    for(j=1;j<=i;j++)
    {if(b[i][j]==p)
        c[i][j]=1;}
    }
cout<<"Drumul parcurs"<<endl;
for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        if(c[i][j]==1)
            cout<<a[i][j]<<" ";
}