Question

Fie mulțimea de litere A = {a, b, c, d, e, i}. Cu ajutorul metodei backtracking se construiesc toate secvențele formate


din 5 litere distincte (din mulțimea A) ce nu conțin două vocale alăturate. Câte soluții vor fi generate?


a) 256 b) 562 c) 224 d) 252


Explicatie va rog!.

Answer 1

► Raspuns :

D) 252

► Explicatie :

Avem 3 consoane si 3 vocale.

Deoarece fiecare litera apare maxim odata putem avea 3 consoane si 2 vocale sau 3 vocale si 2 consoane. Fiecare astfel de configuratie posibila are 36 de variante de asezare a consoanelor si a vocalelor. Spre exemplu :

VCVCV : Pentru prima vocala avem 3 variante de alegere, pentru prima consoana 3 variante de alegere, pentru a doua consoana avem 2 variante alegere (dupa ce am ales prima data), pentru a doua consoana avem doua variante de alegere (dupa ce am ales prima data), pentru ultima vocala avem o singura varianta de alegere disponibila. Acelasi rationament si in celelalte cazuri. Din regula produsului exista 3*3*2*2*1 = 36 posibilitati

Configuratii posibile (V - pe pozitia respectiva se afla o vocala, C - pe pozitia respectiva se afla o consoana):
VCVCV - singura posibilitiate de a avea trei vocale si doua consoane
CCVCV
CVCCV
VCCCV
CVCVC
VCCVC
VCVCC

Configuratiile de 3 consoane sunt generate cu metoda backtracking (practic ai toate posibilitatile de a forma un cuvant cu 3 litere de C si 2 de V, cu conditia ca nu ai voie sa ai doua V-uri succesiv)

Avand 7 configuratii posibile, fiecare cu cate 36 de variante rezulta ca avem 7*36 = 252 de astfel de solutii.