Permutacje



Funkcja rekurencyjna permutacji
Do utworzenia wszystkich możliwych permutacji pewnego ciągu można zastosować algorytm z nawrotami (tzw. backtracking). Najprostsza implementacja wypisuje permutacje nawet jeśli się duplikują.
Funkcja w C++

void permutuj(string slowo, int poz = 0)
{
     if (poz == slowo.size())
    {
            cout << slowo << endl;
    }
else {
     for (int i = poz; i < slowo.size(); i++) {
     swap(slowo[i], slowo[poz]);
     permutuj(slowo, poz + 1);
     swap(slowo[i], slowo[poz]);
}
}
 

Całość programu

 1 #include <iostream>
 2  #include <string>
 3  
 4  using namespace std;
 5  
 6  
 7  void permutuj(string slowo, int poz = 0)
 8  {
 9      if (poz == slowo.size())
10      {
11          cout << slowo << endl;
12      }
13      else
14      {
15          for (int i = poz; i < slowo.size(); i++)
16          {
17              swap(slowo[i], slowo[poz]);
18              permutuj(slowo, poz + 1);
19              swap(slowo[i], slowo[poz]);
20          }
21      }
22  }
23  
24  int main ()
25  {
26      string slowo;
27      cout << "Podaj wyrazenie:\n slowo = ";
28      cin >> slowo;
29      permutuj(slowo);
30  return 0;
31  }

ZADANIA / PROBLEMY




Zadania
  • Na ile sposobów możliwe jest rozmieszczenie liczb 1, 2, 3, 4, 5, 6, 7, 8 na wierzchołkach ośmiokąta tak, aby suma liczb znajdujących się w każdych trzech kolejnych wierzchołkach była większa od:
    a) 11
    b) 12
    c) 13
  • ocenę dostateczną otrzymuje uczeń, który poprawnie użył określonych w zadaniu narzędzi, lecz nie wykorzystał ich wszystkich możliwości, w końcowym dokumencie lub projekcie występują niedoskonałości wynikające z niedbałości lub nieumiejętnego korzystania z narzędzi edytora, ma problemy ze współpracą z członkami zespołu;
  • ocenę dobrą otrzymuje uczeń, który samodzielnie wykonuje zadanie, dobrze współpracuje z członkami zespołu, oddaje prace w określonym terminie, projekty mają drobne niedoskonałości, występują nieuzasadnione odstępstwa od założeń zadania;
  • ocenę bardzo dobrą otrzymuje uczeń: samodzielnie wykonujący ćwiczenie lub swoje zadania w zespole, oddający prace w wyznaczonym terminie, używający wszystkich możliwych opcji narzędzi do poprawy jakości wykonanej pracy, oddający prace estetyczne bez wad, zawierające niewpływające na jakość pracy błędy lub niedociągnięcia.

  • Wróć do spisu tematów