W Przyszłym roku w programach niektórych szkół pojawi się nowy przedmiot — elementy informatyki. Już dzisiaj jednak setki tysięcy młodych ludzi (sądząc po powodzeniu BAJTKA jest ich tylu z pewnością) swój wolny czas spędzają przy komputerze, ucząc się współpracy z nim i świadomego jego wykorzystania. Racjonalna wydaje się więc myśl o daniu im szansy rywalizacji, wykazania się inwencją i umiejętnościami, po prostu sprawdzenia się.
Niestety, w bieżącym roku szkolnym olimpiady takiej nie udało się zorganizować, mimo że najbardziej z urzędu zainteresowane instytucje: Polskie Towarzystwo Informatyczne, Ministerstwo Oświaty i Wychowania, Naczelna Organizacja Techniczna i Towarzystwo Kultury Technicznej w pełni zgadzają się co do potrzeby takiego konkursu. BAJTEK postanowił przejąć inicjatywę i doprowadzić jeszcze w tym roku do spotkania zainteresowanych instytucji, tak by pierwsza olimpiada mogła odbyć się już w roku szkolnym 1986/87. O jego wynikach i podjętych decyzjach poinformujemy już wkrótce!
Tymczasem proponujemy Wam zapoznanie się z zasadami konkursowymi podobnych olimpiad odbywających się w innych krajach. Jeśli postanowicie spróbować swych sił i rozwiązać publikowane dziś zadania — chętnie zapoznamy się z wynikami Waszych dociekań. Najlepsze z nich opublikujemy.
Ocenę rozwiązań obniżają pomyłki oraz algorytmy z nadmierną liczbą działań lub blokami, bez których można się obejść. Dopuszczalne są rozwiązania w dowolnym języku programowania. Rozwiązanie należy poprzedzić słownym objaśnieniem algorytmu, a ponadto w tekście programu powinny znajdować się niezbędne komentarze. Programy powinny być uporządkowane zgodnie z regułami programowania strukturalnego.
A oto zadania:
- Rozkład na składniki: Wypisać wszystkie sposoby przedstawienia liczby naturalnej n w postaci sumy liczb naturalnych. Permutacje składników nie są traktowane jako sposoby różne.
- Równe elementy. Dana jest macierz liczb P (l:m, l:n). Każdy wiersz macierzy uporząd kowany jest rosnąco. Znaleźć i wypisać liczbę, która występuje we wszystkich wierszach lub słowo NIE, jeśli liczba taka nie istnieje.
- Nierozkładalna liczba. Dany jest podzbiór liczb naturalnych M(l:n). Znaleźć i podać najmniejszą liczbę naturalną nie będącą sumą elementów zbioru. Suma ta w szczególnym przypadku może się składać tylko z jednego składnika, każdy element zbioru może się w niej znaleźć tylko raz.
- Czworościany. Na ścianach dwóch jednakowych czworościanów prawidłowych wypisano odpowiednio liczby M1, M2, M3, M4 na jednym oraz N1, N2, Ń3, N4 na drugim (w podanej kolejności). Gzy można nałożyć na siebie czworościany w ten sposób, by na pokrywających się ścianach znalazły się jednakowe liczby?
- Najczęściej występująca liczba. W zbiorze liczb M (l:n) znaleźć liczbę występującą najczęściej. Jeśli ich jest kilka — podać jedną z nich.
- Systemy liczbowe. Zbiór liczb całkowitych M(l:9) zawiera cyfry przedstawienia pewnej liczby naturalnej w systemie liczbowym o podstawie i (tzn. M (1) oznacza liczbę jedności w tym przedstawieniu tej liczby itd.). Należy przedstawić tę liczbę w systemie liczbowym o podstawie j, gdzie liczby i i j nie są większe od 10.
- Przekątna boczna. Znaleźć sumę elementów A (i, j) macierzy A (l:m, l:n), mających stałą różnicę indeksu i–j=k. Liczba k jest całkowita, ale niekoniecznie dodatnia.
- Wyjaśnienia: Macierz P (l:m, l:n) oznacza macierz Pij dla i=l, 2, ...,m oraz j=l...,n natomiast zapis P (i, j) — element Pij. Przez formułowania „dana jest macierz P (I:m, l:n)” należy rozumieć, że dane są liczby m, n i „wartości elementów macierzy.
W rozwiązaniach dane wartości należy wprowadzać z zewnątrz i drukować je. Pożądane jest posługiwanie się programami (w ALGOLU — procedura, w FORTRANIE — subroutine itd.). W tych językach, w których wymiary macierzy należy zadawać liczbowo, np. w FORTRANIE, można je określić dowolnie.
„Dobre rozwiązania” dla dużych liczb danych powinny składać się z dokładnością do stałego czynnika z następującej liczby działań: m n (zadanie 2), n2 lub n log n (zadania 3 i 5), min. m, n (zadanie 7).
Federalne Ministerstwo Nauki i Oświaty RFN ogłosiło (pod osobistym patronatem pani minister Dorothee Wilms) IV Federalny Konkurs Informatyczny 1985. Bezpośrednimi organizatorami konkursu są Federalne Towarzystwo Matematyczne i Przetwarzania Danych oraz Federalne Towarzystwo Informatyczne. To ostatnie liczy sobie 8500 członków — podaję dla zilustrowania, że w krajach zachodnich informatycy nie są wcale tak liczni — różnica w efektach wynika z intensywności pracy i uzbrojenia technicznego informatyków.
Pierwsza seria zadań konkursowych ogłoszona została 1 września 1985 r., a rozwiązania należało nadsyłać do 15 listopada. Druga runda — dla tych, którzy poprawnie rozwiązali zadania pierwszej serii — przewidziana jest w okresie luty—kwiecień 1986 r., a finały na specjalnym spotkaniu uczestników w sierpniu 1986 r.
Organizatorzy oczekiwali, że rozwiązania zadań zawierać będą: ideę rozwiązania, dokumentację programu, protokół testowego przebiegu programu i oczywiście listę rozkazów.
- Jak to zaprogramowano? Rysunki 1 przedstawiają wynik trzykrotnego wykonania programu z dwoma parametrami: KĄT i LICZBA, przy podanych wartościach tych parametrów. Napisz program dający takie właśnie rezultaty oraz wykonaj go dla KĄTA równego 70° i LICZBY równej 9.
- Jam Mata Hari, Bond i Kloss. Rozszyfrować tekst: CD RDBAOE OZSOYFADWZNE TAURND DRSOYFADWZC, wiedząc, że jest to zdanie w języku polskim, w którym pięć naj–częściej występujących liter przetasowano (poddane permutacji), a pozostałe znajdują się bez zmian na swoich właściwych pozycjach. Przykład: tytuł zadania po zaszyfrowaniu brzmi: JMI IMTM HMRA BSND A KLSOO, po podstawieniu M za A, I za M oraz A za I i zamienieniu miejscami S i O. Napisany przez Was program powinien odczytywać dowolny tekst zaszyfrowany według tej zasady, przy czym rozpoznawanie, która z możliwych permutacji prowadzi do sensownego odczytania, można pozostawić użytkowników.
- Sterowanie ramieniem robota. Należy przesunąć koniec ramienia robota z punktu P1 do punktu P2. przy czym punkty te nie muszą leżeć na jednej płaszczyźnie. Ramię robota składa się z trzech części o długości 130 cm każda (niezła łapa, co?) i trzech przegubów. Pierwszy z nich (Gl) pozwala ramieniu obracać się wokół osi pionowej (od 0 do 90°), natomiast drugi (G2) i trzeci (G3) wokół osi poziomej — odpowiednio od 0 do 270° i od 0 do 180° (patrz rysunek 2). Sterowanie ramieniem robota odbywa się przy pomocy rozkazu TWIST (i, j, k), gdzie i, j. k mogą przyjmować wartości –1, 0 i 1°. Dla przykładu rozkaz TWIST (0, –1, 1) oznacza pozostawienie przegubu Gl bez zmian, podczas gdy pozostałe kąty będą odpowiednio zmniejszone i zwiększone o 1° (oczywiście dopóki nie zostaną osiągnięte kąty graniczne — w takim wypadku odpowiedni rozkaz jest ignorowany).
- Napiszcie program, który przesuwa ramię robota z punktu x1, y1, z1 do punktu x2, y2, z2 lub możliwie blisko tego drugiego punktu (położenie punktu określone jest we współrzędnych kartezjańskich). Przetestuj swój program m.in. dla przypadku P1 = (100 cm, 0, 0) i P2 = (100 cm, 100 cm, 0)...
- Postaraj się zapisać swój program w taki sposób, by czubek ramienia robota poruszał się w miarę możliwości po prostej (to są dwa różne zadania — w pierwszym dopuszczamy ruch inną drogą, jeśli pozwoliłoby to uprościć program).
- Analiza kursów giełdowych. Treść tego zadania tak dalece nie ma odniesień w naszej rzeczywistości, że pomijamy je w BAJTKU
- Symulacja sieci oporników. Bierzemy pod uwagę sieci spełniające następujące warunki:
- Sieć jest płaska (tj. nie występują „dwupoziomowe” skrzyżowania przewodów).
- Połączenia z ziemią poprowadzone są poprzez potencjometry ustawione w taki sposób, by danymi odgałęzieniami płynął z góry zadany prąd.
- Dopuszczalne są różne napięcia całkowite i różne wartości oporów.
- W węzłach mogą się schodzić więcej niż trzy przewody.
- Podajcie program, który będzie obliczał rozkład prądów i napięć w takiej sieci i wyświetlał wyniki w postaci przejrzystej tablicy. Wypróbujcie działanie tego programu m.in. dla sieci podanej na rysunku (3).
Opr.
Władysław Majewski