Metoda backtracking in generarea permutarilor

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

1. Să se genereze toate numerele de n cifre care nu conţin 3 numere alăturate identice.

2. Se citesc n şi k. Să se genereze toate permutările de mulţimii {1, 2…, n} care conţin exact k secvenţe crescătoare. De exemplu, pentru n=3 şi k=2, permutările sunt:
1 3 2
2 1 3
2 3 1
3 1 2

3. Se citesc numerele naturale n şi S. Să se determine, dacă există, o permutare p=(p1,p2,...pn) a mulţimii {1, 2…, n} astfel încât 1*p1 + 2*p2 + ... + n*pn = S.

4. Se citesc n, p, q. Să se genereze toate permutările mulţimii {1, 2…, n} care conţin exact p numere vizibile din stânga şi exact q numere vizibile din dreapta. Spunem că un număr este vizibil din stânga, dacă toate numerele din stânga sa sunt mai mici decât el. De exemplu, permutarea 3 1 5 4 2 are două numere vizibile din stânga şi trei din dreapta.

Număr de accesări: 5676

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ă

• 

  Neagu 11-10-2012 14:21:1

  Puteti sa ne spuneti cum se rezolva in C++?

• 

  Dan P. 12-10-2012 16:30:15

  Aici ai generarea permutărilor. Problemele din test sunt legate de aceasta.

  
  
#include<iostream>

using namespace std;

int a[20], n, viz[20];

void PrintSol()

{

int i;

for (i = 1; i <= n; i++)

cout << a[i] << " ";

cout << "\n";

}

void Back(int top)

{

int i;

if (top == n + 1) PrintSol();

else for (i = 1; i <=n; i++)

if (!viz[i])

{

viz[i] = 1;

a[top] = i;

Back(top + 1);

viz[i] = 0;

}

}

int main()

{

cout << "n = ";

cin >> n;

Back(1);

return 0 ;

}