Backtracking – aranjamente

Să se genereze toate aranjamentele de n numere luate câte p. Se consideră mulţimea A={1,2,…n} şi un număr natural k, k < n. Se vor genera toate submulţimile mulţimii A care au k elemente, considerând submulţimi distincte cazurile având aceleaşi elemente dar poziţii diferite. Practic este necesară obţinerea tuturor combinărilor de k elemente din mulţimea A, iar pentru fiecare mulţime astfel obţinută se vor genera toate permutările ei.
#include “stdio.h”
int n,st[100],p,i;
//functia care ne va afisa intr-un final sirul
void afiseaza()
{
for(i=0;i < p;i++)   printf("%d", st[i]); } //functia care verifica daca elementele sunt diferite int valid() { for(i=1;i < k;i++)   if(st[i] == st[k])     return 0;   return 1; } void backtracking(int k) {   if(k > p)
    afiseaza();
  else
    for(i=0;i < n;i++)       {       st[k]=i;       if(valid(k))         backtracking(k+1);       } } int main() { printf("Numarul de elemente: "); scanf("%d", n); prinf("Numarul de moduri"); scanf("%d", p); backtracking(1); getch(); }

Leave a Reply

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

10 − 6 =

Time limit is exhausted. Please reload CAPTCHA.