Bella at 10:20, 2 October 2018

2018-10-02T10:20:18Z

New page

=== Permutari varianta recursiva ===

<syntaxhighlight>

#include <fstream>

using namespace std;

int n, st[16];
char folosit[16];

ifstream fin("permutari.in");
ofstream fout("permutari.out");

void tipar(){
for(int i = 1 ; i <= n ; i++)
fout << st[i] << " ";
fout << "\n";
}

void back( int k ){
if(k == n + 1) // daca am completat stiva pana la nivelul n
tipar(); // tiparim solutie
else // daca nu am completat solutia
for(int i=1 ; i<=n ; i++) // pun pe rand pe nivelul curent toate numerele de la 1 la n
if(!folosit[i]){ // daca val nu a fost folosita
folosit[i] = 1; // o marchez ca folosita in vectorul de frecvente
st[k] = i; // pun valoarea pe stiva
back(k+1); // trec pe nivelul urmator
folosit[i] = 0; // la reintoarcere din apelul recursiv, marchez ca nefolosita valoarea
}
}

int main(){
fin >> n;
back(1); //pornesc construirea solutiei de la nivelul 1
return 0;
}

</syntaxhighlight>
=== Optimizare cu liste - punem valori dintr-o lista cu numere inca nefolosite ===

<syntaxhighlight>
// Solutie pusa de Cella, a lui Cata?
#include <iostream>

using namespace std;
const int MAXN = 10;

int lst[MAXN], v[MAXN], list_len;

inline void delete_from_list(int pos) {
lst[pos] = lst[--list_len];
}

void add_to_list(int pos, int valoare) {
lst[list_len++] = lst[pos];
lst[pos] = valoare;
}

void generate_perm(int pos, int n) {
if (pos == n) {
for (int i = 0; i < n; ++i)
cout << v[i] << " ";
cout << '\n';
return;
}
for (int i = 0; i < list_len; ++i) {
v[pos] = lst[i];
delete_from_list(i);
generate_perm(pos + 1, n);
add_to_list(i, v[pos]);
}
}
int main(){
int n;
cin >> n;
for (int i = 0; i < n; ++i)
lst[i] = i + 1;
list_len = n;
generate_perm(0, n);
return 0;
}
</syntaxhighlight>

=== Aranjamente varianta recursiva ===
<syntaxhighlight>
#include <fstream>

using namespace std;

int n, p, st[16];
char folosit[16];

ifstream fin("aranjamente.in");
ofstream fout("aranjamente.out");

void tipar(){
for(int i = 1 ; i <= p ; i++)
fout << st[i] << " ";
fout << "\n";
}

void back( int k ){
if(k == p + 1) // daca am completat stiva pana la nivelul n
tipar(); // tiparim solutie
else // daca nu am completat solutia
for(int i=1 ; i<=n ; i++) // pun pe rand pe nivelul curent toate numerele de la 1 la n
if(!folosit[i]){ // daca val nu a fost folosita
folosit[i] = 1; // o marchez ca folosita in vectorul de frecvente
st[k] = i; // pun valoarea pe stiva
back(k+1); // reapelez functia pentru completarea nivelului urmator al solutiei
folosit[i] = 0; // inainte sa iau alta valoare pe nivelul curent, specific ca i nu mai e folosita
}
}

int main(){
fin >> n >> p;
back(1); // pornesc construirea solutiei de la nivelul 1
return 0;
}

</syntaxhighlight>

Temp isa - Revision history

Bella at 10:20, 2 October 2018