Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Tłumaczył: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Rok konkursu ACM |
Tematy zadań konkursu |
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:
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.
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.
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.
111101111111111 000000000000000 |
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 |
Gdy x i y są liczbami całkowitymi, liczba wymierna x/y posiada postać dziesiętną:
iiii.fffff... |
Jeśli od pewnego miejsca wszystkie dalsze cyfry f są zerami, to zwykle opuszcza się je i można zapisać dokładny odpowiednik dziesiętny danej liczby wymiernej. Inaczej ciąg cyfr ułamkowych (f = fraction) jest nieskończony, lecz w końcu stanie się powtórzeniami pewnego podciągu. Oznaczając powtarzający się podciąg za pomocą literek r, okresowy ułamek dziesiętny używa następującej notacji:
iii.fffff(r1...rk) |
w celu zapisu okresowego odpowiednika nieskończonego ułamka dziesiętnego:
iii.fffffr1...rkr1...rkr1...rk... |
Na przykład:
22 | = 3.(142857) | 5 | = 0.41(6) | 100 | = 9.(09) |
7 | 12 | 11 |
Zwróć uwagę, że powtarzany ciąg cyfr znajduje się na końcu zapisu liczby i występuje tylko w części ułamkowej.
Napisz program, który:
Na wejściu program otrzymuje ciąg wierszy. W każdym wierszu znajdują się dwie nieujemne liczby całkowite x i y, rozdzielone spacją. W ostatnim wierszu druga z liczb jest równa zero. Po napotkaniu ostatniego wiersza program kończy działanie. Liczby x i y będą posiadały co najwyżej 10 cyfr.
Dla każdego wiersza wejściowego z niezerową liczbą y program powinien wypisać trzy wiersze o następującej postaci:
x ---------- = iii.fff(rrr) y |
gdzie
x, y - wejściowe liczby całkowite i - cyfry całkowite f - cyfry ułamkowe r - cyfry okresu |
27836 462 1 252 2 17 300030003 16 0 0 |
27836 ---------- = 60.(251082) 462 1 ---------- = 0.00(396825) 256 2 ---------- = 0.(1176470588235294) 17 300030003 ---------- = 18751875.1875 16 |
Cesarz rzymski właśnie otrzymał wiadomość od angielskiego króla. Jednakże cesarz nie rozumie liczb arabskich. Napisz program, który przetłumaczy wszystkie wartości liczbowe na liczby rzymskie, pozostawiając bez zmian resztę znaków w łańcuchu tekstowym.
Program otrzyma ciąg wierszy z wiadomością dla cesarza rzymskiego. Wyrazy w wierszach mogą być dzielone. Jednakże wszystkie liczby znajdują się w całości w swoim wierszu. Każda z liczb jest większa od 0 i mniejsza niż 4000. Liczby są dodatnie, całkowite i nie posiadają wewnątrz siebie żadnych znaków interpunkcyjnych. Wiadomość kończy się parą znaków ##.
Do konwersji wykorzystaj poniższą tabelkę:
Cyfry arabskie |
Cyfry rzymskie |
1 2 3 4 5 6 7 8 9 10 20 30 50 90 100 140 500 1000 |
I II III IV V VI VII VIII IX X XX XXX L XC C CXL D M |
Program powinien wypisać kolejno wszystkie wczytane wiersze, w których liczby arabskie są zastąpione liczbami rzymskimi. Tekst otaczający te liczby nie powinien być zmieniony.
PLEASE ADVISE BY 19 OCTOBER, 1001. ## |
PLEASE ADVISE BY XIX OCTOBER, MI. ## |
Szybkościomierz samochodowy jest połączony z napędem samochodu i zamienia liczbę obrotów na sekundę wału silnika na prędkość w milach na godzinę. Lecz od czasu do czasu wielkość opony zmienia się, maleje, gdy zużywa się bieżnik, rośnie, gdy jest gorąco, jej rozmiar zależy od ilości powietrza w dętce, itd. W konsekwencji, jeśli nawet szybkościomierz dokładnie mierzy liczbę obrotów na sekundę, to jego odczyty mogą się różnić od prędkości, z jaką podróżuje samochód. Rogatki oraz niektóre z międzystanowych dróg posiadają ustawione słupy milowe wzdłuż jezdni. Jeśli kierowca utrzymuje prędkość samochodu na ustalonym odczycie z prędkościomierza, a pasażer mierzy okresy czasu pomiędzy słupami milowymi, to rzeczywista prędkość samochodu może być obliczona. Program ma wypisać liczbę sekund pomiędzy słupami milowymi dla samochodu jadącego z prędkościami 10, 20, 30, 40, 50, 60, 70 i 80 mil na godzinę, zaokrągloną do najbliższej sekundy. (Droga s jest powiązana z prędkością v i czasem t zgodnie ze wzorem s = vt.) Prędkość jest w milach na godzinę, zatem będziesz musiał pomnożyć prędkość w milach na godzinę przez odpowiedni współczynnik, aby zmienić ją na prędkość w milach na sekundę.
Średnica toczna opony wynosi około 29 cali dla pełnowymiarowego samochodu oraz 25 cali dla małego samochodu osobowego. Obwód jest równy średnicy pomnożonej przez liczbę π. Program ma określić i wypisać liczbę obrotów wykonanych przez każdą z opon po przejechaniu przez samochód jednej mili (w każdej mili jest 5280 stóp) zaokrągloną do najbliższego obrotu. Program powinien również określić i wypisać liczbę obrotów na sekundę każdej z dwóch opon, gdy samochód porusza się z szybkością 30, 50, 70 i 90 mil na godzinę.
π = 3.1415926535897932385 |
Załóżmy, że średnica opony różni się o -10%, -5%, -1%, +1%, +5% lub +10% od średnicy założonej przy kalibracji szybkościomierza. Program ma określić i wypisać rzeczywistą prędkość, gdy odczyt prędkościomierza ma wartość 50, 60, 70, 80 lub 90 mil na godzinę dla każdego z tych błędów i dla każdego rozmiaru opony z dokładnością do najbliższej dziesiątej części mili na godzinę.
Dane produkowane przez program powinny być jasno opisane. Tam gdzie jest to możliwe należy zastosować tabele.
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.