Pierwsza kaczka zostanie pożarta jako piąta z kolei, drugą kaczkę aligator zje jako czwartą z kolei, itd. Ciąg 5 4 6 1 3 8 7 2 kolejności zjadania kaczek całkowicie określa jadłospis aligatora. Napisz program, który określi ten ciąg dla danych n  i m.

Teraz ustawiamy licznik zjedzonych kaczek lk  = 0 oraz numer kaczki do zjedzenia nk  = n  - 1 (jest to ostatnia pozycja w kręgu – chodzi o to, aby odliczanie kaczek rozpoczęło się od następnej, czyli pierwszej w kręgu).

W pętli dopóki lk  < n  wykonujemy cyklicznie operacje:

1. Wyznaczamy numer kaczki do zjedzenia. Operacja ta wykonywana jest następująco:
   m  razy powtarzamy w pętli:
       Zwiększamy nk  o 1. Jeśli nk  = n, to nk  = 0. Jeśli K[nk] > 0, to operację powtarzamy (kaczka zjedzona, więc jej pozycję należy pominąć).
   W ten sposób nk  wskaże kaczkę do zjedzenia.
2. Zwiększamy lk  o 1 (bo aligator zjada wyznaczoną przez nk kaczkę) i w komórce K[nk] umieszczamy lk (w ten sposób określimy, jako która z kolei będzie zjedzona kaczka na tej pozycji).

Dla n  = 8 i m  = 4:

lk  = 0
nk  = 7

lk  = 1
nk  = 3

lk  = 2
nk  = 7

lk  = 3
nk  = 4

lk  = 4
nk  = 1

lk  = 5
nk  = 0

lk  = 6
nk  = 2

lk  = 7
nk  = 2

lk  = 8 - koniec, tablica jest wypełniona.

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// ACM - Jadłospis Aligatora
// PRG_40
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int * K,n,m,lk,nk;

  while(true)
  {
    cin >> n >> m;    // Odczytujemy liczbę kaczek i krok

    if(!n || !m) break;

    // Tworzymy tablicę dynamiczną

    K = new int [n];

    // Tablicę zerujemy

    for(int i = 0; i < n; i++) K[i] = 0;

    // Inicjujemy dane

    lk = 0; nk = n - 1;

    // W pętli wyznaczamy kolejno jedzone kaczki

    while(lk < n)
    {
      for(int i = 0; i < m; i++)
        do
        {
          nk++;
          if(nk == n) nk = 0;
        } while(K[nk]);

      K[nk] = ++lk;
    }

    // Wyświetlamy zawartość tablicy

    for(int i = 0; i < n; i++)
      cout << setw(3) << K[i];

    cout << endl;

    // Usuwamy tablicę dynamiczną

    delete [] K;
  }

  return 0;
}

Elementy łączymy w listę wpisując w ich pola next adresy elementów następnych. Lista staje się cykliczna, gdy w polu next ostatniego elementu wpiszemy adres elementu pierwszego.

Lista posiada niewątpliwą zaletę – można z niej prosto usuwać elementy. Element usunięty nie jest już częścią listy i nie będzie odwiedzany. Usunięcie elementu polega na wpisaniu do pola next elementu poprzedzającego adresu z pola next elementu usuwanego. W ten sposób poprzedni element nie będzie już adresował usuniętego elementu, lecz jego element następny. Poniższy przykład pokazuje usuwanie elementu e₂.

Po tej operacji przejście przez listę omija element e₂.

Zasada działania zmodyfikowanego programu jest następująca:

1. Definiujemy strukturę elementu listy.
2. Odczytujemy w pętli n  i m. Jeśli któraś z tych liczb wynosi zero, to kończymy program.
3. Tworzymy dynamiczną tablicę elementów listy E o rozmiarze n. Z elementów tych tworzymy listę cykliczną, wpisując w ich pola next  adresy elementów następnych. Ostatni element w tablicy w polu next  musi zawierać adres pierwszego elementu E[0]. Pola data  w tym kroku nas nie interesują.
4. Tworzymy wskaźnik p  na element listy i ustawiamy go na ostatni element tablicy, czyli na E[n-1].
5. Tworzymy licznik zjedzonych kaczek lk  i ustawiamy go na zero.
6. Tworzymy pętlę, która będzie się wykonywać dotąd, aż lk  osiągnie wartość n, czyli aż nasz aligator pożre wszystkie n  kaczek.
7. W wewnętrznej pętli m  - 1 razy przechodzimy wskaźnikiem p  przez kolejne elementy listy. W ten sposób ustawimy p  na element (kaczkę oczywiście) poprzedzający element (też kaczkę), który będziemy usuwali z listy (czyli kaczkę zjadaną w tej kolejce przez żarłocznego aligatora matematyka).
8. Zwiększamy lk  o 1.
9. W usuwanym elemencie wprowadzamy lk  do pola data. Jest to numer zjadanej kaczki.
10. Element usuwamy (jest to element następny do tego, który na liście wskazuje p).
11. Kontynuujemy pętlę z kroku 6 aż do wyczerpania wszystkich kaczek
12. Teraz wystarczy przeglądnąć kolejne elementy tablicy E i wypisać ich pola data.
13. Tablicę E usuwamy i kontynuujemy pętlę z kroku 2.

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// ACM - Jadłospis Aligatora II
// PRG_41
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja elementu listy
//-------------------------
struct list_element
{
  list_element * next;
  int data;
};

int main()
{
  list_element * E;  // dynamiczna tablica elementów listy cyklicznej
  list_element * p;  // wskaźnik elementów listy
  int n,m,i,lk;

  // W pętli wyznaczamy kolejne rozwiązania

  while(true)
  {
    cin >> n >> m;      // odczytujemy liczbę kaczek n oraz odstęp m

    if(!n || !m) break;

    // Tworzymy tablicę dynamiczną

    E = new list_element [n];

    // Tworzymy listę cykliczną

    for(i = 0; i <= n - 2; i++) E[i].next = &E[i+1];
    E[n-1].next = &E[0];

    // Rozpoczynamy ucztę aligatora

    p = &E[n-1];   // wskaźnik elementu poprzedzającego element usuwany

    lk = 0;        // licznik zjedzonych kaczek

    while(lk < n)
    {
      // Ustawiamy p na element poprzedzający "kaczkę do zjedzenia"

      for(i = 0; i < m - 1; i++) p = p->next;

      // Do "zjadanej kaczki" zapisujemy jej numer

      p->next->data = ++lk;

      // "Zjedzoną kaczkę" usuwamy z listy

      p->next = p->next->next;
    }

    // Wypisujemy numery zjedzonych kaczek

    for(i = 0; i < n; i++) 
      cout << setw(3) << E[i].data;
    cout << endl;

    // Tablicę-listę usuwamy z pamięci

    delete [] E;
  }

  return 0;
}