Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» TEHNICA BACKTRACKING


TEHNICA BACKTRACKING


TEHNICA BACKTRACKING

PREZENTAREA TEHNICII BACKTRACKING:

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:



Solutia lor poate fi pusa sub forma unui vector S=x1x2,....,xn cu x1I A1, x2 I A2, ...., xn I An ;

Multimile A1, A2, ...., An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

Nu se dispune de o alta metoda de rezolvare, mai rapida;

Aceasta tehnica presupune trei functii:

Functia de citire a valorile cunoscute;

Functia de tiparire a solutiilor;

Functia backtracking.

Schema generala a procedurii backtracking:

Void back (int k)

Int I, cont;

Programele prezentate mai jos, in pseudocod, sunt:

Paranteze;

Comis-voiajor;

Dame;

Submultimi;

Magazin;

Permutari.

PROGRAME IN PSEUDOCOD

Paranteze: se da un numar natural par n. Sa se determine toate sirurile de n paranteze care se inchid corect.

procedura tipar

j nr natural

pentru p < - 1,n executa // afisarea solutiilor

daca a[p]<-1

atunci scrie ")" // conditie pt afisarea parantezelor inchise

// de la daca

altfel scrie "("

// de la pentru

procedura back (k nr natural)

cont, i, d, j nr naturale

daca k=n+1 // conditie pentru afisare

atunci tipar

// de la daca

altfel pentru i <-0,1 executa

a[k]<-1

cont <-1

daca k=1

atunci daca a[k]=1

atunci cont <- 0 // conditie pentru panateza (

// de la daca a[k]=1

// de la daca k=1

daca k=n

atunci daca a[k]=n

atunci cont <- 1 // conditie pentru paranteza )

// de la daca a[k]=n

// de la daca k=n

d<-0 // numara cate paranteze inchise sunt

pentru j <-1,k executa // de la 1 pana la pozitia la care s-a ajuns executa

daca a[j]=0

atunci d <- d+1 // daca gaseste o paranteza inchisa atunci d creste

// de la daca

// de la pentru (j)

daca d>n/2

atunci cont <- 0 // conditie pt ca nr. de paranteze inchise sa nu fie mai mare de n/2

// de la daca

daca k-d>d

atunci cont <- 0 // conditie pt ca diferenta dintre pozitia la care s-a ajuns (k) si nr. de paranteze inchise

sa nu fie mai mare de numarul de paranteze inchise

// de la daca

daca cont=1

atunci back (k+1) // apelarea recursiva a procedurii back (cu parametru )

//de la daca

//de la pentru (i)

programul principal

se citeste n ( n nr natural )

back (1)    // apelarea procedurii back pentru k=1

exemplu:

date de intrare: n=6

date de iesire : ( ( ( ) ) ), ( ( ) ( ) ), ( ) ( ) ( ), ( ) ( ( ) ), ( ( ) ) ( )

Un comis voiajor porneste din orasul 1 si trebuie sa treaca prin toate cele n-1 orase ramase astfel incat sa nu treaca de 2 ori prin acelasi oras si sa se intoarca in orasul 1. Se citesc legaturile dintre cele n orase cu ajutorul unui matrice de adiacenta cu n linii si n coloane.

procedura tipar

j nr natural

pentru j <- 1,n executa // tiparirea solutiilor

scrie a[j]

// de la pentru

procedura back (k nr intreg)

i,t,cont nr intregi

daca k=n+1 // conditie pt tiparirea solutiilor

atunci tipar

// de la daca

altfel

pentru i <- 1,n executa

a[k] <- i

cont <-1

daca k>1

pentru t <-1,k-1

daca a[k]=a[t] // conditie pt orase distincte

atunci cont <- 0

// de la daca

// de la pentru (t)

daca a[m[k-1][k]] =0 // conditie pt ca intre 2 orase sa existe drum

atunci cont <- 0

// de la daca

daca a[m[n][1]]=0 // conditie pt ca intre ultimul si primul oras sa existe drum

atunci cont <- 0

// de la daca

// de la daca (k>1)

daca cont=1

atunci back(k+1) // apelarea recursiva a procedurii back (cu parametru )

// de la daca

// de la pentru (i)

program principal

citeste n (n nr natural)

pentru b<-1,n (b nr natural) // citirea matricei de adiacenta

pentru c<- 1,n (c nr natural)

scrie m[b][c] (valori naturale)

// de la pentru (c<-1,n)

// de la pentru (b<-1,n)

back(1) // apelarea procedurii back (pt k=1)

exemplu :

date de intrare : 4

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

date de iesire : 1 2 3 4

Se dau n dame si se cere sa fie asezate pe o tabla de sah (n x n ) astfel incat ele sa nu se atace.

procedura tipar

i nr natural

pentru i <- 1,n executa // tiparirea solutiilor

scrie a[i]

// de la pentru

procedura back (k nr intreg)

t, i, cont nr intregi

daca k=n+1 // conditie pt tiparirea solutiilor

atunci tipar

// de la daca

altfel

pentru i <-1,n executa

a[k]<-i

cont<-1

daca k>1

pentru t <-1,k-1 executa

daca a[k]=a[t] sau a[k]-a[t] k-t // conditii pt ca damele sa nu se atace

atunci cont <-0

// de la daca

// de la pentru (t)

// de la daca (k>1)

daca cont <-1

atunci back(k+1) // apelarea recursiva a procedurii back ( cu parametru )

// de la daca

// de la pentru (i)

program principal

citeste n (nr natural)

back (1) // apelarea procedurii back (pt k=1)

exemplu :

date de intrare : 4

date de iesire : 2 4 1 3

Aflati toate submultimile care sunt incluse intr-o multime data. Se citesc nr de elemente ale multimii si elementele sale.

procedura tipar

j nr natural

pentru j <- 1,n executa

daca a[j]=1 // conditie pt tiparirea solutiilor

scrie m[j] // tiparirea solutiilor

// de la daca

// de la pentru

procedura back (k nr natural)

cont, i nr naturale

daca k=n+1 // conditie pt tiparirea solutiilor

atunci tipar

// de la daca

altfel

pentru i <- 0,1 executa

a[k] <-i

cont <-1

daca cont =1 // nu sunt conditii de continuare

atunci back (k+1) // apelarea recursiva a procedurii back ( cu paremetru )

// de la daca

// de la pentru

programul principal

citeste n ( nr natural )

pentru x <-2,n (x nr natural)

citeste m[x] ( valori naturale)

// de la pentru

back(1) // apelarea procedurii back (pt k=1)

exemplu :

date de intrare : 3

1 4 7

date de iesire : 7, 4, 4 7, 1, 1 7, 1 4, 1 4 7

Un copil intra intr-un magazin de jucarii. El are o suma s de bani si doreste sa-si cumpere cat mai multe jucarii. Sa se cate produse diferite poate cumpara copilul stiind ca in magazin se afla n produse, fiecare avand cate un pret dat.

procedura tipar (k nr natural)

pentru i <- 1,k-1 executa

scrie a[i] // tiparirea solutiilor

// de la pentru

procedura back(k nr natural, suma nr intreg)

t, i, cont nr naturale

daca s=suma // conditia pt tiparirea solutiilor

atunci tipar(k) // apelarea procedurii tipar (cu parametru )

// de la daca

altfel

pentru i <- 1,n executa

a[k]<-i

cont<-1

daca k>1

pentru t <-1, k-1

daca a[k]<=a[t] // conditie pt a nu se repeta produsele in cadrul aceleiasi solutii

atunci cont <-0

// de la daca

// de la pentru (t)

// de la daca (k>1)

daca suma>s // conditie pt ca preturile produselor (suma) < suma disponibila (s)

atunci cont <-0

// de la daca

daca cont=1

atunci back(k+1, suma+p[a[k]]) // apelarea recursiva a procedurii back

// suma+p[a[k]] reprezinta suma anterioara + pretul produsului a[k]

// de la daca

// de la pentru (i)

programul principal

citesc s (nr intreg)

citesc n (nr natural)

pentru j <- 1,n executa

citesc p[j] (valori intregi) // se citesc preturile produselor

// de la pentru

back (1,0) // apelarea procedurii back (pt k=1 si suma=0)

exemplu :

date de intrare : 100, 5

5, 80, 15, 20, 85

date de iesire : 1 2 3

Powered by https://www.preferatele.com/

cel mai tare site cu referate





Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate