Perfekcyjne Tasowanie

Algorytm

Perfekcyjne Tasowanie polega na podzieleniu talii kart na dwie, równe połowy, a następnie wstawienie kart z drugiej połowy do pierwszej w taki sposób, że pierwsza karta z drugiej połowy jest po pierwszej karcie z pierwszej i tak dalej dla każdej kolejnej pary kart. Przykładowo:

Jak można zauważyć pierwszy i ostatni element w takim tasowaniu nie zmieniają pozycji. W tablicy wynikowej zgodnie z algorytmem tasowania elementy na indeksach nieparzystych są z pierwszej połowy tablicy wejściowej, a z parzystych z drugiej połowy. Należy oczywiście pamiętać, że algorytm ten pasuje jedynie do tablic o parzystej długości!

Tasowanie kilka razy

Okazuje się, że dla określonej liczby kart w talii po k tasowaniach uzyska się oryginalny układ elementów w talii. Jednak dla różnej ilości kart możliwe, że będzie potrzebna inna ilość tasowań. Za każdym razem tasowanie jest wykonywane opisywanym algorytmem. Kontynuując podany wcześniej przykład otrzymujemy:

W przypadku talii o n = 8 kartach otrzymujemy oryginalny układ kart w tablicy. Jak się jedna okazuje dla 6 kart potrzeba, aż 4 tasowań czyli tyle samo co dla 16 kart. Jednak dla talii o 12 elementach trzeba powótrzyć tasowanie, aż 10 razy! Najbardziej odporna na tasowanie jest oczywiście talia złożona z dwóch kart, gdzie po jednym tasowaniu otrzymujemy.. to samo ułożenie.

Implementacja

Tasowanie

Poniższa funkcja perfekcyjneTasowanie() przyjmuje jako argument listę liczb, a jako wynik zwraca tą listę potasowaną zgodnie z algorytmem tasowania perfekcyjnego. Werjściowa tablica nie jest modyfikowana.

1. static List<int> perfekcyjneTasowanie(List<int> v) {
2.   List<int> w = new List<int>();
3.   int polowa = v.Count / 2;
4.   for (int i = 0; i < polowa; i++) {
5.     w.Add(v[i]);
6.     w.Add(v[polowa + i]);
7.   }
8.   return w;
9. }

Przedstawiony algorytm na początku deklaruje nową liste, a następnie dla każdej pary liczb (z dwóch różnych połówek) dodawane są do nowej listy. Na koniec zwracana jest nowa lista.

Testowanie funkcji

W celu przetesowania funkcji wystarczy poniższy fragment kodu. Należy pamiętać, że zarówno ten kod jak i napisana funkcja nie sprawdzają poprawności danych wejściowych czyli np. czy przekazana długość tablicy jest parzysta.

1. static void Main(string[] args) {
2.   Console.Write("Ile jest kart?\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   List<int> v = new List<int>();
5.   for (int i = 0; i < n; i++)
6.     v.Add(i);
7.   List<int> w = perfekcyjneTasowanie(v);
8.   for (int i = 0; i < n; i++)
9.     Console.Write("{0} ", w[i]);
10.   Console.ReadKey();
11. }

Ile tasowań?

Korzystając z przygotowanej wyżej funkcji perfekcyjneTasowanie() można napisać funkcję ileTasowan(), która zwróci ile razy trzeba przetasować listę, aby otrzymać z powrotem oryginalną listę. W tym jednak przypadku jako argument podawany jest jedynie ilość elementów, a nie ich konkretne wartości.

1. static int ileTasowan(int n) {
2.   int ile = 0;
3.   List<int> v = new List<int>();
4.   for (int i = 0; i < n; i++)
5.     v.Add(i);
6.   bool pokolei = false;
7.   while (!pokolei) {
8.     ile++;
9.     v = perfekcyjneTasowanie(v);
10.     pokolei = true;
11.     for (int i = 0; i < n; i++) {
12.       if (v[i] != i) {
13.         pokolei = false;
14.         break;
15.       }
16.     }
17.   }
18.   return ile;
19. }

Na podstawie przekazanej wartości n funkcja sama generuje tablicę do potasowania. Zaletą takiego rozwiązania jest uproszczony system sprawdzania czy otrzymano z powrotem tablicę wejściową, ponieważ wszystkie elementy w tablicy to kolejne liczby nieujemne, więc wystarczy sprawdzić, że na i-tej pozycji jest wartość i.

Testowanie funkcji

W celu przetestowania kodu wystarczy wczytać od użytkownika liczbę i wypisać wynik:

1. static void Main(string[] args) {
2.   Console.Write("Ile jest kart?\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   Console.WriteLine(ileTasowan(n));
5.   Console.ReadKey();
6. }

• Kod źródłowy Tasowanie
• Kod źródłowy Ile tasowań?

Zadania

Zadanie 1

Rozszerzmy definicję perfekcyjnego tasowania i przyjmijmy, że możn tasować tablice o nieparzystej liczbie elementów. Przykładowo jeśli mamy posortować tablice o 2n+1 elementach to w pierszej części będzie ich n + 1, a w drugiej n. Elementy drugiej tablicy powinny znaleźć się pomiędzy kolejnym parami elementów z tablicy pierwszej. Przykładowo dla n = 5:

Napisz funkcję perfekcyjneTasowanie() oraz ileTasowan() dla nowej definicji tasowania. Przetestuj napisane funkcje.

• Kod źródłowy Zadanie 1