Probleme proiect

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;
}