Koło olimpijskie

 

Zajęcia organizacyjne

Celem zajęć na kole olimpijskim jest przygotowanie uczniów do olimpiady informatycznej oraz do wszelkich innych konkursów, w których jest wymagana dobra umiejętność programowania komputerów w języku C++. Zajęcia będą obejmowały zakres materiału, który nie jest nauczany na lekcjach informatyki w szkole średniej. Wymaga zatem od uczestników dużo większej wiedzy od przeciętnego ucznia informatyki.

Zajęcia będą się odbywały w poniedziałki po 7-mej lekcji w sali komputerowej.

Podstawowym środowiskiem programowania będzie pakiet Code::Blocks, który jest ogólnie dostępny i darmowy w Internecie. Co więcej, pakiet ten daje się bez problemów zainstalować w środowisku Linux (takie jest w pracowni) oraz Windows (takie posiadają najczęściej uczniowie w swoich domach).

Przykładowe zadanie:

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:

 

obrazek

 

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

 

Rozwiązanie dla tablic

Tworzymy tablicę K o maksymalnym rozmiarze. Odczytujemy z wejścia liczbę kaczek n  oraz odstęp m. Następnie zerujemy wszystkie komórki tablicy.

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)2014 mgr Jerzy Wałaszek
// ACM - Jadłospis Aligatora
//-----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int K[99],n,m,lk,nk,i;

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

    if(!n || !m) break;

    // Zerujemy tablicę

    for(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(i = 0; i < m; i++)
        do
        {
          nk++;
          if(nk == n) nk = 0;
        } while(K[nk]);

      K[nk] = ++lk;
    }

    // Wyświetlamy zawartość tablicy

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

    cout << endl;
  }
  return 0;
}

 

 


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

©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe