Backtracking – permutarile

Soluţia se va genera sub forma unui vector. Abordarea este asemănătoare cu cea a construirii unui mecanism de tip stivă. Astfel, primul element X[1] se va găsi pe primul nivel al stivei, X[2] pe nivelul 2 iar elementul X[k] se va găsi pe nivelul al stivei. În cadrul generării permutărilor, vom ţine cont de faptul că orice permutare va fi alcătuită din elemente distincte ale mulţimii valorilor de la 1 la n.


#include "stdio.h"
#include "conio.h"
int stiva[20],n,k;
//funcţia care tipăreşte soluţia
void tipareste()
{
  int i;
  for(i=1;i <= n;i++)     printf("%d ", stiva[i]);   putchar("\n"); }

//funcţia care returnează adevărat dacă elementul curent aşezat în stivă nu se
//regăseşte pe nici unul din nivelurile anterioare
int valid()
{
  int i;
  for(i=1;i < k;i++)     //dacă valoarea încărcată se găseşte pe unul din nivelurile     // anterioare returnăm 0 (fals)     if(stiva[i] == stiva[k])       return 0;     else       return 1; void permutari() {   //pornim de la nivelul 1   k=1;   //k va descreşte până la valoarea o, când se încheie algoritmul   while(k > 0)
  //dacă mai există valori posibile pentru elementul curent
  if(stiva[k] < n)   {     //generăm o nouă valoare     stiva[k]++;     //dacă elementul aşezat este valid     if(valid() == 1)       if (k == n)         //dacă am ajuns la ultimul nivel afişăm soluţia         tipareste();       else       //dacă nu am ajuns la final       {         //urcăm în stivă pentru a aşeza un nou element         k++;         //iniţializăm noul nivel cu 0         stiva[k]=0;       }     }     //când nu mai există posibilitatea de a aşeza un element     //pe nivelul curent revenim pe nivelul anterior în stivă     else       k--; } void main(void) {   printf("Introdu valoarea lui n:");   scanf("%d",&n);   permutari();   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

nine + 3 =

Time limit is exhausted. Please reload CAPTCHA.