Wprowadzenie do informatyki
Informatyka, I rok, studia dzienne i zaoczne
Egzamin poprawkowy, 23.02.00, czas: 60 min
  1. Funkcja f(x) jest zdefiniowana następująco:
    f(1) = A
    f(2n + j) = 2f(n) + g(j)    dla j = 0, 1 i n ≥ 1
    gdzie g(0) = B, g(1) = C.   A, B, C są parametrami funkcji f i mają wartości całkowite. Na przykład dla A=1, B=1, C= -2 mamy:

    x1234567
    f(x)130741-2

    Uzupełnij poniższy schemat blokowy tak, aby obliczał i drukował wartość f(x).

  2. Załóżmy, że na taśmie deterministycznej maszyny Turinga znajduje się skończony ciąg zer i jedynek rozpoczynający się od jedynki. Dane wejściowe można zatem przedstawić w następujący sposób:
    b0 b1 b2 ... bm              (2-1)
    gdzie m ≥ 1, b0 = 1, bi = 0, 1 dla i > 0. Należy skonstruować deterministyczną maszynę Turinga, która będzie obliczała cykliczne przesunięcie w prawo o 1 bit, czyli dla ciągu wejściowego (2-1) wygeneruje ciąg
    b1 b2 ... bm b0              (2-2)
    Zakładamy, że na początku głowica jest nad pierwszym elementem ciągu (2-1) a po zakończeniu obliczeń powinna się znaleźć nad ostatnim elementem ciągu (2-2) - w obu przypadkach jest to bit b0. Uzupełnij poniższy diagram sterowania.

  3. Tzw. problem Flawiusza można przedstawić następująco. Mamy n ludzi ponumerowanych od 1 do n i ustawionych w kręgu. Eliminować będziemy co drugą osobę, aż pozostanie tylko jeden człowiek. Niech np. początkowa konfiguracja dla n=10 wygląda następująco:
    Porządek eliminowania jest następujący: 2, 4, 6, 8, 10, 3, 7, 1, 9. Tak więc pozostanie osoba nr 5. Problem polega na podaniu dla danej liczby osób, n, numeru osoby, J(n), która pozostanie na końcu. Należy rekurencyjnie określić funkcję J(n) zakładając, że n= 1, 2, 4, .., 2k, ..

    UWAGA! Funkcja f(n) z zadania 1 rozwiązuje ten problem dla dowolnego n przy założeniu, że A= 1, B= -1, C= 1. Jednakże przy przyjętych ograniczeniach na wartość n funkcja J(n) ma znacznie prostszą postać.


  4. Załóżmy, że chcemy automatycznie generować formularze w HTML-u na podstawie pliku opisu formularza. Plik opisu zawiera:
    • wiersz z treścią pytania,
    • wiersze z wariantem odpowiedzi.
    Wiersz z treścią pytania jest to wiersz zawierający dowolne znaki, ale pierwszym znakiem różnym od spacji i tabulacji nie może być kropka. Wiersz wariantu odpowiedzi jest to wiersz zaczynający się od kropki, po której jest spacja i ciąg znaków nie zawierający spacji ani tabulacji. Oto przykładowy plik opisu formularza: 
    Ile jest 22 + 33?
.  44
.  55
.  66
    Na podstawie pliku opisu należy wygenerować formularz wysyłany na adres nawrocki@put.poznan.pl. Na przykład dla przedstawionego pliku opisu formularza powinniśmy otrzymać następujący tekst:

    <FORM METHOD="post" ACTION="mailto:nawrocki@put.poznan.pl">
    <P>
    Ile jest 22 + 33?
    <INPUT TYPE="radio" NAME="pyt" VALUE="44">44
    <INPUT TYPE="radio" NAME="pyt" VALUE="55">55
    <INPUT TYPE="radio" NAME="pyt" VALUE="66">66
    <INPUT TYPE="submit" VALUE="Wyślij">
    </FORM>

    Uzupełnij poniższy program w AWK tak, aby generował takie formularze. 

      BEGIN  {print "<FORM METHOD=\"post\" ACTION=\"mailto:nawrocki@put.poznan.pl\">";
          print"<P>"}

      END    {print"<INPUT TYPE=\"submit\" VALUE=\"Wyślij\">";
          print"</FORM>"}

  5. Dana jest funkcja 2-argumentowa nwd(a, b) obliczająca największy wspólny dzielnik dla pary liczb całkowitych dodatnich. Należy za jej pomocą obliczyć największy wspólny dzielnik dla zbioru n liczb całkowitych dodatnich a[1], a[2], .., a[n]. Na przykład największy wspólny dzielnik dla 32, 48 i 40 jest równy 8.

    Uzupełnij podany schemat blokowy. Zakładamy, że zawsze n ≥ 2.

Stronę opracował Jerzy Nawrocki. Ostatnia modyfikacja: