Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Metoda backtracking

Test de progres backtracking

Notă: Problemele se va rezolva utilizându-se metoda backtracking. Se vor preciza mai întâi lungimea stivei, valorile depuse pe stivă, criteriul de validare. Se va scrie apoi programul complet.

1. Se citeşte un număr natural n. Să se afişeze toate şirurile de lungime n, fiecare şir îndeplinind condiţiile:
  a. şirul este format numai cu cifrele 1, 2, 3
  b. în şir nu există două cifre alăturate identice
  c. cifra 2 trebuie obligatoriu să fie aşezată între o cifră 1 şi o cifră 3.
De exemplu, pentru n=3, trei astfel de şiruri sunt:
1 2 3
1 3 1
3 2 1
Afişaţi la final şi numărul soluţiilor.

2. Se citeşte un număr natural n şi apoi un şir a1, a2, ..., an de numere naturale. Se mai citeşte un număr natural k < n. Să se afişeze toate subşirurile crescătoare de lungime k ale şirului.
De exemplu, pentru n = 6, k =4 şi şirul 5, 3, 7, 8, 1, 9 se vor afişa 5,7,8,9 şi 3, 7, 8, 9.

3. Se citesc două numere naturale S şi p. Să se scrie toate şirurile de p numere naturale nenule, fiecare şir având proprietăţile:
  a. suma elementelor din şir este S
  b. elementele şirului sunt distincte
  c. oricare două elemente aflate pe poziţii impare au aceeaşi paritate
De exemplu, pentru n = 10 şi p=3 trei astfel de şiruri sunt:
1 2 7
1 4 5
3 2 5
De remarcat că şirul 1 3 6 nu este soluţie pentru că 1 şi 6 sunt pe poziţii impare în şir şi au parităţi diferite.
Afişaţi la final şi numărul soluţiilor.

Despre autor
Author

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ă

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =