Backtraking pentru funcţii InjectiveSurjectiveBijective
2
Aplicaţ ii backtraking pentru funcţii injective, surjective, bijective Funcţii injective. Aranjamente. Definiţie Fie f : A→ B o funcie. f este o funcie injecti vă sau f este o injecie, dacă pentru oricare două elemente x şi y ale lui A, x≠y, f(x)≠f(y). Să se g enereze toate funciile injective f :{a 1 ,a 2 …..a m }->{b 1 ,b 2 …..b n }, unde card(A)=m, card(B)=n O soluţie este formată din m elemente (nr.elementelor mulţimii A) iar fiecare element din soluţie reprezintă valoarea funcţiei f(k) (un element din B). Problema se reduce la generarea tuturor A n m (n>=m) Ex.1 1 . Să se genereze toate funciile injective f :{a 1 ,a 2 …..a m }->{b 1 ,b 2 …..b n } cu proprietatea c ă f(a i )*f(a i+1 ) >= 0 . Exemplu pentru a=(1,2,3) şi b=(-1,-2,3,-4,5) Soluiile (6) vor fi f(1)=-1 f(2)=-2 f(3)=-4 f(1)=-1 f(2)=-4 f(3)=-2 f(1)=-2 f(2)=-1 f(3)=-4 f(1)=-2 f(2)=-4 f(3)=-1 f(1)=-4 f(2)=-1 f(3)=-2 f(1)=-4 f(2)=-2 f(3)=-1 Rezolvare : Presupunem că vectorul soluiei este V, atunci orice V[k] reprezintă valoarea funciei f (k) Pe nivel al stivei , V[k] va lua valori din {b 1 ,b 2 …..b n }.Cum nu există o relaie de ordine între elementele mulimii B, atunci în V[k] vom reine poziia elementului din B. Conform restriciilor din enun validarea presupune ca în afara faptului că elementele trebuie să fie distincte trebuie să verificăm şi că f(a i )*f(a i+1 ) >= 0 ; … pe orice nivel al stivei element ul este invalid dacă (b[v[i]]* b[v[i-1]]<0) sau v[k]==v[i] (i=1,k-1) Funcţii surjective . Produs cartezian . Definiţie O funcie f : A→ B este o funcie surject ivă , sau f es te o surjecie, dacă pentru orice elemen t b B există cel puţin un element a A, astfel încât f(a)=b. Să se genereze toate funciile surjective f :{a 1 ,a 2 …..a m }->{b 1 ,b 2 …..b n }, unde card(A)=m, card(B)=n. O soluie este formată din m elemente (nr.elementelor mulimii A), fiecare soluie . Problema se reduce la generarea produsului cartezian B 1 xB 2 x….xB m ( B m)* (Atenţie ! algoritm exponenţial datorită numărului mare de elemente ale produsului cartezian ) Vor fi considerate soluţii numai cele care conţin toate elementele din mulţimea B.(după generarea unei posibile soluţii verificaţi înainte de afişare !!!) Ex.2 . Să se genereze toate funciile surjective f :{a 1 ,a 2 …..a m }->{b 1 ,b 2 …..b n } astfel încât ∑ <=x, x număr întreg dat. Dacă problema nu are soluie, se va afişa mesajul de eroare “Fără soluie”. Pentru A=(1,2,3) B=(1,2) x=4 vor fi afişate funciile f(1)=1 f(2)=1 f(3)=2 ( 1+1+2=4) f(1)=1 f(2)=2 f(3)=1 f(1)=2 f(2)=1 f(3)=1 Rezolvare : Presupunem că vectorul soluiei este V, orice V[k] va lua valor i din B. Teoretic, pentru generarea produsului cartezian orice valoare este validă . Restriciile din enun , reduce numărul de soluii. 1 Culegere probleme informatică Carmen Negrea/ Mihaela Runceanu Ed.Donaris 2003 k=3 2 (1,2) k=2 1 (1,2) k=1 1 (1,2) V[k] k=3 4 (1,2,3,4,5) k=2 2 (1,2,3,4,5) k=1 1 (1,2,3,4,5) poziţi a elem.din B V[k] Ex. V=(1,2,3) nu este soluie b[2]*b[3]<0 ( -2*3 <0 )
-
Upload
andrei-oldan -
Category
Documents
-
view
9 -
download
0
description
Backtraking pentru funcţii InjectiveSurjectiveBijective
Transcript of Backtraking pentru funcţii InjectiveSurjectiveBijective
-
5/28/2018 Backtraking pentru func ii InjectiveSurjectiveBijective
Aplica ii backtraking pentru funcii injective, surjective, bijective
Funcii injective. Aranjamente.
Definiie
Fie f : A B o funcie. f este o funcie injectiv sau f este o injecie, dacpentru oricare douelemente x i y ale lui A, xy, f(x)f(y).
S se genereze toate funciile injective f:{a1,a2..am}->{b1,b2..bn}, unde card(A)=m, card(B)=nO soluie este format din m elemente (nr.elementelor mulimii A) iar fiecare element din soluie
reprezint valoareafunciei f(k) (un element din B).
Problema se reduce la generarea tuturor Anm (n>=m)
Ex.11.S se genereze toate funciile injective f:{a1,a2..am}->{b1,b2..bn} cu proprietatea c
f(ai)*f(ai+1) >= 0 .Exemplu pentru a=(1,2,3) i b=(-1,-2,3,-4,5)
Soluiile (6) vor fi
f(1)=-1 f(2)=-2 f(3)=-4f(1)=-1 f(2)=-4 f(3)=-2
f(1)=-2 f(2)=-1 f(3)=-4f(1)=-2 f(2)=-4 f(3)=-1f(1)=-4 f(2)=-1 f(3)=-2f(1)=-4 f(2)=-2 f(3)=-1
Rezolvare :Presupunem cvectorul soluiei este V, atunci orice V[k] reprezint valoarea funciei f(k)Pe nivel al stivei , V[k] va lua valori din {b1,b2..bn}.Cum nu exist o relaie de ordine ntre elementelemulimii B, atunci n V[k] vom reine poziia elementului din B.Conform restriciilor din enun validarea presupune ca n afara faptului c elementele trebuie s fie
distincte trebuie s verificm i c f(ai)*f(ai+1) >= 0 ; pe orice nivel al stivei elementul este invaliddac (b[v[i]]*b[v[i-1]]{b1,b2..bn}, unde card(A)=m, card(B)=n. Osoluie este format din melemente (nr.elementelor mulimii A), fiecare soluie .Problema se reduce la generarea produsului cartezian B1xB2x.xBm ( B
m)* (Atenie ! algoritm
exponenial datorit numrului mare deelemente ale produsului cartezian )Vor fi considerate soluii numai cele care conin toate elementele din mulimea B.(dup generareaunei posibile soluii verificai nainte de afiare!!!)
Ex.2 . S se genereze toate funciile surjective f :{a1,a2..am}->{b1,b2..bn} astfel nct
-
5/28/2018 Backtraking pentru func ii InjectiveSurjectiveBijective
Se consider soluie dac
-
5/28/2018 Backtraking pentru func ii InjectiveSurjectiveBijective
