ZADANIA DRUGIEGO ETAPU

Zadania drugiego etapu II Warszawskiego Konkursu Informatycznego
rok szkolny 1995/96

Zadanie 1.

Zdefiniuj dwuparametrową funkcję AB :n :m, której wartością jest losowo utworzone słowo, złożone z :n liter A i :m liter B. Wywołanie funkcji AB z parametrami odpowiednio :n równym 2 i :m równym 3 zwróci jako wartość jedno z dziesięciu słów, jakie można utworzyć z dwóch liter A i trzech liter B, np. AABBB lub BABAB.

Zadanie 2.

Każdą trasę na kwadratowej siatce (n+1)*(n+1), która:

  • składa się z poziomych i pionowych odcinków łączących sąsiednie punkty na siatce,
  • zaczyna się od lewego dolnego i kończy w prawym górnym rogu siatki,

można zakodować za pomocą odpowiedniego słowa złożonego z n liter A i m liter B. Przyjmujemy, że litera A jest kodem odcinka trasy biegnącego pionowo z dołu do góry, zaś litera B kodem odcinka biegnącego poziomo w prawo.

Poniższe rysunki przedstawiają wywołania POPRZEK "ABAABBBAAABBBBAA oraz POPRZEK "ABBBBAAAAABBABBA.

Napisz jednoparametrową procedurę POPRZEK :kod, która dla dowolnego słowa danego jako wartość parametru :kod sprawdza, czy składa się ono z tej samej liczby n liter A i B. Jeśli nie (np. dla POPRZEK "ABBBBAAAA), to procedura powinna wypisać na ekranie komunikat: "niepoprawne dane", jeśli tak, powinna narysować na ekranie kwadratową siatkę (n+1)*(n+1) kropek, a na niej trasę, której kodem jest dane słowo. Zakładamy, że dane słowo będzie się składało z co najwyżej 16 liter, wyłącznie z wielkich A lub B.

Zadanie 3.

Poniższy rysunek przedstawia mapę rzędu 3:

Mapa rzędu n jest kwadratową siatką kropek, utworzoną z 2n+1 poziomych rzędów po 2n+1 kropek w każdym rzędzie. Środkowe punkty na zachodniej, północnej, wschodniej i południowej krawędzi mapy oznaczamy odpowiednio literami W, N, E oraz S.
Trasa WNESW nazywamy każdą trasę na mapie spełniającą trzy warunki:

  • składa się z jednostkowych poziomych i pionowych odcinków, łączących sąsiednie punkty na mapie,
  • zaczyna się w punkcie W, następnie biegnie do N, do E, do S i wraca do W,
  • ma minimalną długość.

Mówimy, że trasa WNESW jest regularna, jeśli po jej obrocie o 90o dookoła środka mapy otrzymamy tę samą trasę. Poniższy rysunek przedstawia przykładowe regularne trasy na mapie rzędu 3:

Napisz procedurę TRASA_REG :n, która dla dowolnej wartości parametru :n, nie mniejszej niż 1 i nie większej niż 6:

  • rysuje na ekranie mapę rzędu :n,
  • wykreśla na niej w sposób losowy regularną trasę WNESW.

Procedurę należy napisać w taki sposób, aby każda regularna trasa WNESW mogła być efektem jej wywołania.