Problem A - Zagadka z kołków
Problem B - Dziesiętne ułamki okresowe
Problem C - Zamiana liczb arabskich na rzymskie
Problem D - Poprawki szybkościomierza

 

1979

Problem A - Zagadka z kołków


Opis

Mała zagadka, która stała się popularna w różnych restauracjach, składa się z trójkątnego kawałka drewna z przewierconymi w nim 15 otworami. Numeracja oraz układ tych otworów są  następujące:

 

 

Zagadka rozpoczyna się od drewnianych kołków w 14 otworach. Celem jest "skakanie i usuwanie" 13 z tych kołków, kończąc z tylko jednym kołkiem pozostałym na planszy. Reguły są następujące:

  1. Kołek można przesunąć tylko skokiem ponad innym kołkiem w wolny otwór, zbijając przeskoczony kołek.
  2. Wolno przeskakiwać tylko przez sąsiedni kołek, który jest połączony linią z kołkiem, który skacze.
  3. Skok musi w całości odbyć się wzdłuż łączącej linii i jej przedłużenia.
  4. Skok można wykonać tylko wtedy, gdy bezpośrednio za przeskakiwanym kołkiem znajduje pusty otwór.

Daje to 36 potencjalnych ruchów, które zebrano w poniższej tabeli:

 

Kołek
na pozycji
przeskakuje
kołek
na pozycji
i ląduje
w pustym otworze
na pozycji
01 02 04
04 02 01
01 03 06
06 03 01
02 04 07
07 04 02
03 06 10
10 06 03
04 07 11
11 07 04
06 10 15
15 10 06
11 12 13
13 12 11
12 13 14
14 13 12
13 14 15
15 14 13
02 05 09
09 05 02
03 05 08
08 05 03
04 05 06
06 05 04
04 08 13
13 08 04
05 08 12
12 08 05
07 08 09
09 08 07
05 09 14
14 09 05
06 09 13
13 09 06
08 09 10
10 09 08

 

Program ma odczytać początkowy układ kołków na planszy. Układ ten jest opisany za pomocą 15 cyfr dwójkowych, gdzie "1" oznacza, że otwór odpowiadający pozycji cyfry zawiera w sobie kołek, a "0" oznacza, że jest on pusty - będzie 14 cyfr o wartości "1" oraz jedna cyfra "0". Program ma następnie obliczyć i wypisać ciąg ruchów, które kończą się jednym kołkiem pozostałym na planszy. Taki ciąg będzie istniał dla początkowej konfiguracji, którą program napotka w trakcie oceniania.

 

Specyfikacja wejścia

Na wejściu program będzie otrzymywał ciąg wierszy z cyframi binarnymi, które określają konfigurację planszy. Cyfry są numerowane od strony lewej do prawej.. W każdym wierszu będzie dokładnie 15 cyfr. Pierwsza cyfra określa otwór nr 1, ostatnia cyfra określa otwór nr 15. Wiersz końcowy będzie się składał z 15 zer. Po napotkaniu wiersza końcowego program ma zakończyć działanie.

 

Specyfikacja wyjścia

Dla każdego zestawu konfiguracji planszy program ma wyznaczyć ciąg ruchów, które prowadzą do rozwiązania zagadki - po wykonaniu tych ruchów na planszy ma pozostać tylko jeden kołek. Każdy ruch ma być opisany następująco:

 

PEG AT n1 JUMPS PEG AT n2 AND MOVES TO n3

n1 - pozycja kołka, którym wykonujemy skok
n2 - pozycja kołka, nad którym przeskakujemy - ten kołek zostanie usunięty z planszy
n3 - pozycja otworu, w którym ląduje skaczący kołek

 

Po wypisaniu wszystkich ruchów w danym ciągu program powinien wypisać trzy puste wiersze i przejść do analizy kolejnego zestawu danych lub zakończyć działanie w przypadku otrzymania w danych wejściowych 15 zer.

 

Przykładowe dane wejściowe

111101111111111
000000000000000

 

Przykładowe dane wyjściowe

PEG AT 14 JUMPS PEG AT  9 AND MOVES TO  5
PEG AT  7 JUMPS PEG AT  8 AND MOVES TO  9
PEG AT 10 JUMPS PEG AT  9 AND MOVES TO  8
PEG AT 12 JUMPS PEG AT 13 AND MOVES TO 14
PEG AT  3 JUMPS PEG AT  6 AND MOVES TO 10
PEG AT 15 JUMPS PEG AT 10 AND MOVES TO  6
PEG AT  2 JUMPS PEG AT  4 AND MOVES TO  7
PEG AT  6 JUMPS PEG AT  5 AND MOVES TO  4
PEG AT  7 JUMPS PEG AT  4 AND MOVES TO  2
PEG AT  1 JUMPS PEG AT  2 AND MOVES TO  4
PEG AT  4 JUMPS PEG AT  8 AND MOVES TO 13
PEG AT 14 JUMPS PEG AT 13 AND MOVES TO 12
PEG AT 11 JUMPS PEG AT 12 AND MOVES TO 13

 



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.