Koło informatyczne - ciekawe zadanie ACM

1974

Problem C - Dolna liga


Opis

Załóżmy, że na stawie unosi się n kaczek tworzących koło. W stawie mieszka również aligator, który uwielbia jeść kaczki. Rozpoczynając od określonej pozycji (kaczka nr 1) aligator liczy w koło i zjada każdą m-tą kaczkę (koło się zamyka w miarę zjadania kaczek). Na przykład, gdy n = 8, a m = 4, to poniższy schemat pokazuje numery kaczek na zewnątrz węzła oraz kolejność ich zjadania wewnątrz węzła:

 

 

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.

 

Specyfikacja wejścia

Wejście składa się z ciągu wierszy. W każdym wierszu są dwie liczby rozdzielone spacją. Liczby te określają kolejno n - liczbę kaczek (n > 0, n < 100), m - odstęp (m > 0, m < 100). Ostatni wiersz posiada obie liczby n i m równe 0.

 

Specyfikacja wyjścia

Dla każdego wiersza danych program powinien wypisać wiersz z ciągiem liczb, które określają numery kolejno zjadanych kaczek. Każda liczba na wydruku ma zajmować 3 znaki z cyframi dosuniętymi do prawej krawędzi pola.

 

Przykładowe dane wejściowe

8 4
10 3
0 0

 

Przykładowe dane wyjściowe

  5  4  6  1  3  8  7  2
  6  4  1 10  8  2  5  7  3  9

Przykładowe rozwiązania

Odczytujemy z wejścia liczbę kaczek n oraz odstęp m. Następnie tworzymy tablicę dynamiczną K o rozmiarze n i zerujemy jej wszystkie komórki.

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

komórka  0   0   0   1   0   0   0   0 
indeks 0 1 2 3 4 5 6 7
        nk        

 

lk = 1
nk = 3

komórka  0   0   0   1   0   0   0   2 
indeks 0 1 2 3 4 5 6 7
                nk

 

lk = 2
nk = 7

komórka  0   0   0   1   3   0   0   2 
indeks 0 1 2 3 4 5 6 7
          nk      

 

lk = 3
nk = 4

komórka  0   4   0   1   3   0   0   2 
indeks 0 1 2 3 4 5 6 7
    nk            

 

lk = 4
nk = 1

komórka  5   4   0   1   3   0   0   2 
indeks 0 1 2 3 4 5 6 7
  nk              

 

lk = 5
nk = 0

komórka  5   4   6   1   3   0   0   2 
indeks 0 1 2 3 4 5 6 7
      nk          

 

lk = 6
nk = 2

komórka  5   4   6   1   3   0   7   2 
indeks 0 1 2 3 4 5 6 7
              nk  

 

lk = 7
nk = 2

komórka  5   4   6   1   3   8   7   2 
indeks 0 1 2 3 4 5 6 7
            nk    

 

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;
}

 

Podany powyżej algorytm nie jest specjalnie efektywny. Program musi wciąż wielokrotnie przechodzić przez wykorzystane elementy w tablicy (czyli pomijać kaczki, które wcześniej zjadł aligator). Aby poprawić efektywność działania programu, musimy zmodyfikować strukturę danych, która przechowuje numery kolejno zjedzonych kaczek.

Lista cykliczna jednokierunkowa

Lista (ang. list) jest dynamiczną strukturą danych. Oprócz danych każdy element listy zawiera pole, które wskazuje element następny. Nazwijmy to pole next. Jest ono wskaźnikiem, czyli adresem następnego elementu na liście. Pole data przechowuje dane – u nas będzie to numer zjedzonej kaczki.

 

 

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 e2.

 

 

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

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;
}

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.