Back Teorie Si Aplicatii

68 3. METODA BATRACKING

3. METODA BACKTRACKING

3.1. Descrierea generală a metodei

Deseori în practică apar probleme care implică alegerea unor soluţii optime

dintr-un spaţiu extrem de vast de soluţii posibile.

Un teoretician „pur” ar răspunde: „nici o problemă! construim toate soluţiile

posibile şi le alegem apoi pe cele optime!” Dar este realistă o astfel de abordare?

Să analizăm un caz foarte simplu: să presupunem că problema noastră implică

selectarea unei mulţimi de n elemente care trebuie să îndeplinească anumite

condiţii. Pentru fiecare element i presupunem că există pi posibilităţi de alegere.

A genera toate soluţiile posibile înseamnă de fapt a genera toate elementele

produsului cartezian {1, 2, ..., p1}x{1, 2, ..., p2}x...x{1, 2, ..., pn}. Acest

produs cartezian are p1xp2x...xpn elemente. Chiar dacă vom considera că pi=2,

pentru orice i de la 1 la n tot obţinem 2n soluţii posibile. E mult? Să evaluăm cu

aproximaţie timpul de execuţie a unui program bazat pe un astfel de algoritm,

presupunând că dispunem de un calculator care execută un miliard de operaţii pe

secundă (109 operaţii).

n Timp de execuţie

40 109 secunde

50 31 ore

100 41013 ani

E puţin probabil să putem aştepta atât!

Prin urmare trebuie să abordăm în alt mod astfel de probleme! O idee ar fi să

procedăm ca în multe situaţii din viaţa de zi cu zi. Să ne gândim la modul în care

un copil rezolvă un puzzle. Copilul nu face toate combinaţiile posibile de piese

pentru ca apoi să le compare cu modelul pe care vrea să îl obţină. El va lua mai

întâi o piesă. Va căuta apoi în mulţimea de piese rămase una care să se potrivească

la cea pe care o are, apoi încă una, ş.a.m.d. Dacă la un moment dat „se blochează”

(nu mai găseşte nici o piesă în cele rămase care să se potrivească), el nu distruge tot

ce a construit ca să o ia de la început. Va îndepărta mai întâi ultima piesă pe care a

pus-o şi va căuta o „alternativă” (o altă piesă care s-ar potrivi în locul ei). Dacă

găseşte, continuă construcţia cu noua piesă aleasă. Dacă nu găseşte, se mai întoarce

un pas şi îndepărtează şi penultima piesă pe care a pus-o, căutând apoi o altă

variantă. Procedeul continuă până când obţine modelul dorit.

3. METODA BACKTRACKING 69

Observaţi că pe parcursul construcţiei, copilul face anumite verificări (se

potriveşte piesa aici? mă poate conduce la modelul dorit?), eliminând astfel foarte

multe dintre soluţiile posibile. Cu alte cuvinte, căutarea nu este exhaustivă.

Un alt aspect semnificativ este faptul că se fac reveniri. Dacă la un moment dat

nu mai poate continua construcţia, copilul revine la pasul precedent, îndepărtează

piesa utilizată şi încearcă să o înlocuiască, dacă este posibil. Dacă nu este posibil,

face reveniri succesive, până când găseşte o piesă pe care o poate înlocui şi apoi

continuă construcţia. Acest mod de abordare se bazează pe principiul „Încerc aşa,

dacă nu merge mă întorc şi încerc o altă variantă!”

Fără să ştie, copilul din exemplu a aplicat metoda backtracking. Numele

metodei este semnificativ1 şi s-ar putea traduce prin „a o lua înapoi pe urme” sau,

cu aproximaţie, prin „căutare cu revenire”.

Să descriem acum într-un mod mai general metoda backtracking. În variantă

elementară, considerăm că soluţia problemei pe care trebuie să o rezolvăm se poate

reprezenta ca un vector x=(x0, x1, …, xn-1). Fiecare componentă xi a vectorului

poate lua valori într-o anumită mulţime Si (i=0, n-1). Produsul cartezian

S0xS1x...xSn-1 se numeşte spaţiul soluţiilor posibile.

Problemele care se rezolvă prin backtracking nu impun generarea tuturor

soluţiilor posibile (generare exhaustivă), ci doar generarea acelor soluţii care

îndeplinesc anumite condiţii, specifice problemei, denumite condiţii interne.

Soluţiile posibile care respectă condiţiile interne sunt denumite soluţii rezultat.

Unele probleme impun obţinerea unei singure soluţii rezultat şi anume cea care

îndeplineşte o anumită condiţie de optim. Aceasta este denumită soluţie optimă.

Pentru a evita generarea tuturor soluţiilor posibile, metoda backtracking atribuie

pe rând valori elementelor vectorului x. Mai exact, componenta xk primeşte o

valoare numai în cazul în care componentele x0, x1, ..., xk-1 au primit deja valori.

În acest caz, componentei xk i se atribuie pe rând acele valori posibile (valori din

mulţimea Sk) care îndeplinesc condiţiile de continuare. Condiţiile de continuare

sunt condiţii derivate din condiţiile interne, care stabilesc dacă pentru o anumită

valoare pentru xk are sau nu sens să continuăm construcţia soluţiei. Spunem că o

anumită valoare pentru xk nu îndeplineşte condiţiile interne dacă oricum am atribui

valori componentelor xk+1, ..., xn-1 nu obţinem o soluţie rezultat (soluţie care să

respecte condiţiile interne).

După atribuirea unei valori posibile care respectă condiţiile interne componentei

xk se poate continua construcţia soluţiei în mod recursiv (de data aceasta sunt

fixate k+1 poziţii).

1. În limba engleză back înseamnă „înapoi”, iar track înseamnă „urmă”.


Pentru a descrie formatul general al metodei backtracking vom utiliza o funcţie

BKT(). Considerăm că n, numărul de componente ale vectorului, şi vectorul x

sunt variabile globale.

void BKT (int k)

{//cand apelam functia BKT cu parametrul k presupunem ca

//pozitiile 0,1,…,k-1 din vectorul x sunt fixate

Element MC[]; int nc;

//tipul elementelor din MC depinde de problema concretă

if (k==n) //solutia este completa

Prelucrare_Solutie();

else //continuam generarea

{Candidat(MC, nc, k);

/*functia Candidat retine in vectorul MC cele nc elemente

din multimea Sk care respecta conditiile de continuare*/

for (int i=0; i<nc; i++)

{x[k]= MC[i]; //extrag un candidat din MC

BKT(k+1);} //apel recursiv

}

}

Din descrierea generală a metodei backtracking nu reiese explicit unde intervine

revenirea. Pentru aceasta trebuie să ne gândim la modul de realizare a recursivităţii.

La fiecare apel recursiv se memorează pe stivă valorile variabilelor locale şi

valoarea parametrului. La încheierea unui apel recursiv, se eliberează zona de

memorie alocată pe stivă şi se revine la apelul precedent.

Pentru a înţelege mai bine modul de funcţionare a acestei metode să analizăm

următoarea problemă.

Problema reginelor

Să se plaseze n regine pe o tablă de şah de dimensiune nxn astfel încât oricare

două regine să nu se atace.

Reprezentarea informaţiilor

Pentru ca două regine să nu se atace ele nu trebuie să fie situate pe aceeaşi linie,

pe aceeaşi coloană sau pe aceeaşi diagonală. Cum numărul de regine este egal cu

dimensiunea tablei de şah, deducem că pe fiecare linie trebuie plasată o regină.

Deci, pentru ca poziţia reginelor să fie complet determinată, este suficient să

reţinem pentru fiecare linie coloana în care este plasată regina. Pentru aceasta vom

utiliza un vector C, cu n componente având următoarea semnificaţie:

C[i] reprezintă coloana în care este plasată regina de pe linia i.


Condiţii interne

1. C[i]{0,1,…,n-1}, i{0,1,…,n-1}

(elementele vectorului C sunt indici de coloane)

2. C[i]C[j], ij, i,j{0,1,…,n-1}

(două regine nu pot fi plasate pe aceeaşi coloană)

3. |C[i]-C[j]||i-j|, ij, i,j{0,1,…,n}

(două regine nu pot fi plasate pe aceeaşi diagonală).

#include <iostream.h>

#include <math.h>

#include <conio.h>

int n, NrSol, C[30];

void Plaseaza_Regina(int);

int main ()

{ cout << "n= "; cin >> n;

Plaseaza_Regina(0); return 0; }

void Afisare()

{int i, j;

cout<<"Solutia nr. "<< ++NrSol<<endl;

for (i=0; i<n; i++)

{for (j=0; j<n; j++)

if (j==C[i]) cout<<" * ";

else cout<<" o ";

cout<<endl;}

cout<<endl; getch(); }

void Plaseaza_Regina(int k)

{/*cand apelam functia Plaseaza_Regina cu parametrul k am

plasat deja regine pe liniile 0,1,...,k-1 */

int i, j, ok;

if (k==n) //am obtinut o solutie

Afisare(); //prelucrarea solutiei consta in afisare

else

//trebuie sa mai plasam regine pe liniile k,k+1,...,n-1

for (i=0; i<n; i++)

//verific daca pot plasa regina de pe linia k in coloana i

{for (ok=1, j=0; j<k; j++)

if (C[j]==i || abs(C[j]-i)==(k-j)) ok=0;

/*regina s-ar gasi pe aceeasi coloana sau aceeasi diagonala

cu o regina deja plasata */

if (ok) //valoarea i respecta conditiile interne

{C[k]=i; //i este un candidat, il extrag imediat

Plaseaza_Regina(k+1);}}

}


3.3. Aplicaţii

Plata unei sume cu monede de valori date

Având la dispoziţie n săculeţi cu monede, fiecare săculeţ conţinând monede de

aceeaşi valoare, să se afişeze toate modalităţile de a plăti o sumă dată S folosind

numai monedele din săculeţi.

De exemplu, să presupunem că trebuie să achităm suma S=100 şi avem n=3

săculeţi de monede. În primul săculeţ se găsesc 6 monede cu valoarea 3, în al

doilea săculeţ se găsesc 4 monede cu valoarea 7, iar în ultimul săculeţ sunt 14

monede cu valoarea 5. Programul va afişa în fişierul de ieşire (denumit

suma.out) cele două soluţii posibile de plată astfel:

Solutia nr. 1

3 monede cu valoarea 3



Solutia nr. 2





Vom reţine într-un vector V cu n componente valorile monedelor din cei n

săculeţi, iar într-un alt vector M vom reţine multiplicităţile, adică numărul de

monede din fiecare săculeţ în parte.

Soluţiile vor fi generate într-un vector P, cu n componente având semnificaţia:

P[i] – numărul de monede din săculeţul i folosite pentru plata sumei S,

i{0,1,…,n-1}.

Condiţii interne

1. P[i]{0,1,…,M[i]}, i{0,1,…,n-1}

(din săculeţul i se pot folosi cel mult M[i] monede);

2. P[0]V[0]+P[1]V[1]+…+P[n-1]V[n-1]=S

(valoarea totală a monedelor selectate trebuie să fie egală cu suma S).

Pentru a genera soluţiile vom utiliza o funcţie recursivă Plata(). Când apelăm

funcţia Plata(k), am stabilit numărul de monede din săculeţii 0, 1, 2, ..., k-1.

Pentru a completa soluţia, ocupăm mai întâi poziţia k din vectorul P şi apoi apelăm

recursiv funcţia Plata(k+1). Pe poziţia k poate fi plasat orice număr natural

care reprezintă numărul de monede selectate din sacul k (deci acest număr trebuie

să fie M[k]) şi în plus valoarea totală a monedelor selectate să nu depăşească S.


#include <fstream.h>

#define NrMaxMonede 20

unsigned V[NrMaxMonede], M[NrMaxMonede], P[NrMaxMonede];

unsigned n, S, Sum, NrSol;

ofstream fout("suma.out");

void Citire()

{//citesc datele de intrare din fisierul suma.in

ifstream fin("suma.in");

fin>>n>>S;

for (int i=0; i<n; i++) fin>>V[i]>>M[i];

fin.close();}

void Afisare()

{//afisez o solutie in fisierul de iesire

fout<< "Solutia nr. "<<++NrSol<<endl;

for (int i=0; i<n; i++)

if (P[i])

fout<<P[i]<<" monede cu valoarea "<<V[i]<<endl;}

void Plata(int k)

{/* cand apelam Plata(k) am selectat deja monede din

saculetii 0,1,...,k-1 */

if (k==n) //am selectat monede de toate tipurile

if (Sum==S) //valoarea monedelor selectate e egala cu S

Afisare();

else;

else //mai selectam monede din saculetii k,k+1,...,n-1

for (int j=0; j<=M[k] && Sum+j*V[k]<=S; j++)

{P[k]=j; //selectez j monede din saculetul k

Sum+=j*V[k];

/*adaug valoarea monedelor selectate din saculetul k

la valoarea totala a monedelor selectate memorata in Sum */

Plata(k+1); //apel recursiv

Sum-=j * V[k];}

//restaurez dupa apel valoarea variabilei globale Sum

}

int main ()

{Citire();

Plata(0);

fout.close(); return 0;}

Observaţi că şi în acest program am utilizat tehnica variabilei globale: pentru a

nu calcula la fiecare pas valoarea totală a monedelor deja selectate, am reţinut

această valoare în variabila globală Sum. De fiecare dată când selectăm monede

dintr-un săculeţ, adăugăm valoarea lor la Sum, apoi apelăm recursiv funcţia Plata


care selectează în continuare monede din ceilalţi săculeţi pentru plata sumei. Când

revenim din apelul recursiv, trebuie să restaurăm valoarea variabilei globale Sum

(deci trebuie să scădem din Sum valoarea monedelor selectate la pasul precedent

din săculeţul k, pentru a putea adăuga ulterior, dacă este cazul, valoarea

corespunzătoare monedelor selectate din săculeţul k la pasul următor).

Observaţi de asemenea că am optimizat programul: dacă la un moment dat

valoarea monedelor deja selectate depăşeşte suma S care trebuie plătită nu

continuăm generarea.

Generare şir

Se citesc de la tastatură numerele naturale n şi lg (0<n, lg10). Să se afişeze

toate şirurile de lg numere strict pozitive, şiruri cu proprietatea că încep şi se

termină cu n, iar între două elemente consecutive ale şirului diferenţa este exact 1.

Dacă nu există nici o soluţie, se va afişa un mesaj. De exemplu, pentru n=2 şi

lg=5, se vor afişa soluţiile (nu neapărat în această ordine):

2 3 4 3 2 ; 2 3 2 3 2 ; 2 3 2 1 2 ; 2 1 2 3 2 ; 2 1 2 1 2. Simulare bacalaureat 2001

Soluţie

Vom construi soluţiile într-un vector s cu lg componente. În funcţia main()

vom iniţializa prima componentă a vectorului cu n (s[0]=n), pentru a ne asigura

că şirul începe cu n.

Pentru a construi toate şirurile care încep cu n şi respectă proprietăţile din enunţ

vom utiliza o funcţie recursivă Gen(). Când apelăm funcţia Gen(k), poziţiile 0,

1, ..., k-1 din vectorul s sunt deja ocupate şi trebuie să plasăm elemente pe

poziţiile k, k+1, ..., lg-1. Vom ocupa mai întâi poziţia k, apoi vom apela recursiv

funcţia de generare pentru a construi şirul în continuare (Gen(k+1)).

Pentru a ne asigura că diferenţa dintre oricare două elemente consecutive din şir

este exact 1, pe poziţia k pot fi plasate cel mult două valori: s[k-1]-1 (doar dacă

s[k-1]>1, pentru că în şir pot fi plasate valori strict pozitive) sau s[k-1]+1.

Atunci când vectorul s este complet, vom afişa soluţia obţinută, testând în

prealabil că pe ultima poziţie în vector se află valoarea n (s[lg-1]==n).


#define NMax 11

int s[NMax];

int n, lg;

long nrsol;

ofstream fout("sir.out");


void Afisare();

void Gen(int k)

//cand apelam Gen(k), am fixat in sir k valori

{ if (k==lg) //sirul este complet

Afisare();

else

{if (s[k-1]>1)

{s[k]=s[k-1]-1;

Gen(k+1); }

s[k]=s[k-1]+1;

Gen(k+1);

}

}

int main()

{

cout<<"n, lg="; cin>>n>>lg;

s[0]=n;

Gen(1);

if (!nrsol) fout<<"Nu exista solutii\n";

fout.close();

return 0;

}

void Afisare()

{int i;

if (s[lg-1]==n)

{nrsol++;

for (i=0; i<lg; i++) fout<<s[i]<<' ';

fout<<endl; }

}

Observăm că algoritmul precedent generează şiruri care nu se termină

obligatoriu cu n, iar noi testăm această condiţie abia la final. Dacă valoarea s[k]

va creşte/scădea prea mult, nu mai există şanse ca pe ultima poziţie în vector să

obţinem valoarea n, oricum am genera valorile s[k+1], s[k+2], ..., s[lg-1].

Pentru a determina cea mai mică valoare care poate fi plasată pe poziţia k,

presupunem că de la poziţia k+1 până la poziţia lg-1 valorile vor fi în ordine

strict crescătoare.

Valoare minimă ? n-2 n-1 n

Poziţie ... k ... lg-3 lg-2 lg-1

Observăm că suma dintre valoarea minimă şi poziţie este constantă (n+lg-1).

Deducem astfel că cea mai mică valoare care poate fi plasată pe poziţia k este n-

lg+1+k (cu condiţia ca n-lg+1+k>0)


Pentru a determina cea mai mare valoare care poate fi plasată pe poziţia k,

presupunem că de la poziţia k+1 până la poziţia lg-1 valorile vor fi în ordine

strict descrescătoare:

Valoare maximă ? n+2 n+1 n

Poziţie ... k ... lg-3 lg-2 lg-1

Observăm că suma dintre valoarea maximă şi poziţie este constantă (n+lg-1).

Deducem că valoarea maximă care poate fi plasată pe poziţia k este n+lg-1-k.

Funcţia de generare optimizată este:

void Gen(int k)


{ if (k==lg) //sirul este complet

Afisare();

else

{if (s[k-1]>1 && s[k-1]-1>=n-lg+1+k)

{s[k]=s[k-1]-1;

Gen(k+1); }

if (s[k-1]+1<=n+lg-1-k)

{s[k]=s[k-1]+1;

Gen(k+1);}

}

}

Exerciţiu

Modificaţi programul precedent astfel încât să genereze toate şirurile de

lungime lg, care încep cu n şi se termină cu n, diferenţa între oricare două valori

consecutive fiind cel mult D.

Generare numere

Se citesc de la tastatură numerele naturale n şi k (0<n10000 şi 0<lg<10)

reprezentate în baza 10. Să se afişeze în ordine crescătoare toate numerele naturale

de lg cifre cu proprietatea că sunt formate numai cu cifre ale numărului n.

De exemplu, pentru n=216 şi lg=2, se vor afişa numerele: 11, 12, 16, 21,

22, 26, 61, 62, 66. Bacalaureat special 2001

Soluţie

În primul rând vom construi vectorul caracteristic al mulţimii cifrelor numărului

n. Soluţiile vor fi generate în variabila x, de tip unsigned long (pentru că

numărul de cifre este < 10. Pentru a genera toate soluţiile vom utiliza funcţia

recursivă Gen(). Când apelăm Gen(k) în numărul x au fost adăugate k cifre;


adăugăm la sfârşitul numărului x, pe rând, fiecare dintre cifrele numărului n, apoi

vom apelăm recursiv Gen(k+1) pentru a completa numărul soluţie.


int c[10];

int n, lg;

unsigned long x;

ofstream fout("sir.out");

void Determina_Cifre(int);

void Gen(int k)


{int i;

if (k==lg) //sirul este complet

fout<<x<<endl;

else

for (i=0; i<10; i++)

if (c[i]) //cifra i apare in n?

{x=x*10+i; //adaug la sfarsitul lui x cifra i

Gen(k+1); //generez in continuare

x/=10; //sterg cifra adaugata

}

}

int main()

{

cout<<"n, lg="; cin>>n>>lg;

Determina_Cifre(n);

Gen(0);

fout.close();

return 0;

}

void Determina_Cifre(int x)

{

do

{c[x%10]=1;

x/=10; }

while (x);

}

Exerciţiu

Modificaţi programul precedent astfel încât să genereze toate numerele formate

din lg cifre ale numărului n care au cifrele în ordine crescătoare. De exemplu,

pentru n=216 şi lg=2, se vor afişa numerele: 11, 12, 16, 22, 26, 66.


Comis-voiajor

Un comis voiajor plecă din oraşul în care locuieşte (să-l notăm 1) să prezinte

produsele unei firme în toate cele n oraşe din regiunea sa. El are la dispoziţie harta

regiunii, pe care sunt marcate legăturile directe dintre oraşe şi distanţele dintre

acestea. Scrieţi un program care să determine un traseu cât mai scurt, astfel încât

comisul voiajor să viziteze toate oraşele din regiune, să nu treacă de mai multe ori

prin acelaşi oraş şi să se întoarcă în oraşul în care locuieşte!

De exemplu, să presupunem că există n=5 oraşe, numerotate de la 1 la 5. Să

presupunem că harta regiunii indică următoarele legături directe:

Pentru acest exemplu, programul va afişa: Traseul cel mai scurt are lungimea 815.00

Traseul este 1,3,4,2,5,1


Vom reprezenta harta regiunii printr-o matrice pătratică A, cu nxn componente

având semnificaţia: A[i][j]=0 dacă între oraşele i şi j nu există legătură

directă, respectiv distanţa dintre oraşele i şi j dacă există legătură directă.

Traseul, mai exact ordinea în care comisul voiajor vizitează cele n oraşe, îl vom

reţine într-un vector T, cu n componente.

Pentru a nu trece de mai multe ori prin acelaşi oraş, vom mai utiliza un vector v,

cu n componente, în care pentru fiecare oraş vom reţine dacă a fost sau nu vizitat:

v[i]=1 dacă oraşul i a fost vizitat şi 0 în caz contrar.

Când obţinem un traseu soluţie nu îl afişam, ci îl comparăm cu traseul de

lungime minimă obţinut până la momentul respectiv. Prin urmare, vom utiliza

TMin, un vector cu n componente, în care reţinem un traseu de lungime minimă şi

o variabilă globală LgMin în care reţinem lungimea acestui traseu.

Pentru a optimiza funcţia de generare a traseelor, vom utiliza o variabilă globală

Lg în care reţinem lungimea traseului curent. Astfel nu va mai fi nevoie să

calculăm la fiecare pas lungimea traseului curent: când ne deplasăm în alt oraş

adunăm distanţa până la oraşul respectiv la Lg. Când eliminăm un oraş de pe

traseu, scădem distanţa până la acesta din Lg. Dacă la un moment dat Lg>LgMin,

2

1 3

4 5

100

300

500

140 110

125

150


nu mai continuăm generarea acestui traseu, deoarece lungimea lui a depăşit deja

lungimea celui mai scurt traseu obţinut până la momentul respectiv.

Condiţii interne

1. T[i]{1,2,…,n} i{1,2,…,n} (traseul conţine cele n oraşe)

2. T[1]=1 (comis voiajorul pleacă din oraşul 1)

3. A[T[i]][T[i+1]]=1 i{1,2,…,n-1}

(între două oraşe vizitate succesiv trebuie să existe legătură directă)

4. T[i]T[j] ij, i,j{1,2,…,n}

(comisul voiajor nu trece de mai multe ori prin acelaşi oraş)

5. A[1][T[n]]=1

(trebuie să existe legătură directă între oraşul de plecare şi ultimul oraş vizitat). #include <iomanip.h>


#define NMaxOrase 20

float A[NMaxOrase][NMaxOrase];

int n;

int T[NMaxOrase], TMin[NMaxOrase], v[NMaxOrase];

float Lg, LgMin, Inf;

void Citire()

{ifstream f("comis.in");

int i, j;

float d;

f>>n;

while (!f.eof())

/* de pe fiecare linie citesc doua orase intre care exista

legatura directa, precum si distanta dintre ele */

{f>>i>>j>>d;

A[i][j]=A[j][i]=d; }

f.close(); }

float Infinit() //intoarce un numar suficient de mare

{float s=0;

for (int i=1; i<=n; i++)

for (int j=1; j<=n; j++) s+=A[i][j];

return s+1; }

void Afisare()

{ if (LgMin==Inf) cout<<"Nu exista solutii\n";

else

{cout<<"Traseul cel mai scurt are lungimea ";

cout<< setprecision(10) << LgMin << endl;

cout<<"Traseul este ";

for (int i=1; i<=n; i++) cout<<TMin[i]<<',';

cout<<TMin[1]<<endl; }

}


void ConstrTraseu(int k)

/*cand apelam ConstrTraseu(k) sunt fixate pe traseu orasele

T[1], T[2], ..., T[k-1] */

{ if (k-1==n) //traseul este complet

if (A[1][T[n]]) //poate reveni in orasul 1

if (Lg+A[1][T[n]]<LgMin)

{ //am obtinut un traseu mai scurt

for (int i=1; i<=n; i++) TMin[i]=T[i];

LgMin=Lg+A[1][T[n]]; }

else;

else;

else //construiesc in continuare traseul


//verific daca se poate deplasa in orasul i

if (A[i][T[k-1]] && !v[i])

{T[k]=i; v[i]=1; Lg+=A[i][T[k-1]];

if (Lg<=LgMin) ConstrTraseu(k+1);

v[i]=0; Lg-=A[i][T[k-1]];}

}

int main()

{ Citire();

T[1]=v[1]=1; LgMin=Inf=Infinit();

ConstrTraseu(2);

Afisare();

return 0;

}

Medii

Se ştie că media la o materie unde se dă teză se calculează după formula

următoare, unde Nt reprezintă nota la teză, iar Mn media notelor la oral. Se ştie, de

asemenea, că un elev poate avea la oral minim 3 şi maxim 10 note.

Cerinţă

În aceste condiţii, dacă doi elevi au aceeaşi medie şi aceeaşi notă la teză să se

determine toate combinaţiile distincte de note pe care le pot avea cei doi elevi.

Date de intrare

Fişierul de intrare medii.in conţine pe prima linie, separate printr-un spaţiu,

media şi nota la teză.

4

*3 MnNtmedia


Date de ieşire

Dacă există soluţie, fişierul de ieşire medii.out conţine pe fiecare linie câte o

combinaţie de note, notele fiind separate prin câte un spaţiu. Dacă nu există soluţie,

în fişierul de ieşire se va scrie mesajul NU.

Restricţii

1 Nt 10

1 media 10

Media se dă în fişierul de intrare cu 3 zecimale exacte.

Exemplu

medii.in medii.out Comentarii 5.625 3

...

2 3 4 7 7 9 10 10

...

5 6 6 9

...

Există mai multe combinaţii de note

care furnizează aceeaşi medie, două

dintre acestea fiind cele indicate. Mn=(5+6+6+9)/4=26/4=6.50

Media_calculată=(3+3*6.50)/4= 22.50/4 = 5.625

Olimpiada municipală de Informatică, Iaşi 2003

Soluţie

Având în vedere că se cer toate combinaţiile de note care furnizează aceeaşi medie,

rezultă că problema se rezolvă prin tehnica de programare backtracking.


Notele la oral care participă la calcularea mediei se reţin în ordine crescătoare

într-un tablou n. Deoarece cea mai mică notă este nota 1, şi notele se reţin în

ordine crescătoare, vom iniţializa prima valoare a acestui tablou (n[0]) cu 1,

urmând ca notele care participă efectiv la calcularea mediei să fie reţinute în

continuare (n[1], ..., n[10]).

Condiţii interne

1. n[i]{1, ..., 10}, i{1, ..., 10}

2. n[0]=1

3. n[i]≤n[i+1], i{0, ..., 9}

Se generează în vectorul n toate combinaţiile de minim trei şi maxim zece note.

După fiecare notă adăugată se calculează media şi, în cazul în care aceasta coincide

cu media dată, se afişează soluţia.


#include <stdio.h>

FILE *f, *g;

float media, nt;

int n[12], GASIT;

void afiseaza(int k)

{ int i;

for (i=1; i<=k; i++)

fprintf(g, "%d ", n[i]);

fprintf(g, "\n");

GASIT=1; //am gasit solutie

}

float media_calculata(int k)

{ int i;

float s, mn, mc;

if (k>2) //are rost sa calculez doar daca am minim 3 note

{ s=0;

for (i=1; i<=k; i++) s+=n[i]; //suma notelor

mn=s/k; //media notelor

mc=(nt+3.0*mn)/4.0; //media calculata

return mc;

}

return 0;

}

void calculeaza(int k)

{ int i;

if (k<11) //daca nu am pus toate notele (maxim 10 aici)

{

for (i=n[k-1]; i<=10; i++)//pun toate notele posibile

{

n[k]=i; //pun nota i

if (media_calculata(k)==media)

//daca media corespunde

afiseaza(k); //afiseaza

calculeaza(k+1); //treci la nota urmatoare

n[k]=0; //anuleaza ultima nota

}

}

}

int main()

{ f=fopen("medii.in", "r");

g=fopen("medii.out", "w+");

fscanf(f, "%f %f", &media, &nt);

GASIT=0; //nu am gasit nici o solutie

n[0]=1; //ca sa plec de la nota 1


calculeaza(1); //pune notele incepand cu prima

if (!GASIT) fprintf(g, "NU\n");

fclose(f); fclose(g);

return 0;

}

Domino

Să se afişeze cel mai lung lanţ ce se poate construi din cele n piese ale unui joc

de domino, ştiind că fiecare piesă are înscrise în ordine două numere din mulţimea

{1,2,3,4,5,6}, iar două piese se pot plasa pe lanţ în poziţii consecutive dacă

şi numai dacă primul număr înscris pe cea de a doua piesă coincide cu cel de al

doilea număr înscris pe prima piesă.

De exemplu, pentru n=6 piese, care au înscrise numerele 4 2, 1 2, 4 4,

1 3, 2 5, 6 5 programul va afişa: Cel mai lung lant este format din piesele 3 1 2 4


Vom reprezenta un joc de domino reţinând într-un vector J valorile înscrise pe

fiecare piesă din joc.

O soluţie va fi reprezentată într-un vector L, în care reţinem în ordine indicii

pieselor din joc ce formează un lanţ.

Soluţia optimă (cel mai lung lanţ care se poate construi cu piese din joc) o vom

reţine într-un vector LMax, în care vom memora, în ordine, indicii pieselor care

constituie un cel mai lung lanţ. Când obţinem în L o soluţie maximală (care nu mai

poate fi mărită, un lanţ la care nu mai putem „lipi” nici o piesă) o vom compara cu

lanţul cel mai lung obţinut până la momentul respectiv şi, dacă lanţul din L este

mai lung îl vom reţine în LMax.

Deoarece în lanţ nu putem utiliza o aceeaşi piesă de mai multe ori, vom utiliza

un vector Uz, cu n componente (Uz[i]=1 dacă piesa cu indicele i a fost folosită

în lanţul L şi 0, în caz contrar).

Condiţii interne

1. L[i]{1,2,…,n} i{1,2,…,n}

(lanţul este format din indici ai pieselor din joc);

2. L[i]L[j] ij, i,j{1,2,…,n}

(nu se poate folosi o piesă de mai multe ori);

3. J[L[i]].ultim = J[L[i+1]].prim, i{1,2,…,n-1}

(pentru oricare două piese consecutive pe lanţ, a doua valoare înscrisă pe prima

dintre piese coincide cu cea de a doua valoare înscrisă pe piesa următoare).



#define NrMaxDomino 100

struct Piesa { int prim, ultim; } J[NrMaxDomino];

//pentru fiecare piesa retin cele doua numere inscrise

int n, LgMax;

int L[NrMaxDomino], LMax[NrMaxDomino], Uz[NrMaxDomino];

void Citire()

{ifstream fin("domino.in");

fin>>n;

for (int i=1; i<=n; i++) fin>>J[i].prim>>J[i].ultim;

fin.close(); }

void Afisare()

{cout<<"Cel mai lung lant este format din piesele ";

for (int i=1; i<=LgMax; i++)

cout<<LMax[i]<<' ';}

void ConstrLant(int k)

//lantul contine k-1 piese de domino

{int Se_Poate=0; //incerc sa prelungesc lantul


if (!Uz[i]) //nu am mai utilizat piesa i

{if (J[i].ultim == J[L[k-1]].ultim)

{ //intoarce piesa

int aux=J[i].prim;

J[i].prim=J[i].ultim; J[i].ultim=aux;}

if (J[i].prim == J[L[k-1]].ultim)

{ //piesa i "se lipeste"

L[k]=i; Uz[i]=1; Se_Poate=1;

ConstrLant(k+1);

Uz[i]=0;}

}

if (!Se_Poate) //am obtinut o solutie maximala

if (k-1 > LgMax) //compar lantul curent cu cel maxim

{LgMax=k-1;

for (i=1; i<=LgMax; i++) LMax[i]=L[i];}

}

int main()

{ Citire();


{ //pot incepe lantul cu orice piesa

L[1]=i; Uz[i]=1;

ConstrLant(2);

Uz[i]=0;}

Afisare();

return 0; }


Scara

Ion şi-a construit o vilă pe frumosul vârf al unui munte. Acum proiectează o

scară specială, pe care va urca de la şosea până la vilă. Diferenţa de nivel dintre

şosea şi vilă este H (deci aceasta trebuie să fie înălţimea totală a scării). Scara va

avea N trepte, toate de aceeaşi lăţime, dar de înălţimi distincte două câte două.

Ion a sesizat că efortul pe care îl depune pentru a urca o treaptă este egal cu

înălţimea treptei. Dar dacă el urcă x trepte deodată, efortul depus este egal cu

media aritmetică a înălţimilor acestor x trepte pe care le urcă deodată + un efort de

valoare constantă p (necesar pentru a-şi lua avânt).

Fiind un tip atletic, Ion poate urca mai multe trepte deodată, dar suma

înălţimilor treptelor urcate deodată nu trebuie să depăşească o valoare maximă M.

Cerinţă

Scrieţi un program care să determine efortul minim necesar pentru a urca pe o

scară construită conform restricţiilor problemei, precum şi o modalitate de a

construi scara care va fi urcată cu efort minim.

Date de intrare

Fişierul de intrare scara.in va conţine pe prima linie 4 numere naturale

separate prin câte un spaţiu H N M p (cu semnificaţia din enunţ).

Date de ieşire

Fişierul de ieşire scara.out va conţine

– pe prima linie va fi scris efortul minim necesar (cu 2 zecimale cu rotunjire);

– pe cea de a doua linie vor fi scrise N numere naturale nenule care reprezintă

înălţimile celor N trepte ale scării (în ordinea de la şosea către vilă), separate

prin câte un spaţiu.

Restricţii şi precizări

0 < H 75

0 < N 8

0 < M < 14

0 p 10

Pentru datele de test, problema are întotdeauna soluţie.

Dacă există mai multe soluţii (modalităţi de a construi scara astfel încât să

obţineţi efortul minim dorit), veţi afişa prima soluţie în ordine lexicografică.

Spunem că vectorul x=(x1, x2, ..., xk) precedă în ordine lexicografică vectorul

y=(y1, y2, ..., yk) dacă există i1 astfel încât xj=yj, pentru orice j<i şi

xi<yi.


Dacă a doua zecimală a efortului minim este 0, sau chiar ambele zecimale sunt

0 nu este necesar să le afişaţi. Deci în exemplu s-ar fi putut scrie efortul minim

9 sau 9.0.

Exemplu

scara.in scara.out

10 4 5 2 9.00

1 4 2 3

Olimpiada Judeţeană de Informatică, 2005

Soluţie


1. Vectorul în care generăm soluţiile: sol, cu n componente, cu semnificaţia

sol[i]=înălţimea treptei i

2. Soluţia care necesită efort minim o vom reţine în vectorul solmin

3. Pentru a verifica dacă toate înălţimile sunt distincte vom construi vectorul uz cu

M componente, vectorul caracteristic al înălţimilor (nu putem folosi înălţimi mai

mari decât M):

uz[i]=1, dacă înălţimea i a fost utilizată şi 0 în caz contrar

4. htot=suma înălţimilor treptelor până la un moment dat

5. efmin=efortul consumat pentru solmin

6. Pentru a calcula efortul minim necesar la fiecare pas, vom utiliza un vector ef

cu n componente, cu semnificaţia:

ef[i]=efortul minim necesar pentru a urca primele i trepte din soluţia

memorată în vectorul sol

Condiţii interne

1. sol[i] {1, 2, ..., M}, i{1, 2, ..., N}

2. sol[i] sol[j], ij i, j{1, 2, ..., N}

3. sol[1]+s[2]+...+sol[N]=H

Treptele 1, 2, ..., i se pot urca cu efort minim astfel:

– urcăm cu efort minim treptele 1, 2, ..., i-1 şi apoi urcăm separat treapta i

(efortul necesar în acest caz este ef[i-1]+sol[i]);

– urcăm cu efort minim treptele 1, 2, ..., j, apoi urcăm deodată treptele j+1,

j+2, ..., i, dacă este posibil, adică dacă suma înălţimilor acestor trepte nu

depăşeşte M (sol[j+1]+sol[j+2]+...+sol[i])M); efortul depus

este ef[j]+p+(sol[j+1]+sol[j+2]+...+sol[i])/(i-j). Treapta


j poate fi aleasă în toate modurile posibile (j=i-2, i-3, ...), varianta

convenabilă fiind cea care minimizează efortul depus.

Deducem din acest raţionament că efortul minim necesar pentru a urca treptele

1, 2, ..., i se calculează astfel: ef[i]=min {ef[i-1]+sol[i],

min {ef[j]+p+(sol[j+1]+sol[j+2]+...+sol[i])/(i-j),

j=i-2,i-3... dacă (sol[j+1]+sol[j+2]+...+sol[i])M}


#include <iomanip.h>

#define InFile "scara.in"

#define OutFile "scara.out"

#define NMax 101

#define HMax 101

int sol[NMax], solmin[NMax], uz[HMax], htot;

double ef[NMax], efmin;

//ef[i]=efortul minim cu care urc primele i trepte din sol

int N, H, p, M;

void Citire();

void Gen(int);

void Afisare();

double efort ();

int main()

{Citire();

efmin=(double)H*N+1;

Gen(1);

Afisare();

return 0;

}

void Citire()

{ifstream fin(InFile);

fin>>H>>N>>M>>p;

fin.close();

}

void Afisare()

{int i;

ofstream fout(OutFile);

fout<<setprecision(2)<<efmin<<endl;

for (i=1; i<N; i++)

fout<<solmin[i]<<' ';

fout<<solmin[N]<<endl;

fout.close();

}


double efort()

{int k, j;

double x, sum;

for (k=1; k<=N; k++)

{x=sol[k]+ef[k-1];

/* urc cu efort minim primele k-1 trepte si apoi urc

treapta k de inaltime i */

sum=sol[k];

for (j=2; k-j>=0; j++)

{/* urc deodata j trepte k, k-1, ..., k-j+1, daca

suma inaltimilor lor este <=M;

in sum calculez suma inaltimilor */

sum+=sol[k-j+1];

if (sum>M) break;

if (sum/j+p+ef[k-j]<x)

x=sum/j+ef[k-j]+p;

}

ef[k]=x;

}

return ef[N];

}

void Gen(int k)

{

int i;

double x;

if (k==N+1)

{

if (htot==H)

{x=efort();

if (x<efmin && efmin-x>0.001)

{efmin=x;

for (i=1; i<=N; i++) solmin[i]=sol[i]; }

}

}

else

for (i=1; i<=H && htot+i<=H && i<=M; i++)

if (!uz[i])

{

/* care ar fi efortul minim daca as pune

inaltimea treptei k=i? */

sol[k]=i; htot+=i; uz[i]=1;

Gen(k+1);

uz[i]=0; htot-=i;

}

}


Staţie

În laboratoarele unei staţii spaţiale există un simulator centrifugal care conţine C

camere, numerotate de la 1 la C. Într-o cameră pot să încapă 0, 1 sau 2 persoane.

Coeficientul de dezechilibrare a unui simulator se calculează astfel:

C

Cdez = |MCi - MA|

i=1

unde MCi este masa camerei i (calculată prin însumarea maselor persoanelor din

camera respectivă), iar MA este masa medie a camerelor (calculată prin însumarea

maselor tuturor persoanelor din camere, şi împărţirea sumei la numărul de camere).

La un experiment de simulare participă S persoane, numerotate de la 1 la S.

Cerinţă

Scrieţi un program care să determine coeficientul de dezechilibrare minim ce se

poate obţine prin repartizarea celor S persoane în camerele simulatorului.

Date de intrare

Fişierul de intrare statie.in conţine:

statie.in Semnificaţie

C S

M1 M2 ... MS C – numărul de camere dintr-un simulator

S – numărul de persoane

Mi – masa persoanei i

Date de ieşire

Fişierul de ieşire statie.out va conţine

statie.out Semnificaţie Cdez Cdez reprezintă coeficientul de dezechilibrare minim

al simulatorului

Restricţii

1 C 5

1 S 2C

1 Mi 1000, i=1, 2, ..., S

Coeficientul de dezechilibrare Cdez va fi afişat cu 3 zecimale.

Exemplul 1

statie.in statie.out Explicaţie 2 3

6 3 8

1.000 O soluţie este: persoanele 1 şi 2 sunt plasate în camera 1;

persoana 3 este plasată în camera 2.


Coeficientul de dezechilibrare este 1.000

Exemplul 2

statie.in statie.out Explicaţie 5 9

1 2 3 5 7 11 13 17 19

11.600 O soluţie este: persoanele 1 şi 8 sunt

plasate în camera 1; persoanele 2 şi 7

sunt plasate în camera 2; persoanele 3 şi

6 sunt plasate în camera 3; persoanele 4

şi 5 sunt plasate în camera 4; persoana 9

este plasată în camera 5.

Coeficientul de dezechilibrare este 11.600

.campion, 2004

Soluţie

Deoarece se cere determinarea unei repartizări optime a celor S persoane în

camere şi deoarece dimensiunile datelor nu sunt mari, vom aplica o metodă de tip

backtracking, încercând să repartizăm persoanele în camerele care mai au locuri

disponibile. O cameră este caracterizată de numărul de persoane repartizate la un

moment dat în cameră şi greutăţile persoanelor respective. În momentul în care

toate cele S persoane au fost repartizate în camere se calculează coeficientul de

dezechilibrare a staţiei şi, în cazul în care a fost determinat un coeficient mai bun, îl

reţinem.

#include <stdio.h>

#define Infinit 99999

typedef struct //structura unei camere

{

long nr, //numarul de persoane

pers[2]; //cele (maxim) 2 persoane (greutatile)

} camera;

long pers[10];

camera cam[5], best_cam[5];

int nr_cam, nr_pers;

long best_Cdez=Infinit, medie;

long abs(long x)

{ if (x<0) return -x;

return x; }

long calc_Cdez(void) //calculeaza coef de dezechilibru

{long Cdez=0;

int i,j;

for (i=0; i<nr_cam; i++)

Cdez+=abs((nr_cam*(cam[i].pers[0]+cam[i].pers[1]))-medie);

return(Cdez);


}

void citire(void)

{ int i;

FILE *inp=fopen("statie.in","r");

fscanf(inp, "%d %d", &nr_cam, &nr_pers);

medie = 0;

for (i=0; i<5; i++) //initializeaza cu 0 toate camerele

{ cam[i].nr=0; //numarul de persoane

cam[i].pers[0]=0; //persoana 1

cam[i].pers[1]=0; //persoana 2

}

for (i=0; i<nr_pers; i++) //greutatile persoanelor

{fscanf(inp, "%d ", &(pers[i]));

medie+=pers[i]; //se calculeaza si suma greutatilor

}

fclose(inp); }

void calcul(int k)

{ long temp;

int i,j;

if (k==nr_pers) //daca le-am repartizat pe toate

{

temp=calc_Cdez(); //calculam coef de dezechilibru

if (temp<best_Cdez) //daca e mai bun

best_Cdez=temp; //il retinem

}

else //nu i-am repartizat pe toti

for (j=0; j<nr_cam; j++)//parcurg toate camerele si

if (cam[j].nr<2) //daca in camera j mai e loc

{

cam[j].pers[cam[j].nr]=pers[k];//pun pers k aici

cam[j].nr++; //numar inca o persoana

calcul(k+1); //trec la persoana urmatoare

cam[j].nr--; //revin scad numarul de persoane

cam[j].pers[cam[j].nr]=0;//greutatea la loc pe 0

}

}

void afisare(void)

{FILE *g;

g=fopen("statie.out","w");

fprintf(g,"%5.3f\n",((float)(best_Cdez))/((float)nr_cam));

fclose(g); }

int main(void)

{ citire();

calcul(0);

afisare();


return 0; }

3.4. Bactracking în plan

În variantă elementară aplicam metoda backtracking pentru rezolvarea

problemelor în care soluţia era reprezentată ca vector. Putem generaliza ideea

căutării cu revenire şi pentru probleme în care căutarea se face „în plan”. Pentru

noi planul va fi reprezentat ca un tablou bidimensional.

Pentru a intui modul de funcţionare a metodei backtracking în plan să ne

imaginăm explorarea unei peşteri. Speologul porneşte de la intrarea în peşteră şi

trebuie să exploreze în mod sistematic toate culoarele peşterii. Ce înseamnă „în

mod sistematic”? În primul rând îşi stabileşte o ordine pentru toate direcţiile

posibile de mişcare (de exemplu, N, NE, E, SE, S, SV, V, NV) şi întotdeauna când

se găseşte într-un punct din care are mai multe culoare de explorat, alege direcţiile

de deplasare în ordinea prestabilită. În al doilea rând, speologul va plasa marcaje

pe culoarele pe care le-a explorat, pentru ca nu cumva să se rătăcească şi să

parcurgă de mai multe ori acelaşi culoar (ceea ce ar conduce la determinarea

eronată a lungimii peşterii).

În ce constă explorarea? Speologul explorează un culoar până când întâlneşte o

intersecţie sau până când culoarul se înfundă. Dacă a ajuns la o intersecţie,

explorează succesiv toate culoarele care pornesc din intersecţia respectivă, în

ordinea prestabilită a direcţiilor. Când un culoar se înfundă, revine la intersecţia

precedentă şi alege un alt culoar, de pe următoarea direcţie (dacă există; dacă nu

există, revine la intersecţia precedentă ş.a.m.d.).

Să descriem într-o formă mai generală această metodă.

Vom nota prin NrDirectii o constantă care reprezintă numărul de direcţii de

deplasare, iar dx, respectiv dy sunt doi vectori constanţi care reprezintă deplasările

relative pe direcţia Ox, respectiv pe direcţia Oy, urmând în ordine cele

NrDirectii de deplasare.

void Bkt_Plan(int x, int y)

//x, y reprezinta coordonatele pozitiei curente

{

Explorare(x,y); //exploram pozitia curenta

if (EFinal(x,y)) //pozitia x,y este un punct final

Prelucrare_Solutie();

else //continuam cautarea

for (i=0; i<NrDirectii; i++)

//ma deplasez succesiv pe directiile posibile de miscare

if (Nevizitat(x+dx[i], y+dy[i]))

//nu am mai trecut prin aceasta pozitie

Bkt_Plan(x+dx[i], y+dy[i]);

}


Labirint

Într-un labirint, reprezentat ca o matrice L, cu n linii şi m coloane, cu

componente 0 sau 1, (1 semnificând perete, 0 culoar) se găseşte o bucată de

brânză pe poziţia (xb, yb) şi un şoricel pe poziţia (xs, ys). Afişaţi toate

posibilităţile şoricelului de a ajunge la brânză, ştiind că el se poate deplasa numai

pe culoar, iar direcţiile posibile de mişcare sunt N, NE, E, SE, S, SV, V, NV.

De exemplu, pentru un labirint cu 4 linii şi 4 coloane de forma următoare, în

care şoricelul se găseşte pe poziţia 1 1, iar brânza pe poziţia 4 4

0 1 1 1

0 1 1 1

0 1 0 0

1 0 1 0

programul va afişa: Solutia nr. 1

*111

*111

*1**

1*1*

Solutia nr. 2

*111

*111

*1*0

1*1*


Labirintul este reprezentat ca o matrice L, cu nxm elemente. Elementele

labirintului sunt iniţial 0 (semnificând culoar) şi 1 (semnificând perete). Pentru ca

şoricelul să nu treacă de mai multe ori prin aceeaşi poziţie, existând riscul de a intra

în buclă, vom marca în labirint poziţiile prin care trece şoricelul cu 2.

Pentru a determina poziţiile în care se poate deplasa şoricelul, vom utiliza doi

vectori Dx[8] şi Dy[8], pe care îi iniţializăm cu deplasările pe linie, respectiv pe

coloană pentru toate cele 8 direcţii posibile de mişcare.

NV

L[x-1][y-1]

N

L[x-1][y]

NE

L[x-1][y+1]

V

L[x][y-1]

L[x][y]

E

L[x][y+1]

SV

L[x+1][y-1]

S

L[x+1][y]

SE

L[x+1][y+1]


Pentru a nu verifica permanent dacă şoricelul nu a ajuns cumva la marginea

labirintului, bordăm labirintul cu perete ( două linii şi două coloane cu valoarea 1).

Condiţii interne

Din poziţia (x,y) şoricelul se poate deplasa pe direcţia dir, deci în poziţia

(x+Dx[dir], y+Dy[dir]) dacă şi numai dacă L[x+Dx[dir]][y+Dx[dir]]=0

(această poziţie reprezintă un culoar prin care şoricelul nu a mai trecut).


#define DimMax 20

int Dx[8]={-1,-1,0,1,1,1,0,-1};

int Dy[8]={0,1, 1,1,0,-1,-1,-1};

int L[DimMax][DimMax];

int n, m, xs, ys, xb, yb, NrSol;

ofstream fout("labirint.out");

void Citire()

{ifstream f("labirint.in");

f>>n>>m>>xs>>ys>>xb>>yb;


for (int j=1; j<=m; j++) f>>L[i][j];

f.close();}

void Bordare()

{ //bordam labirintul cu cate un perete

for (int i=0; i<=n+1; i++)//perete la stanga si la dreapta

L[i][0]=L[i][m+1]=1;

for (i=0; i<=m+1; i++) //perete sus si jos

L[0][i]=L[n+1][i]=1; }

void Afisare()

{fout<<"Solutia nr. "<<++NrSol<<endl;


{for (int j=1; j<=m; j++)

if (L[i][j] == 2) fout<<'*';

else fout<<L[i][j];

fout<<endl;}

}

void Cauta(int x, int y)

{ L[x][y]=2; //marchez pozitia x y

if (x == xb && y == yb) Afisare();

else

for (int dir=0; dir<8; dir++)

if (!L[x+Dx[dir]][y+Dy[dir]]) //culoar nevizitat

Cauta(x+Dx[dir], y+Dy[dir]);

L[x][y]=0;

/*la intoarcere sterg marcajul, pentru a putea explora

acest culoar si in alta varianta*/

}


int main()

{ Citire(); Bordare();

Cauta(xs, ys);

if (!NrSol) fout<<"Nu exista solutii!\n";

fout.close();

return 0;

}

Exerciţiu

Executaţi programul pas cu pas şi urmăriţi valorile variabilelor globale şi locale.

Fotografie

Fotografia alb-negru a unui obiect este reprezentată sub forma unei matrice cu n

linii şi m coloane ale cărei elemente sunt 0 sau 1. Elementele egale cu 1 reprezintă

punctele ce aparţin unui obiect. Două elemente de valoare 1 fac parte din acelaşi

obiect dacă sunt adiacente pe linie sau pe coloană. Se cere să se determine numărul

obiectelor din fotografie.

De exemplu, pentru matricea: 3 6

1 0 0 0 0 0

0 1 0 0 1 1

0 1 0 0 1 0

programul va afişa: Nr. obiecte = 3

Soluţie

Pentru a număra obiectele din fotografie, vom parcurge matricea care reprezintă

fotografia, căutând un element cu valoarea 1, deci care aparţine unui obiect. Vom

număra noul obiect depistat, apoi vom „şterge” obiectul din fotografie, colorându-l

în culoarea de fond (valoarea 0 în matrice). Pentru a „şterge” un obiect vom folosi

funcţia recursivă Sterge_Obiect(x, y), care în cazul în care punctul de

coordonate (x,y) aparţine obiectului (a[x][y]=1), îl şterge (a[x][y]=0),

apoi se apelează recursiv funcţia pentru toate punctele adiacente cu (x,y) (pe

linie sau pe coloană).

Pentru a nu testa dacă în timpul căutării am depăşit marginile fotografiei, am

bordat matricea care reprezintă fotografia cu câte o linie şi o coloană sus, jos,

stânga, dreapta iniţializate cu valoarea 0 (am „înrămat” fotografia).

Observaţie

Acest tip de algoritm, prin care plecând de la un element sunt „atinse” succesiv

toate elementele care au o legătură (directă sau indirectă) cu elementul respectiv

poartă numele de algoritm de fill (umplere).



#define DimMax 50

int Dx[4]={-1, 0, 1, 0}, Dy[4]={ 0, 1, 0,-1};

int a[DimMax][DimMax], m, n, NrObiecte;

void Citire()

{ifstream fin("foto.in");

fin>>n>>m;


for (int j=1; j<=m; j++) fin>>a[i][j];

fin.close();}

void Sterge_Obiect(int x , int y)

{ if (a[x][y])

{ a[x][y]=0; //sterg acest element de imagine

//cautarea continua in cele 4 directii posibile

for (int dir=0; dir<4; dir++)

Sterge_Obiect(x+Dx[dir], y+Dy[dir]);}

}

int main()

{ Citire();


for (int j=1; j<=m; j++)

if (a[i][j]) //am depistat un obiect

{NrObiecte++;

Sterge_Obiect(i, j);}

cout<<"Nr. obiecte = "<<NrObiecte<<endl;

return 0;}

Cel mai lung prefix

Fie C, o matrice cu n linii şi m coloane, care conţine numai litere. Să se

determine cel mai lung prefix al unui cuvânt dat s, care să se găsească în matricea

C, astfel încât oricare două litere succesive ale prefixului să se afle în matrice pe

poziţii adiacente (pe linie, coloană sau diagonală). Nu se va face distincţie între

literele mari şi cele mici.

De exemplu, pentru cuvântul s='elefantel' şi matricea: elean

ghanr

ttnde

elfen

aeatt

prefixul maximal obţinut va fi: elefa.


Soluţie

Vom utiliza funcţia recursivă Cauta(x,y), care verifică dacă următoarea

literă din cuvânt (indicată de variabila globală Lg, care reţine lungimea prefixului

curent) se află sau nu pe poziţia (x,y) în matricea C. În caz afirmativ, am mai

găsit o literă în matrice, deci lungimea prefixului curent creşte şi continuăm

căutarea în poziţiile adiacente poziţiei (x,y). Altfel am obţinut un prefix maximal

şi comparăm lungimea lui cu lungimea celui mai lung prefix determinat până la

momentul curent (LgMax).

Pentru a nu verifica permanent dacă prin deplasări succesive nu am depăşit

lungimea cuvântului sau limitele indicilor din matrice, vom borda matricea cu

spaţii şi vom marca sfârşitul cuvântului prin caracterul '.'.

De data aceasta nu trebuie să marcăm literele din matrice pe care le-am utilizat

pentru construirea prefixului din două motive:

– putem utiliza aceeaşi literă de mai multe ori;

– nu există riscul de a apela recursiv funcţia Cauta la infinit (sau mai exact

până se umple stiva) deoarece la fiecare apel mărim Lg, lungimea prefixului

curent, şi după strlen(s) paşi vom ajunge la '.', marcajul de sfârşit de

cuvânt.


#include <ctype.h>

#include <string.h>

#define DimMax 30

//dimensiunea maxima a labirintului

int Dx[8]={-1,-1,0,1,1,1,0,-1};

int Dy[8]={0,1, 1,1,0,-1,-1,-1};

char s[200];

int Lg, LgMax, n, m;

char C[DimMax][DimMax];

void Citire()

{ifstream fin("prefix.in");

fin.getline(s, sizeof(s)); fin>>n>>m; fin.get();


{for (int j=1; j<=m; j++)

fin.get(C[i][j]);

fin.get();}

fin.close();}

void Bordare()

{//bordez matricea cu spatii

for (int i=0; i<=n+1; i++) C[i][0]=C[i][m+1]=' ';

for (i=0; i<=m+1; i++) C[0][i]=C[0][n+1]=' '; }


void Cauta(int i, int j)

{/*verific daca elementul de pe linia i coloana j coincide

cu litera de pe pozitia Lg din cuvant */

if (tolower(C[i][j])==tolower(s[Lg])) //am gasit o litera

{ Lg++; //lungimea prefixului curent creste

for (int k=0; k<8; k++) Cauta(i+Dx[k], j+Dy[k]);

Lg--; } //restaurez lungimea prefixului curent

else //prefixul este maximal

if (Lg>LgMax) LgMax=Lg;

/*am comparat lungimea prefixului curent cu lungimea

maxima obtinuta pana acum si, daca este cazul, o retin*/

}

int main()

{ Bordare(); Citire();


for (int j=1; j<=m; j++) Cauta(i,j);

s[LgMax]=NULL;

cout<<"Prefixul maximal este " << s;

return 0;}

Albina

Pe un gazon de formă dreptunghiulară au fost plantate pe fiecare din cele n

rânduri câte m fire de flori de diferite specii. O albină, încântată de coloritul şi de

mireasma florilor, va încerca să polenizeze cât mai multe dintre acestea. Albina se

află iniţial în a k-a floare din rândul r şi la fiecare pas poate zbura din floarea în

care se află în una dintre cele patru flori vecine acesteia situate pe cele patru

direcţii N, E, S, V. Diversitatea tipurilor de flori face ca inflorescenţele acestora să

se afle la diferite înălţimi faţă de sol, fapt ce va îngreuna zborul albinei. Din acest

motiv, pentru a-şi conserva energia, albina va putea zbura la fiecare pas cel mult

h1 unităţi în sus sau cel mult h2 unităţi în jos.

Cerinţă

Cunoscând înălţimea fiecărui fir de floare, determinaţi aria celei mai mari

suprafeţe dreptunghiulare cu flori polenizate de albină.

Date de intrare

Fişierul de intrare albina.in va conţine:

– pe prima linie numerele n şi m separate printr-un spaţiu, reprezentând

dimensiunile gazonului;

– pe linia a doua numerele k şi r separate printr-un spaţiu, reprezentând poziţia

iniţială a albinei ;

– pe cea de-a treia linie numerele h1 şi h2, separate printr-un spaţiu,

reprezentând diferenţele de nivel pe care le poate aborda albina ;


– pe fiecare dintre următoarele n linii, câte m numere naturale separate prin spaţii,

reprezentând înălţimile florilor

Date de ieşire

Fişierul de ieşire albina.out va conţine pe prima linie un singur număr

natural, reprezentând aria celei mai mari suprafeţe cu flori polenizate de albină.

Restricţii şi precizări

1 n, m 30

1 h1, h2 20

Înălţimea fiecărui fir de floare este un număr natural din intervalul [1,100].

Exemplu

albina.in albina.out

4 4

1 3

2 1

1 2 1 15

4 4 2 12

3 2 5 12

1 7 3 10

6

Concursul Naţional de Soft „Grigore Moisil” , Lugoj 2003

Soluţie

Este o problemă de backtracking în plan, în care apar câteva elemente în plus:

condiţionarea deplasării albinei în raport cu înălţimile florilor şi determinarea

suprafeţei dreptunghiulare de aria maximă.


Informaţiile despre înălţimile florilor se reţin într-un tablou a. Acesta este

bordat cu o valoare mai mare decât înălţimea maximă a florilor pentru a nu permite

ieşirea în afara câmpului în timpul procesului de „polenizare”. În plus se foloseşte

un tablou auxiliar t, în care sunt marcate cu valoarea 1 florile care au fost

polenizate. Acest tablou este folosit şi pentru determinarea zonei dreptunghiulare

de arie maximă care conţine numai flori polenizate.

Condiţii interne

1. a[i][j]{1, 2, ..., 100}

2. t[i][j]{0,1}, i{1, ..., n}, j{1, ..., m}

3. 1 n, m 30

4. 1 h1, h2 20


În prima etapă se determină toate florile care pot fi polenizate, plecând de la

floarea iniţială. Printr-un algoritm de tip fill sunt marcate în tabloul t toate

florile care pot fi polenizate.

În etapa a doua se determină zona dreptunghiulară de arie maximă care conţine

doar flori polenizate – adică în tabloul t doar valori egale cu 1. Pentru aceasta se

parcurge tabloul t şi se determină, pe rând, câte un element nenul. Acesta va fi

colţul din stânga-sus a zonei dreptunghiulare testate. Păstrând colţul constant se

determină, pe rând, toate elementele nenule din tablou aflate la dreapta (indice de

coloană mai mare) şi mai jos (indice de linie mai mare) decât colţul respectiv.

Fiecare element nenul detectat va constitui colţul din dreapta-jos a unei zone

dreptunghiulare. Se verifică dacă această zonă conţine numai elemente egale cu 1,

făcându-se produsul tuturor elementelor din zonă, şi, în caz afirmativ, se compară

cu aria maximă detectată până în acel moment, reţinându-se eventual noua arie.

#include <stdio.h>

#define MAX 1000

int dx[4]={-1, 0, 1, 0};

int dy[4]={0, 1, 0, -1};

int t[32][32], a[32][32], n, m, i_prim, j_prim, l_s, l_j;

void citire(void)

{ int i, j;

FILE *f=fopen("albina.in","r");

fscanf(f,"%d %d", &n, &m);

fscanf(f,"%d %d", &i_prim, &j_prim);

fscanf(f,"%d %d", &l_s, &l_j);

for(i=1; i<=n; i++)

for(j=1; j<=m; j++) fscanf(f, "%d", &a[i][j]);

fclose(f);

}

void bordare(void)

{ int i, j;

for(i=0; i<=n+1; i++) a[i][0]=a[i][m+1]=MAX;

for(j=0; j<=m+1; j++) a[0][j]=a[n+1][j]=MAX;

}

void depune(int i, int j)

{ int i_nou, j_nou, l;

t[i][j]=1;

for (l=0; l<4; l++)

{ i_nou=i+dx[l]; j_nou=j+dy[l];

if (t[i_nou][j_nou]==0)

{if ((a[i][j]>=a[i_nou][j_nou])&&

(a[i][j]-a[i_nou][j_nou]<=l_j))

depune(i_nou,j_nou);


if ((a[i][j]<a[i_nou][j_nou])&&

(a[i_nou][j_nou]-a[i][j]<=l_s))

depune(i_nou,j_nou);

}

}

}

int aria(void)

{

int i, j, k, l, i1, j1;

int Max=0,p;

for(i=1; i<=n; i++)

for(j=1; j<=m; j++)

if(t[i][j]) //pentru fiecare floare polenizata

for(k=i; k<=n; k++) //colt stanga-sus

for(l=j; l<=m; l++) //se cauta

if(t[k][l]) //o alta floare polenizata

{ //colt dreapta-jos

//in dreptunghiul determinat de aceste doua flori se face

//produsul elementelor (1 - polenizata sau 0 - nu)

p=1;

for(i1=i; i1<=k; i1++)

for(j1=j; j1<=l; j1++)

p*=t[i1][j1];

if(p) //daca toate au fost 1

//am determinat un dreptunghi plin

if((k-i+1)*(l-j+1)>Max)

Max=(k-i+1)*(l-j+1);

//retin maximul aflat pana acum

}

return Max;

}

int main()

{

FILE *g;

citire();

bordare();

depune(i_prim,j_prim);

g=fopen("albina.out","w");

fprintf(g,"%d",aria());

fclose(g);

return 0;

}


Collapse

Collapse este un joc foarte popular. Tabla de joc este reprezentată de o zonă

dreptunghiulară de pe ecran, zona fiind împărţită în celule, organizate în N linii şi M

coloane. Fiecare celulă poate conţine o piesă roşie (identificată prin litera R), verde

(identificată prin litera V) sau albastră (identificată prin litera A).

Acţionând printr-un clic pe o piesă, tot grupul de piese corespunzător piesei

respective va dispărea.

Grupul unei piese este format din toate piesele care au aceeaşi culoare cu piesa

respectivă şi la care se poate ajunge deplasându-ne numai pe piese de aceeaşi

culoare cu piesa respectivă. O deplasare se poate face în 4 direcţii (sus, jos, stânga

sau dreapta). Un grup trebuie să conţină cel puţin două piese.

După ce grupul piesei asupra căreia am acţionat printr-un clic a dispărut, piesele

de pe tablă se „prăbuşesc”. Prăbuşirea se realizează executând, în ordine,

următoarele două operaţii:

1. Mai întâi, toate piesele rămase „cad” (sunt deplasate în jos), pentru a umple

golurile de pe coloane; ordinea pieselor pe coloane se păstrează.

2. Dacă o coloană se goleşte complet, ea va fi eliminată, deplasând celelalte

coloane către stânga, cât este posibil; ordinea coloanelor se păstrează.

De exemplu, să considerăm tabla de joc din figura următoare:

R R A R V R V

R R R R V A V

V R R R V A R

V V R R R R R

V V R R A V V

V V R R A A A

A A A R V V A

A A A R V V R

A R R R V R R

Dacă executăm un clic pe piesa din colţul din stânga sus, obţinem:

A V R V

V A V

V V A

V V

V V A V V

V V A A A

A A A V V A

A A A V V R

A V R R

Apoi piesele se prăbuşesc. Mai întâi “cad” pentru a umple golurile pe coloane:


V R

V V A V

V V A V

V V A V V

V V A A A

A V A V V A

A A A V V R

A A A V R R

Apoi se elimină coloanele goale:

V R

V V A V

V V A V

V V A V V

V V A A A

A V A V V A

A A A V V R

A A A V R R

Jocul se termină când pe tabla de joc nu se mai pot forma grupuri de piese.

Vasile joacă acest joc de mulţi ani. Niciodată nu joacă la întâmplare,

întotdeauna foloseşte aceeaşi strategie. La fiecare pas, Vasile face un clic pe o

piesă din cel mai mare grup existent pe tabla de joc. Chiar dacă există mai multe

posibilităţi de a alege piesa, el va face clic pe piesa situată pe cea mai din stânga

linie. Şi dacă există mai multe posibilităţi de a alege o piesă pe cea mai din stânga

linie, Vasile o va alege întotdeauna pe cea situată cel mai jos.

Cerinţă

Scrieţi un program care să simuleze jocul şi care să determine numărul de clic-

uri pe care le execută Vasile până la terminarea jocului.

Date de intrare

Fişierul de intrare joc.in conţine pe prima linie două numere naturale

separate printr-un spaţiu N M, care reprezintă numărul de linii şi respectiv numărul

de coloane de pe tabla de joc. Urmează N linii, fiecare linie conţinând M caractere

din mulţimea {‘R’, ‘V’, ‘A’}.

Date de ieşire

Fişierul de ieşire joc.out va conţine o singură linie pe care va fi scris

numărul de clic-uri pe care le execută Vasile până la terminarea jocului.

Restricţii

1 ≤ N, M ≤ 50


Exemple

joc.in joc.out joc.in joc.out

3 4

AVVR

AAVV

AVRR

3 8 7

RRARVRV

RRRRVAV

VRRRVAR

VVRRAVV

VVRRAAA

AAARVVA

AAARVVR

ARRRVRR

7

Olimpiada Naţională de Informatică, Galaţi 2005

Soluţie

Se repetă cât timp se mai pot forma grupuri cu cel puţin 2 elemente:

1. Se determină grupurile de pe tablă. Pentru fiecare grup determinat se calculează

dimensiunea şi se reţine dimensiunea maximă, precum şi elementul cel mai din

stânga-jos care aparţine unui grup de dimensiune maximă.

2. Se şterge grupul de dimensiune maximă selectat.

3. Se compactează coloanele.

4. Se elimină coloanele goale.

Pentru determinarea/ştergerea unui grup se utilizează un algoritm de fill.


#define DMax 52

#define InFile "joc.in"

#define OutFile "joc.out"

#define Dir 4

int dl[]={-1,0,1,0};

int dc[]={0,-1,0,1};

struct poz

{

char cul; //culoarea celulei

int gr; //numarul grupului din care face parte celula

};

poz T[DMax][DMax]; //tabla de joc

int n, m, linmax, colmin, nrclic;

/* linmax si colmin reprezinta coordonatele celulei din

unul dintre grupurile de dimensiune maxima, care se afla

cel mai in stanga – jos */

void citire();

void afisare();


int prelucrare_tabla();

int det_grup(int , int , int , char );

void sterge_grup(int , int , int );

void refa_tabla(int , int );

int main()

{ int dim;

citire();

do

{ linmax=0; colmin=m+1;

dim = prelucrare_tabla();

if (dim>1)

{ nrclic++;

refa_tabla(linmax, colmin); }

}

while (dim>1);

afisare();

return 0;

}

void citire()

{ int i, j;

ifstream fin(InFile);

fin>>n>>m; fin.get();

for (i=1; i<=n; i++)

{

for (j=1; j<=m; j++)

{fin>>T[i][j].cul;

fin.get(); }

//bordare

for (i=0; i<=n+1; i++)

T[i][0].gr=T[i][m+1].gr=DMax*DMax+1;

for (j=0; j<=m+1; j++)

T[0][j].gr=T[n+1][j].gr=DMax*DMax+1;

fin.close();

}

int det_grup(int grnum, int i, int j, char ch)

{ int sum=1, k;

if (T[i][j].cul != ch) return 0;

T[i][j].gr = grnum;

for (k=0; k<Dir; k++)

if (T[i+dl[k]][j+dc[k]].gr==0)

sum+=det_grup(grnum, i+dl[k], j+dc[k], ch);

return sum;

}


int prelucrare_tabla()

/* identifica toate grupurile si returneaza dimensiunea

grupului maxim */

{ int maxdim = 0, dim, grnum=1, i, j;

for (j=1; j<=m; j++)

for (i=n; i>=1 ; i--)

if (T[i][j].gr == 0 && T[i][j].cul!=' ')

//aceasta celula nu apartine nici unui grup

{

dim = det_grup(grnum, i, j, T[i][j].cul);

//marcam grupul

if (dim > maxdim)

{maxdim = dim; linmax=i; colmin=j; }

else

if (dim==maxdim)

if (j<colmin) {colmin=j; linmax=i;}

else

if (j==colmin)

if (i>linmax) linmax=i;

grnum++;

}

return maxdim;

}

void sterge_grup(int grnum, int i, int j)

{if (T[i][j].gr == grnum && T[i][j].cul!=' ')

{ T[i][j].cul=' ';

sterge_grup(grnum, i-1, j);

sterge_grup(grnum, i, j-1);

sterge_grup(grnum, i+1, j);

sterge_grup(grnum, i, j+1); }

}

void refa_tabla(int lin, int col)

{ int i, j, i2, j2;

sterge_grup(T[lin][col].gr, lin, col);

for (j=1; j<=m; j++)

{ //prelucram coloana j

for (i=n; i>=1; i--)

if (T[i][j].cul==' ')

{//caut mai sus un element colorat

for (i2=i-1; i2>=1 && T[i2][j].cul==' '; i2--);

if (i2) //am gasit

{T[i][j]=T[i2][j]; T[i2][j].cul=' '; }

else break;

}

}

//eliminam coloanele goale


for (j=1; j<=m; j++)

if (T[n][j].cul == ' ') //coloana j este vida

{//caut in dreapta o colona nevida

for (j2=j+1; j2<=m && T[n][j2].cul==' '; j2++);

if (j2<=m) //am gasit

//copiez coloana j2 peste coloana j; sterg coloana j2

for (i=1; i<=n; i++)

{T[i][j]=T[i][j2]; T[i][j2].cul=' ';}

else break;

}

for (i=1; i<=n; i++)

for (j=1; j<=m; j++)

T[i][j].gr = 0;

}

void afisare()

{ofstream fout(OutFile);

fout<<nrclic<<endl;

fout.close(); }

3.5. Consideraţii finale asupra metodei backtracking

A existat o perioadă în evoluţia gândirii algoritmice când metoda backtracking

era considerată un panaceu. Nu ştim să rezolvăm o problemă? Nu-i nimic! Aplicăm

un backtracking! Sigur că această metodă are avantaje indiscutabile. Aşa cum

spuneam la începutul capitolului, metoda evită generarea tuturor soluţiilor posibile,

urmată de verificarea condiţiilor problemei pentru fiecare soluţie posibilă (adică se

poate şi mai rău). În plus, rezolvarea unei probleme prin backtracking garantează

obţinerea soluţiei. Numai că timpul de execuţie este foarte mare, datorită reveni-

rilor specifice metodei. Uneori timpul de execuţie este atât de mare încât pentru

dimensiuni mari ale datelor de intrare, este practic imposibilă obţinerea unei soluţii.

În concluzie, când trebuie să rezolvăm o problemă încercăm în primul rând să

elaborăm un algoritm care nu se bazează pe backtracking. Dacă nu reuşim să

elaborăm un astfel de algoritm sau un astfel de algoritm nu există, analizăm datele

de intrare. Dacă datele de intrare au dimensiuni rezonabil de mici, astfel încât un

algoritm backtracking să furnizeze soluţii în timp util, abordăm problema în

această manieră.

Dacă însă datele de intrare au dimensiuni mari, ceea ce în practică este inevita-

bil, o abordare backtracking este inacceptabilă. Principiul de bază poate fi rezumat

astfel: decât un algoritm teoretic perfect, dar care să nu furnizeze soluţii în timpul

disponibil, mai bine un algoritm bun, care să ofere soluţii „aproape” optime în

timp scurt. Un astfel de algoritm este denumit algoritm euristic. Studiul

algoritmilor euristici este o problemă „fierbinte” în informatică la ora actuală.


3.6. Probleme propuse

1. Urmăriţi pas cu pas execuţia următorului program pentru n=4. Ce va afişa pe

ecran programul?

#include <iostream.h>

char x[30];

int n;

void gen(int k)

{ if (k==n) cout<<x<<endl;

else

for (char c='a'; c<'d'; c++)

if (x[k-1]!=c)

{x[k]=c;

gen(k+1); }

}

int main()

{cin>>n;

x[0]='a';

gen(1); return 0;}

2. Care dintre următoarele afirmaţii sunt adevărate şi care sunt false?

a. Metoda backtracking se poate implementa numai cu ajutorul funcţiilor

recursive.

b. Metoda backtracking evită generarea tuturor soluţiilor posibile, urmată de

verificarea condiţiilor interne pentru fiecare soluţie posibilă.

c. Indiferent de problemă, aplicarea metodei bactracking conduce la cei mai

eficienţi algoritmi.

3. Prin metoda backtracking au fost generate toate posibilităţile de a aranja pe un

rând 4 copii (Ana, Dan, Ion, Maria), astfel încât să nu fie plasaţi doi băieţi

unul lângă altul. Primele 4 soluţii generate sunt: Ana Dan Maria Ion

Ana Ion Maria Dan

Dan Ana Ion Maria

Dan Ana Maria Ion

Care va fi următoarea soluţie generată?

4. Secvenţe binare

Să se genereze toate secvenţele binare de lungime m, în care apar n de 1.

5. Coliere

Scrieţi un program care să vizualizeze în mod text toate colierele de n (nN*)

mărgele albe, roşii, galbene, verzi şi negre care se pot construi respectând

următoarele reguli:

– nu plasăm două mărgele de aceeaşi culoare în poziţii consecutive;


– nu plasăm mărgele albe lângă mărgele galbene şi nici mărgele verzi lângă

mărgele negre;

– nu utilizăm mai mult de n/2 mărgele roşii.

6. Numere cu suma cifrelor dată

Să se afişeze toate numerele formate din cifre distincte cu proprietatea că suma

cifrelor este S. Valoarea variabilei S se citeşte de la tastatură. Soluţiile vor fi afişate

pe ecran. De exemplu, pentru S=3, se afişează soluţiile 102, 12, 120, 201, 21,

210, 3, 30. Bacalaureat, 2000

7. Matrice

Fie nN*, n10, n par. Să se genereze toate matricele cu n linii şi n coloane

având componente numere naturale între 1 şi n astfel încât oricare două elemente

vecine (pe orizontală sau verticală) să fie de parităţi diferite, iar elementele de pe

aceeaşi linie, respectiv de pe aceeaşi coloană să fie distincte.

Soluţiile vor fi afişate în fişierul matrice.out, între două soluţii consecutive

fiind scrisă o linie goală.

8. Operatori

Se citesc de la tastatură un număr natural n (0<n10) şi apoi n valori naturale

a1, a2, ..., an. Afişaţi pe ecran toate posibilităţile de a intercala între toate numerele

a1, a2, ..., an operatorii + şi – astfel încât evaluând expresia obţinută de la stânga la

dreapta, la fiecare pas rezultatul obţinut să fie strict pozitiv. Fiecare soluţie se va

afişa pe câte o linie. De exemplu, pentru n=3 şi valorile a1=3, a2=5, a3=2, se vor

afişa soluţiile:

3+5+2

3+5-2 (variantă bacalaureat, 2000)

9. Examen

Un student primeşte la un examen n subiecte, numerotate de la 1 la n

(1≤n≤20). Pentru fiecare subiect este cunoscut punctajul care se obţine rezolvând

subiectul respectiv (nu se acordă punctaje parţiale), precum şi dificultatea

subiectului. Studentul vrea să obţină cel puţin un punctaj total P, dar nu poate să

rezolve subiecte cu dificultate > D.

Determinaţi toate variantele în care studentul poate obţine un punctaj

satisfăcător.

Fişierul de intrare examen.in conţine pe prima linie trei numere naturale

separate prin spaţii n, P şi D, cu semnificaţia din enunţ. Pe cea de a doua linie se

află n numere naturale separate prin spaţii, reprezentând, în ordine, dificultăţile

subiectelor. Pe cea de a treia linie se află n numere naturale separate prin spaţii,

reprezentând, în ordine, punctajele subiectelor.


Fişierul de ieşire examen.out va conţine câte o linie pentru fiecare variantă

generată. Descrierea unei variante este constituită din numerele subiectelor

rezolvate, separate prin câte un spaţiu. Dacă nu există nici o variantă satisfăcătoare,

fişierul de ieşire va conţine pe prima linie mesajul MAI INVATA!.

10. Generare şir

Se citesc de la tastatură două numere naturale a şi b (0<a10, 0<b1000,

3a b). Să se genereze cel mai lung şir care are ca prim element valoarea a,

suma elementelor şirului este egală cu b şi în care orice termen este cel puţin

dublul valorii termenului precedent. Şirul obţinut se va afişa pe un singur rând, cu

spaţii între elementele ce-l formează.

Dacă există mai multe şiruri cu acelaşi număr maxim de elemente, se va afişa

unul singur, oricare dintre acestea.

De exemplu, pentru a=4 şi b=63 se va afişa oricare dintre următoarele şiruri: 4 8 16 35

4 8 17 34

Se observă că şirul 4 11 48 respectă condiţiile din enunţ, dar nu are număr

maxim de termeni. Bacalaureat special 2002

11. Rând

Într-o clasă de n elevi sunt f fete (n,fN*, fn). Fetele sunt numerotate de

la 1 la f, iar băieţii de la f+1 la n. Să se genereze toate posibilităţile de a forma un

rând din p elevi (pn) astfel încât să nu existe două fete aşezate în rând una lângă

cealaltă, respectiv doi băieţi unul lângă celălalt.

12. Generare şiruri crescătoare

Să se genereze toate şirurile strict crescătoare formate din numere naturale cu

proprietatea că primul element din şir este n, iar ultimul element al şirului este

n+k. Numerele naturale n şi k (0<n<20, 0<k<16) sunt citite de la tastatură.

Fiecare şir generat va fi scris pe o linie, elementele unui şir fiind separate prin câte

un spaţiu

De exemplu, pentru n=7 şi k=3, se vor afişa (nu neapărat în această ordine)

şirurile: 7 8 9 10

7 8 10

7 9 10

7 10

Bacalaureat 2001 13. Generare şiruri de cifre

Să se genereze toate şirurile formate din n cifre, fiecare şir generat având

următoarele proprietăţi:


– conţine numai cifre din mulţimea {1, 2, 3, 4};

– orice două cifre alăturate sunt fie ambele pare, fie ambele impare.

Numărul natural n (3 n 15) se citeşte de la tastatură. Toate soluţiile vor fi

scrise una după alta, cu spaţii între soluţii, fiecare şir fiind scris fără spaţii între cifrele

ce-l formează.

De exemplu, pentru n=3, se afişează (nu neapărat în această ordine) şirurile: 111 113 131 133 311 313 331 333 222 224 242 244

422 424 442 444

Bacalaureat august 2001

14. Tombolă

La o tombolă sunt n obiecte (numerotate de la 1 la n), care valorează v1, v2, ...,

respectiv vn lei. Premiul cel mare trebuie să fie format din obiecte din categorii

diferite, a căror valoare totală să fie exact S lei. Să se determine în câte moduri se

poate constitui premiul cel mare. Datele se citesc din fişierul de intrare

tombola.in care conţine pe prima linie un număr natural nenul n, reprezentând

numărul de obiecte. Pe cea de a doua linie se află n numere naturale nenule

separate prin câte un spaţiu, reprezentând, în ordine, valorile celor n obiecte. Pe

următoarea linie este scris un număr natural k, reprezentând numărul de categorii.

Pe ultima linie este sunt scrise n numere cuprinse între 1 şi k, separate prin spaţii

(al i-lea număr de pe linie reprezintă categoria din care face parte obiectul i).

Numărul de variante va fi afişat pe ecran.

15. Bare

Se consideră o bară de lungime n şi m repere de lungimi L1,L2,…,Lm. Din bară

trebuie tăiate bucăţi de lungimea reperelor date, astfel încât să rezulte din fiecare

reper cel puţin o bucată şi pierderile să fie nule. Scrieţi un program care să afişeze

toate posibilităţile de tăiere a barei în condiţiile enunţate.

16. Banda

Misiunea unui robot este de a lua obiecte de pe o bandă de asamblare, în

ordinea în care sunt produse şi de a le introduce în containere care sunt identice şi

au capacitatea gmax.

La fiecare moment de timp numai două containere sunt disponibile. După ce ia

un obiect de pe bandă, robotul poate alege între:

– a plasa obiectul în unul dintre cele două containere disponibile, dacă este posibil

(adică dacă nu se depăşeşte greutatea gmax);

– a închide unul dintre cele două containere şi a deschide unul nou, pentru a pune

în el obiectul.

Atenţie! După ce a fost închis un container, acesta este sigilat şi nu poate fi

redeschis.


Scrieţi un program care să determine numărul minim de containere necesar

pentru a transporta obiectele de pe banda de asamblare dacă se cunoaşte n numărul

lor, greutăţile acestora gi (i =1, …, n) precum şi capacitatea gmax a unui

container.

Date de intrare

Fişierul de intrare banda.in conţine pe prima linie două numere naturale

separate prin spaţiu n gmax, reprezentând numărul de obiecte şi capacitatea unui

container. Pe cea de a doua linie se află n numere naturale separate prin spaţii g1

g2 … gn, reprezentând greutăţile celor n obiecte.

Date de ieşire

Fişierul de ieşire banda.out va conţine pe prima linie numărul minim de

containere necesare transportului.

Restricţii n ≤ 25

0 < gmax ≤ 100

0 < gi ≤ 100

Exemplu banda.in banda.out

6 8

4 2 5 3 5 4

3

Olimpiada Municipală de Informatică, Iaşi 2004

17. Puncte

Fie n un număr natural (n20) şi P1, P2, ..., Pn puncte în plan, având de

coordonate întregi. Să se determine o modalitate de colorare a celor n puncte,

folosind un număr minim de culori, astfel încât oricare două puncte situate la

distanţă D să fie colorate diferit.

18. Concurs

Cei N elevi, numerotaţi de la 1 la N, din tabăra olimpicilor informaticieni de la

Costineşti doresc să se întreacă într-un campionat pe nisip de tras la frânghie.

Pentru aceasta ei se împart în P echipe, dar pentru ca întrecerea să fie cât mai

echilibrată, echipele trebuie să fie cât mai apropiate ca greutate. Greutatea unei

echipe este dată de suma greutăţilor componenţilor ei.

Cerinţă

Cunoscând greutăţile g1, g2, ..., gN ale celor N elevi, să se formeze cele P echipe

astfel încât echipele să fie cât mai echilibrate, adică suma diferenţelor de greutate

dintre oricare două echipe trebuie să fie minimă.


Date de intrare

Fişierul de intrare concurs.in va conţine pe prima linie valorile N şi P

separate printr-un spaţiu. Pe linia a doua se găsesc cele N greutăţi separate prin câte

un spaţiu.

Date de ieşire

Fişierul de ieşire concurs.out va conţine pe prima linie valoarea minimă a

sumei diferenţelor de greutate dintre oricare două echipe. Următoarele P linii vor

conţine cele P echipe, fiecare linie conţinând indicii membrilor unei echipe,

separaţi prin câte un spaţiu.

Restricţii

2 N 10

2 P 6

P N

40 gi 99, 1 i N

În fiecare echipă trebuie să existe cel puţin un elev.

Exemplu

concurs.in concurs.out Explicaţii 7 3

11 20 30 39 50 61 70

24

1 2 7

4 5

3 6

Greutatea echipei E1 este 101. Greutatea

echipei E2 este 89. Greutatea echipei E3

este 91. Deci (E1-E2)+(E1-E3)+(E3-E2)=

12+10+2=24

19. Problema bilei

Un teren este reprezentat ca o matrice T, cu n linii şi m coloane, elementele

matricei reprezentând cotele diferitelor porţiuni de teren. În poziţia iniţială

(xb,yb) se află o bilă. Ştiind că bila nu se poate deplasa decât într-o porţiune de

teren învecinată (pe direcţiile N, NE, E, SE, S, SV, V, NV) cu cotă strict inferioară

poziţiei pe care se află, scrieţi un program care să determine toate traseele pe care

le poate urma bila pentru a ieşi din teren.

20. Săritura calului

Pe o tablă de şah de dimensiune n (nN*) se află plasat un cal în colţul din

stânga sus. Afişaţi toate posibilităţile calului de a parcurge toată tabla de şah, fără a

trece de două ori prin aceeaşi poziţie.

21. Explorarea Labirintului

Un labirint este reprezentat ca un tablou bidimensional. Pereţii labirintului sunt

marcaţi cu 'X', culoarele labirintului fiind marcate cu spaţii. Problema este de a

determina toate punctele labirintului care pot fi vizitate începând cu o poziţie

iniţială (de start) marcată prin caracterul '*'.


22. Joc

Există şi jocuri care pot fi jucate de un singur jucător. Un astfel de joc este

descris mai jos.

O tablă rectangulară de dimensiuni NxM este plină cu litere mari a alfabetului

(A-Z). La începutul jocului în colţul din stânga sus al tablei este plasată o piesă. În

fiecare moment, jucătorul poate muta această piesă într-o poziţie vecină (sus,

dreapta, jos, stânga), cu singura restricţie ca în poziţia respectivă să nu existe o

literă peste care piesa a mai trecut. Scopul jocului este de a menţine piesa în joc cât

mai mult posibil. Jocul se opreşte când piesa nu mai poate fi mutată într-o poziţie

validă şi se opreşte într-o poziţie în care există o literă peste care piesa a mai trecut.

Scrieţi un program care determină numărul maxim de mutări pe care le poate

face jucătorul.

Date de intrare

Prima linie a fişierului de intrare joc.in conţine două valori întregi N şi M,

separate printr-un singur spaţiu, reprezentând dimensiunile tablei de joc.

Următoarele N linii conţin fiecare câte M caractere reprezentând tabla de joc.

Date de ieşire

Fişierul de ieşire joc.out conţine o singură linie pe care se află numărul

maxim de mutări pe care le poate face jucătorul.

Restricţii

1 ≤ N, M ≤ 30

Exemple

joc.in joc.out joc.in joc.out joc.in joc.out

2 4

CAAB

ADCB

3 5 5

IEFCJ

FHFKC

FFALF

HFGCF

HMCHH

10 3 6

HFDFFB

AJHGDH

DGAGEH

6

.campion 2003

23. Calul şi Regele

Un cal şi un rege se află pe o tablă de şah. Unele dintre câmpuri sunt arse,

poziţiile lor fiind cunoscute. Calul nu poate călca pe câmpuri „arse”, iar orice

mişcare a calului pe un nou câmp, bineînţeles „nears”, face ca acesta să devină ars.

Scrieţi un program care să determine dacă există o succesiune de mutări prin care

calul să ajungă la rege şi să revină în poziţia sa iniţială, cu regele în spate.

24. Popularea acvariului

Dacă dorim să creăm un acvariu cu peşti exotici, trebuie să cerem avizul unui

expert pentru a nu ajunge în situaţia în care să cumpărăm tipuri de peşti care nu pot

coexista în acvariu.


Fiind date numărul maxim n de tipuri de peşti şi suma S care poate fi cheltuită

pentru investiţie, se cere să se stabilească numărul maxim de tipuri compatibile de

peşti care se pot cumpăra. Pentru acest număr, se cere suma maximă folosită (dar

nu mai mult de S), ştiind că se cumpără câte un singur peşte din fiecare tip.

Scrieţi un program care citeşte din fişierul de intrare 'acv.in' :

– de pe prima linie S, suma de bani disponibilă (S1000);

– de pe a doua linie n, numărul de specii (n30);

– de pe a treia linie, în ordine, preţul fiecărei specii de peşti;

– pe fiecare din următoarele linii se specifica câte o pereche de specii de peşti

(separate printr-un spaţiu) care nu pot coexista în acelaşi timp în acvariu.

În fişierul acv.out vor fi afişate numărul maxim de specii ce pot fi

cumpărate, suma maximă cheltuită, precum şi speciile cumpărate în aceste condiţii.

25. Râma lacomă

Se dă o reţea rectangulară de dimensiune mxn (0<m<101, 0<n<101). În

anumite noduri, ale căror coordonate se citesc din fişierul de intrare, se află

substanţe nutritive (SN) în cantităţi precizate. O râmă se poate deplasa orizontal sau

vertical, pornind dintr-un nod ce conţine SN. Deplasarea între două noduri alăturate

presupune pierderea unei unităţi de SN. Trecerea printr-un nod ce conţine SN

presupune câştigarea întregii cantităţi de SN din nod. Să se stabilească un nod de

plecare şi un traseu de deplasare astfel încât:

– râma să culeagă toate cantităţile de SN;

– cantitatea finală de SN câştigată de râmă să fie maximă.

Iniţial râma nu are SN şi nu se poate deplasa fără SN. Dacă nu este posibilă

culegerea tuturor cantităţilor de SN se va afişa mesajul Rama moare. Baraj, Focşani, 1995

Back Teorie Si Aplicatii

Documents

Transcript of Back Teorie Si Aplicatii