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

"PROFI te adoră la orice oră!" devine sloganul blogului de acum înainte pe toată durata sponsorizării pe care lanţul de Supermarket-uri Profi a decis să ne-o acorde până la încheierea studiilor în Liceul de Informatică "Tiberiu Popoviciu" din Cluj-Napoca.

Dorim să le mulţumim pe această cale domnilor de la Profi Grigorescu, Profi Mărăşti, dar în special celor de la Profi Zorilor. Pe cei din urmă îi înţelegem că, în condiţiile meteo provaidate de end-ul lunii noiembrie, nu ies afară din magazin să ne ovaţioneze la trecerea prin preajma lor. Iată, mai jos, de ce "PROFI te adoră la orice oră!"

Probleme

6. Se consideră un număr nelimitat de rucsaci de acelaşi tip, cu fiecare putându-se transporta o greutate maximă G şi n<=1000 obiecte de greutăţi g1, g2, …, gn. Să se determine numărul minim de rucsaci necesari pentru a transporta toate obiectele.

#include<iostream>
#include<fstream>
using namespace std;
int a[100],n,G;
void citire()
{int i;
ifstream f("date.in");
f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
f>>G;
}

int main()
{int s=0,nr=1,i,j;
citire();
sort(a,n+a);
for(i=1;i<=n;i++)
    if(a[i]>G)
        a[i]=0;
for(i=n;i>0;i--)
{if(a[i]!=0)
    {s=a[i];
    cout<<a[i]<<" ";
    a[i]=0;
for(j=1;j<i;j++)
{    if(a[j]!=0)
    {    if(s+a[j]<=G)
        {    s=s+a[j];
            cout<<a[j]<<" ";
            a[j]=0;
        }
        else if(s+a[j]>G)
        {    nr++;
            s=0;
            cout<<endl;
            j=i;
        }
    }
}
    }
}
cout<<endl<<endl<<nr<<" ruxa";
}

Fişier

8
1 3 4 5 8 6 2 6
8

7. Se dau două şiruri de lungime N şi un număr K (N<1000 şi K<1000). Cele două şiruri au doar elementele 1 şi –1. Scopul este de a transforma primul şir în al doilea. Singura operaţie permisă este de a selecta o secvenţă de K elemente alăturate şi să le inversăm semnul la toate numerele cuprinse în această zonă. Dacă este posibil, se va afişa numărul minim de operaţii şi apoi poziţia de început a fiecărei operaţii efectuate.

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

void citire()
{ifstream f("date.in");
int i;
f>>n>>k;
for(i=1;i<=n;i++)
    f>>a[i];
for(i=1;i<=n;i++)
    f>>b[i];
}

int verifica()
{int ok=1,i;
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
        ok=0;
return ok;
}

void aplica(int i)
{int j;
for(j=i;j<i+k;j++)
    a[j]=-a[j];
}

int main()
{int i,j,k=0;
citire();
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
    {aplica(i);
    v[k]=i;
    k++;
    if(verifica()==1)
        i=n+1;
    else i=1;
    }
cout<<k<<" operatii"<<endl;
for(i=0;i<k;i++)
    cout<<v[i]<<" ";
}

Fişier

5
2
-1 1 1 1 -1
1 1 -1 1 -1

#include<iostream>
#include<fstream>
using namespace std;
int a[10][10],n,m,sol[10][10],ax,bx,cx,ay,by,cy,oka=1,okb=2,okc=3,nr;

void citire()
{int i,j;
ifstream f("date");
f>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        f>>a[i][j];
f>>ax>>ay>>bx>>by>>cx>>cy;
}

void fill(int i, int j, int k)
{
    if(a[i][j]==k)
    {
    a[i][j]=-k;nr++;
    if(i==bx && j==by)
        okb=1;
    if(i==cx && j==cy)
        okc=1;
    fill(i-1,j,k);
    fill(i-1,j+1,k);
    fill(i,j+1,k);
    fill(i+1,j+1,k);
    fill(i+1,j,k);
    fill(i+1,j-1,k);
    fill(i,j-1,k);
    fill(i-1,j-1,k);
    }
}

int main()
{int nra,i,j,k,nrb,nrc,minim=INT_MAX;
citire();
k=a[ax][ay];
oka=1;
okb=2;
okc=3;
fill(ax,ay,k);
nra=nr;
nr=0;
if(oka==1 && okb==2 && okc==3)
{k=a[bx][by];
fill(bx,by,k);
nrb=nr;nr=0;
if(okc==3)
    cout<<"Obiecte diferite";
fill(cx,cy,a[cx][cy]);
nrc=nr;
if(nra<=nrb && nra<=nrc)
    cout<<endl<<nra;
if(nrb<=nra && nrb<=nrc)
    cout<<endl<<nrb;
if(nrc<=nrb && nrc<=nra)
    cout<<endl<<nrc;
}

}

GREEDY. NETERMINATA. Se dau n numere întregi nenule B={b1, b2, …, bn} si m numere întregi nenule a1, a2, …, am. (m<n). Să se determine o submulţime a mulţimii B care maximizează valoarea expresiei
E=a1*x1 + a2*x2 + … + am*xm

#include<iostream>
#include<fstream>
using namespace std;
int n,m,b[100],a[100];

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

int main()
{int e=0,i,j,aneg[10],bneg[10],k=0,l=0,mm;
citire();
sort(a,m+a);
sort(b,n+b);
mm=m;
for(i=1;i<=m;i++)
    if(a[i]<0)
    {aneg[k]=a[i];k++;}
for(i=1;i<=n;i++)
    if(b[i]<0)
    {bneg[l]=b[i];l++;}
for(i=1;i<k;i++)
    for(j=i+1;j<=k;j++)
        if(abs(aneg[i])>abs(aneg[j]))
            swap(aneg[i],aneg[j]);
       
for(i=1;i<l;i++)
    for(j=i+1;j<=l;j++)
        if(abs(bneg[i])>abs(bneg[j]))
            swap(bneg[i],bneg[j]);

    while(k>0)
    {    e=e+aneg[k]*bneg[l];
        k--;
        l--;
    }
    while(mm>0)
    {
        if(a[i]>0)
            {e=e+a[mm]*b[n];
    mm--;
    n--;}
            else break;
    }

cout<<e;
}

Se da un numar n si multimea {1,2,3...n}. Sa se afiseze o submultime de lungime maxima care are proprietatea ca niciun element nu se imparte la niciun altul.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100],x[100],maxi[100],ma=0;

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

int verif(int i)
{int j;
for(j=1;j<i;j++)
    if(x[i]%x[j]==0)
        return 0;
return 1;}

void back(int i)
{int j;
for(j=x[i-1]+1;j<=n;j++)
{x[i]=j;
if(verif(i))
    {if(i>ma)
        {ma=i;
    for(int k=1;k<=ma;k++)
        maxi[k]=x[k];
        }
    back(i+1);
    }
   
}
}

int main()
{int i;
cin>>n;
for(i=1;i<=n;i++)
    a[i]=i;
back(1);
afisare(maxi,ma);
}

Se citeşte un şir de n numere întregi. Să se aleagă din şir un număr maxim de elemente astfel încât produsul lor să fie maxim. De exemplu, pentru n = 5 şi şirul 3, –4, 2, –5, –8 se vor alege 3, 2, –5, –8.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=1,v[100],s=0,b[100],c[100],ok=0,nrneg=0;
citire();
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(abs(a[i])>abs(a[j]))
            swap(a[i],a[j]);
for(i=0;i<n;i++)
    if(a[i]<0)
        nrneg++;
if(nrneg%2==1)
    for(i=0;i<n;i++)
        if(a[i]<0)
            {a[i]=1;
            break;}
cout<<"Numerele alese"<<endl;
for(i=0;i<n;i++)
    {if(a[i]!=1)
        cout<<a[i]<<" ";
    p*=a[i];}
    cout<<endl<<"Produsul "<<p;
}

Se dă un şir de n nr. nat. Folosind un algoritm Greedy, partiţionaţi şirul în două submulţimi care au proprietatea că diferenţa dintre sumele elementelor este minimă.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=0,v[100],s=0,b[100],c[100],ss=0;
citire();
sort(a,n+a);
for(i=0;i<n;i++)
    s=s+a[i];
for(i=n-1;i>=0;i--)
{    if(ss+a[i]<=s/2)
        {b[k]=a[i];
        ss=ss+b[k];
        k++;}
    else
        {v[p]=i;
        p++;}
}
for(i=0;i<p;i++)
    {c[j]=a[v[i]];
    j++;}
afisare(b,k);
cout<<"Suma "<<ss<<endl;
afisare(c,j);
cout<<"Suma "<<s-ss<<endl;
cout<<"Diferenta "<<abs(s-ss-ss);
}

Fişier

9
2 5 7 1 9 10 6 4 3

Se da un punct din interiorul unui obiect (intr-o matrice 0-1). Sa se determine numarul de valori 0 situate in imediata vecinatate a frontierei obiectului.

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],viz[100][100],n,xx,yy,nr;

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

void fill(int x, int y)
{
    if(x>=1 && x<=n && y>=1 && y<=n)
    if(a[x][y]==1 && viz[x][y]==0)
        {viz[x][y]=1;
        fill(x,y+1);
        fill(x,y-1);
        fill(x-1,y);
        fill(x+1,y);}
    else if(x>=1 && x<=n && y>=1 && y<=n && a[x][y]==0)
    {    if(viz[x][y]==0)
        nr++;
    viz[x][y]=2;}
}

int main()
{citire();
fill(xx,yy);
cout<<nr;
}

Fisier

5
0 1 1 0 0
0 0 0 0 1
1 1 0 0 0
0 0 0 0 1
1 1 1 0 0
3 1

Se da o fotografie color (reprezentata printr-o matrice nxm). Culorile sunt numere intregi intre 0 si 9. Sa se verifice daca exista o culoare majoritara. (care sa acopere mai mult de jumatate din suprafata matricii.)

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],n,m;

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

int main()
{
int v[100]={0},i,j,p,k;
citire();
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        {p=a[i][j];
        v[p]++;}
for(k=0;k<=9;k++)
    if(v[k]>=n*m/2)
        {cout<<k<<" "<<v[k]<<endl;break;}
cout<<"Culoarea majoritara "<<k<<" apare de "<<v[k]<<" ori";
}

Fisier

5 5
1 1 1 2 1
2 2 1 1 1
4 5 5 5 1
4 2 5 6 7
1 1 1 1 1

In conditiile problemei 6, sa se verifice daca exista un obiect care sa acopere mai mult de jumatate din matrice.

#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],n,m,nr;

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

void fill(int x,int y,int k)
{
    if(x>=1 && x<=n && y>=1 && y<=m)
    if(a[x][y]==k)
        {a[x][y]=(-1)*k;
        nr++;
        fill(x,y+1,k);
        fill(x,y-1,k);
        fill(x-1,y,k);
        fill(x+1,y,k);}
}

int main()
{int i,j,k;
citire();
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {k=a[i][j];
    nr=0;
    fill(i,j,k);
    if(nr>=n*m/2)
        {cout<<k<<" "<<nr;return 0;}
    }
}

Fisier

5 5
1 1 1 1 1
2 2 2 2 2
4 2 2 2 2
4 2 2 2 2
1 1 1 1 1

Sa se verifice daca 2 puncte dintr-o fotografie fac parte din acelasi obiect.

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,i,j,is,js,iis,jjs;

void citire()
{ifstream f("date");
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
    f>>is>>js>>iis>>jjs;
}

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

void fill(int i,int j)
{
    if(a[i][j]==1)
    {
        a[i][j]=2;
        fill(i-1,j);
        fill(i-1,j+1);
        fill(i,j+1);
        fill(i+1,j+1);
        fill(i+1,j);
        fill(i+1,j-1);
        fill(i,j-1);
        fill(i-1,j-1);
    }
}

int main()
{   citire();
       fill(is,js);
    if(a[is][js]==a[iis][jjs])
        cout<<"DA"<<endl;
    else cout<<"NU"<<endl;
    afisare();
    return 0;
}

Fisier

4 4
1 0 1 1
0 0 0 1
1 1 0 1
0 0 1 0
3 1
1 4

Sa se verifice daca un obiect de culoarea c1 este vecin cu un obiect de culoarea c2. Mesaj: DA/NU

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,c1,c2;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};

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

int main()
{  int ok=1,i,j,inou,jnou,k;
citire();
       for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {if(a[i][j]==c1)
                {for(k=0;k<8;k++)
                    {inou=i+dx[k];
                    jnou=j+dy[k];
                    if(a[inou][jnou]==c2)
                        ok=0;
                }
                }
            }
if(ok==0)
    cout<<"DA";
else cout<<"NU";
}

Fisier

4 5
1 2  2 2 4
5 10 2 4 4
5 5  5 4 6
9 9  9 9 2
1 6

Fotografia alb-negru a unui obiect este reprezentata sub forma unei matrici A (nxn) cu elemente din multimea {0,1}. Doua elemente sunt vecine "in 8 directii". Sa se stabileasca daca obiectul fotografiat este compus dintr-o singura bucata sau nu si sa se afiseze un mesaj corespunzator.

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

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

void fill(int i,int j)
{
    if(a[i][j]==1)
    {
        a[i][j]=2;
        fill(i-1,j);
        fill(i-1,j+1);
        fill(i,j+1);
        fill(i+1,j+1);
        fill(i+1,j);
        fill(i+1,j-1);
        fill(i,j-1);
        fill(i-1,j-1);
    }
}

int main()
{int i,j;
citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
                {fill(i,j);
                i=j=n+2;}
  
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1)
                {cout<<"Mai mult de un obiect"<<endl;
                for(i=1;i<=n;i++)
                {for(j=1;j<=n;j++)
                    cout<<setw(3)<<a[i][j];
                cout<<endl;}
                return 1;}
    cout<<"Un singur obiect";
}

Fisier

4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

Pe o matrice nxm sunt codificate obiecte prin valori nr. nat. Obiectele invecinate sunt codificate prin valori diferite. Sa se afiseze dimensiunea obiectelor maximale, coordonatele unui punct din interiorul acestora si codul lor.

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m,Dmax,nrob,D;
struct obiect{
    int i,j,cod;};
obiect x[10];

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

void fill(int i,int j,int k)
{
    if(a[i][j]==k)
    {
        a[i][j]=k*(-1);
        D++;
        fill(i-1,j,k);
        fill(i-1,j+1,k);
        fill(i,j+1,k);
        fill(i+1,j+1,k);
        fill(i+1,j,k);
        fill(i+1,j-1,k);
        fill(i,j-1,k);
        fill(i-1,j-1,k);
    }
}

int main()
{
    int i,j,k;
    citire();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i][j]>0){
                k=a[i][j]; // k=codul obiectului
                D=0;
                fill(i,j,k);
                if(D>Dmax)
                    {Dmax=D;
                    x[1].i=i;
                    x[1].j=j;
                    x[1].cod=k;
                    nrob=1;}
                else if(D==Dmax)
                {nrob++;
                x[nrob].i=i;
                x[nrob].j=j;
                x[nrob].cod=k;}
            }
           
    cout<<"Dimensiune maxim "<<Dmax<<endl;
    for(i=1;i<=nrob;i++)
        cout<<"obiectul codificat "<<x[i].cod<<" contine punctul ("<<x[i].i<<","<<x[i].j<<")"<<endl;
   
for(i=1;i<=n;i++)
{   for(j=1;j<=m;j++)
        cout<<setw(3)<<a[i][j];
cout<<endl;
}
return 0;
}

Fisier

5 7
1 0 0 5 0 7 0
0 1 0 5 0 0 0
0 1 0 5 0 0 20
0 0 5 0 0 0 0
0 0 0 1 1 1 1

Fiind data o matrice m x n, unde m,n apartin lui N si exista y elemente notate cu 1 si z elemente notate cu 0 iar y+z=m*n, aflati aria cea mai intinsa de elemente de 1.
Exemplu:
m=4, n=4
matricea:
0 1 1 0
0 1 1 0
1 0 0 0
0 0 1 1
Se va afisa: 4, adica regiunea care cuprinde elementele: (1,2),(1,3),(2,2),(2,3)

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m;
int size;
void fill(int i,int j,int k)
{
    if(a[i][j]==1)
    {
        a[i][j]=k; // fiecarei element din regiune ii corespunde numarul zonei
        size++;
       /*verificam daca elementele alaturate pot apartine aceiasi regiuni si daca nu au fost 
         inca marcate*/
        fill(i-1,j,k);
        fill(i+1,j,k);
        fill(i,j-1,k);
        fill(i,j+1,k);
    }
}

int main()
{
    int i,j;
    ifstream f("fill.in");
    f>>m>>n;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    int max=0;
    int k=1;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1){
                k++; //fiecarei regiuni ii va corespunde un numar de ordine
                size=0;//numarul de elemente dintr-o regiune este initial 0
                fill(i,j,k);
                if(max<size) max=size;//calculam maximul ariilor
            }
    cout<<max<<endl;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
            cout<<setw(3)<<a[i][j];
    cout<<endl;
    }return 0;
}

Fisier

4 4
0 1 1 1
0 1 1 1
1 1 1 1
0 0 1 1

Se oferă un lac de nxn "bălţi" care posedă sau nu obiecte plutitoare care pot susţine o broască de masă m. Broasca este paraşutată pe un astfel de obiect plutitor căruia îi vom atribui în continuare denumirea de "nufăr". Se citeşte dintr-un fişier cu denumire fortuită n, poziţia iniţială a amfibianului, un număr întreg m şi m perechi de coordonate pe care se găsesc nuferi. Să se jenereze într-o ordine fortuită toate traseele pe care le poate parcurge amfibianul pentru a ajunge la malul lacului. Pentru olimpici (se cere doar la faza naţională): Rezolvaţi aceeaşi problemă pentru masa broaştei M=m derivat de două ori în raport cu sinusul unghiului format de razele soarelui cu suprafaţa nufărului cel mai apropiat de centrul lacului.

#include<iostream>  // Rezolvare pentru non-olimpici
#include<fstream>
#include<iomanip>
using namespace std;

int L[10][10],sol[10][10],n,m,nrsol,is,js;
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};

void citire()
{int a,b,i;
ifstream f("broasca");
f>>n>>is>>js>>m;
for(i=1;i<=m;i++)
{f>>a>>b;L[a][b]=1;}
}

void afisare()
{int i,j;
nrsol++;
cout<<"Solutia nr "<<nrsol<<endl;
for(i=1;i<=n;i++)
{    for(j=1;j<=n;j++)
        cout<<setw(3)<<sol[i][j];
cout<<endl;}
cout<<endl;
}

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=n)
    if(sol[inou][jnou]==0 && L[inou][jnou]==1)
    {sol[inou][jnou]=pas;
    if(inou==1 || inou==n || jnou==1 || jnou==n)
        afisare();
    traseu(inou,jnou,pas+1);
    sol[inou][jnou]=0;
    }
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol<<" Solutii";
}

Fişier

7
4 3
10
1 2
1 4
2 3
2 5
3 4
3 5
4 1
5 2
6 1
7 2

Un turist pleaca in vacanta de iarna la munte. El descopera o suprafata dreptunghiulara de teren denivelat unde vrea sa schieze. Cunoscand cotele diferitelor portiuni din acest teren si stiind in ce portiunde se afla schiorul, sa se determine toate partiile posibile pe care acesta poate cobori, pana la iesirea din teren, La un moment dat, schiorul se poate deplasa in orice portiune de teren invecinata, avand o cota strict inferioara cotei terenului pe care se afla el in momentul respectiv. Se citesc dimensiunile terenului m si n (2<=m<=100, 2<=n<=100), cotele diferitelor portiuni ale terenului (date in ordine, pe linii) si pozitia schiorului.

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],sol[10][10],nrsol=0,is,js;
int dx[]={-1,0,1,0,-1,1,1,-1},dy[]={0,1,0,-1,1,1,-1,-1};

void citire()
{int i,j;
ifstream f("teren");
f>>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
f>>L[i][j];
f>>is>>js;
}


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

void traseu(int i, int j, int pas)
{int inou,jnou,k;
for(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
if(sol[inou][jnou]==0 && L[inou][jnou]<L[i][j])
{sol[inou][jnou]=pas;
 if(inou==1 || inou==n || jnou==1 || jnou==m)
 afisare();
 traseu(inou,jnou,pas+1);
 sol[inou][jnou]=0;}
}
}

int main()
{citire();
sol[is][js]=1;
traseu(is,js,2);
cout<<nrsol;
}

Fisier

5 5
20 10 7 5 6
22 8 20 60 18
12 10 30 120 12
24 6 60 100 15
2 4 4 5 6
3 2

8. ANFINISHID Se citeste o matrice nXm cu elemente numere naturale si o pozitie io, jo din matrice in care se afla un robot care se poate deplasa paralel cu liniile si coloanele matricii pe pozitii alturate.
Afisati toate drumurile pe care poate parcurge robotul matricea trecand prin fiecare pozitie de atatea ori cat este valoarea pozitiei respective.
Drumurile vor fi afisate ca perechi de coordonate.
Exemplu:
pentru datele de intrare
6 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 2 0 2 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 2
se afiseaza
3,2 3,3 4,3 3,3 2,3 2,4 2,5 3,5 4,5 3,5 3,6
3,2 3,3 4,3 3,3 2,3 2,4 2,5 3,5 3,6 3,5 4,5

#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
int n,m,L[10][10],px[20],py[20],nrsol=0,is,js,ii=1,ff[10][10];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

void citire()
{int i,j;
ifstream f("teren");
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
    {f>>L[i][j];
     ff[i][j]=L[i][j];}
f>>is>>js;
}

void afisare(int n)
{int i;
for(i=0;i<n-1;i++)
    cout<<px[i]<<","<<py[i]<<"  ";
nrsol++;
cout<<endl;
}

int matrice(int L[10][10])
{int i,j,ok=0;
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        if(L[i][j]>0)
            ok=1;
return ok;
}

void traseu(int i, int j)
{int inou,jnou,k;
for(k=0;k<4;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inou>=1 && inou<=n && jnou>=1 && jnou<=m)
    if(L[inou][jnou]>0)
        {L[inou][jnou]--;
         px[ii]=inou;
         py[ii]=jnou;
         ii++;
         if(matrice(L)==0)
            {afisare(ii);
             for(int jj=1;jj<=ii+1;jj++)
             {px[jj]=0;
              py[jj]=0;}
             ii=1;
             L[inou][jnou]++;
            }
         else traseu(inou,jnou);
         //L[inou][jnou]++;
        }
}
}

int main()
{citire();
px[0]=is;
py[0]=js;
traseu(is,js);
cout<<endl<<"Solutii totale "<<nrsol;
}

Fisier

6 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 1 2 0 2 1 0
0 0 1 0 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 2