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:

 

 

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

 

 



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.