Backtracking

Apărut la 1 iulie 2010 în Teste de informatică   |   autor: Dan Pracsiu 0 comentarii

Rândul 1

1. (Nota 6) Se citesc numerele naturale n şi p. Să se genereze toate şirurile de n numere naturale care au proprietăţile:
- şirul începe şi se termină cu numărul p;
- diferenţa în modul a oricare două numere alăturate din şir este 1.
Exemplu: pentru n=5, p=2, două astfel de soluţii sunt
2 1 2 1 2
2 3 4 3 2

2. (Nota 8) Se citeşte de la tastatură un număr natural S£36. Să se afişeze la ecran toate numerele formate cu cifre distincte cu proprietatea că suma cifrelor este S. De exemplu, pentru S=3: 102, 12, 120, 201, 21, 210, 3, 30.

3. (Nota 10) Se consideră două cuvinte a şi b şi o listă având n cuvinte. Se doreşte transformarea cu­vântului a în b, trecând prin cuvinte in­ter­me­diare, existente în lista dată. Trecerea dintr-un cuvânt în altul se poate face folosind următoarele operaţii: schimbarea, adăugarea sau ştergerea unui singur caracter. Găsiţi cea mai scurtă secvenţă de operaţii care transformă primul cuvânt în cel de-al doilea folosind operaţiile permise. Cuvintele sunt formate numai din litere mici.
Exemplu:
a = “car” , b =  “mare”,  lista L = (cer, cerc, mar, rosu, inrosit, mere, cart, cere)
Cea mai scurtă soluţie: car, mar, mare

1. (Nota 6) Se citesc numerele naturale n şi S. Să se genereze toate şirurile de n numere naturale cu următoarele proprietăţi:
- suma numerelor din şir este S
- oricare două elemente aflate pe poziţii consecutive din şi au diferenţa în modul strict mai mare decât 1.
Exemplu: n=4, S = 14. Două soluţii sunt:
1 5 2 6
2 4 2 6

2. (Nota 8)  Se citeşte de la tastatură un număr natural n. Să se determine toate posibilităţile de a aşeza n dame pe o tablă de şah de dimensiuni n x n astfel încât oricare două să nu se atace. Două dame se atacă dacă se află pe aceeaşi linie, aceeaşi coloană sau pe aceeaşi diagonală.

3. (Nota 10) Se consideră două cuvinte a şi b şi o listă având n cuvinte. Se doreşte transformarea cu­vântului a în b, trecând prin cuvinte in­ter­me­diare, existente în lista dată. Trecerea dintr-un cuvânt în altul se poate face folosind următoarele operaţii: schimbarea, adăugarea sau ştergerea unui singur caracter. Găsiţi cea mai scurtă secvenţă de operaţii care transformă primul cuvânt în cel de-al doilea folosind operaţiile permise. Cuvintele sunt formate numai din litere mici.
Exemplu:
a = “car” , b =  “mare”,  lista L = (cer, cerc, mar, rosu, inrosit, mere, cart, cere)
Cea mai scurtă soluţie: car, mar, mare

Număr de accesări: 5141

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică