Ćwiczenia 01: wstęp

Zadanie o przecinających się prostokątach - na płaszczyźnie dane są dwa prostokąty o bokach prostopadlych do osi. Wyznacz ich przecięcie.

Wskazówki do rozwiązania:

Zastanówmy, czym może być rozwiązanie. Odpowiedź zależy od tego, czy prostokąty są otwarte, czy domknięte. Ustalmy dla ułatwienia, że otwarte. Wtedy są możliwe dwa typy wyników: zbiór pusty lub prostokąt o bokach prostopadłych do osi.

Kolejne pytanie: jak reprezentować dane i wyniki. Dane, to dla każdego prostokąta 4 liczby rzeczywiste (albo całkowite, jeśli chcemy to robić na kratkach) reprezentujące współrzędne wierzchołków przy przekątnej. Wygodnie jest od razu ustalić, że chodzi o konkretną przekątną, np. tę która idzie w prawo w górę.

Zatem zadanie przyjmuje taką treść: Danych jest 8 liczb rzeczywistych: a1,b1,a2,b2,a3,b3,a4,b4. Punkty o współrzędnych (a1,b1) i (a2,b2) są wierzchołkami prostokąta P1, zaś (a3,b3), (a4,b4) prostokąta P2, przy czym a1 < a2, b1 < b2, a3 < a4, b3 < b4.

Ćwiczenia 02: Flaga polska

Dziś - zadanie o fladze polskiej.

Treść: Danych jest M urn, numerowanych od 1 do M, każda zawierająca żeton biały lub czerwony. Robot ma za zadanie tak poprzestawiać urny z żetonami, aby wśród kolejnych urn najpierw były te, które mają czerwone żetony, a potem te, które mają białe żetony. Do dyspozycji ma dwie funkcje:

• Kol(i) określającą kolor żetonu w i-tej urnie
• Z(i,j) zamieniającą urnę i-tą z j-tą.

Uwaga: robot może się zepsuć, jeśli każe się mu sięgnąć poza zakres 1..n lub zamienić urnę i-tą z i-tą.

Ćwiczenia 03: Zadanie o fladze holenderskiej

Tym razem mamy w N urnach żetony 3 kolorów: czerwone, białe i niebieskie i chcemy je poprzestawiać tak, aby końcowo były ułożone w tej właśnie kolejności.

Wskazówka: Postaraj się zachować następujący niezmiennik: \( N(c,b,n)=\forall 1\le k < c: Kol(k)=czerwony \land \forall c \le k \le b: Kol(k)=biały \land \forall n < k \le N: Kol(k)=niebieski \land 1\le c \le b \le n+1 \le N+1 \).

Ćwiczenia 04: Sortowanka

Tym razem sortowanie danych małego rozmiaru: 0,1,2,3,4,5 elementów. Postaraj się to zrobić optymalnie, czyli za pomocą najmniejszej możliwej liczby porównań. Kolejno są to liczby 0,0,1,3,5,7, przy czym posortowanie 5 elementów za pomocą 7 porównań należy uznać za sukces.

Ćwiczenia 05: Zadanie o najdłuższym plateau

Znajdź najdłuższy segment stały w tablicy. Rozważ dwa warianty: tablica posortowana i nieposortowana.

Ćwiczenia 06: Arytmetyka dużych liczb

Dziś mnożenie i dzielenie dużych liczb. Podobnie jak na poprzednich ćwiczeniach liczby trzymamy w tablicach indeksowanych od 0 do n-1 i w przypadku przepełnienia wyniku sygnalizujemy to.

Dla dużych liczb x zapisanych w tablicy typu liczba=array [0..N-1] of Integer robimy procedury i funkcje
1. function Zero(const x:liczba):Boolean; sprawdzająca zerowość liczby x
2. function Większe(const x,y:liczba):Boolean; sprawdzająca czy x>y
3. procedure Dodaj(var x:Integer; const y:liczba); dodającą do liczby x wartość y
4. procedure Odejmij(var x:Integer; const y:liczba); odejmującą od liczby x wartość y

Ćwiczenia 07: Mnożenie i dzielenie z resztą dużych liczb

Dziś Iloczyn i - jesli się da - dzielenie z resztą. Tak jak na poprzednich zajęciach sygnalizujemy przepełnienie, jeśli wystąpi.

Ćwiczenia 08: Zadanie o segmencie z największą sumą elementów

Napisz funkcję znajdującą w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.

Ćwiczenia 09: Gramatyki (1)

Na ćwiczeniach nr 9 zaczynamy zadania z gramatyk. Podaj gramatykę generującą

1. Wszystkie słowa w \( \in {a,b}*\) t. że #(a,w)<>#(b,w)
2. Wszystkie słowa w \(\in {a,b}* \)poza abababb .
3. Języki typu \(a^n b^k c^m\) takie, że n,k,m spełniają jakieś
   równania/nierówności liniowe np
   • n+k=m
   • n+m=k
   • n+m=k+1
   • n+m<>k
   • n+2m=k+2
     itp.
4. Język nawiasów kwadratowych i okrągłych; kwadratowych nie można umieszczać wewnątrz okrągłych.
5. Wyrażenia boolowskie

Ćwiczenia 10: Gramatyki (2)

1. Wszystkie słowa w \in {a,b}* t. ze #(a,w)<>#(b,w)
2. Wszystkie słowa w \in {a,b}* poza abababb.
3. Języki typu a^n b^k c^m takie, że n,k,m spełniają poniższe równania/nierówności liniowe
n+k=m n+m=k n+m=k+1 n+m<>k n+2m=k+2
4. Język nawiasów kwadratowych i okrągłych; kwadratowych nie można umieszczać wewnątrz okrągłych.
5. wyrażenia arytmetyczne z prawostronnie łącznym potęgowaniem, czyli że np.
x*y^z^v parsuje się jako x*(y^(z^v))

Ćwiczenia 11: Gramatyki(3)

Wygeneruj słowa nad alfabetem {a,b}

1. o parzystej liczbie a
Na przykład taka jednoznaczna:
S ::= aBaS | bS | e
B ::= bB | e

2. gdzie żadne dwa a nie występują obok siebie
Na przykład taka jednoznaczna:
S ::= aB | B
B:= e | bS

3. gdzie nigdzie więcej niż dwa a nie może wystąpić koło siebie
Na przykład taka (jednoznaczna):
S::= aaB | aB | B
B ::= e | bS
Uzasadnienie: wprowadzamy nowy "symbol" aa, który nie może wystąpić koło a.

4. gdzie żadne słowo nie jest postaci \(a^nb^na^n \)

Ćwiczenia 12: Wyszukiwanie binarne (1)

Ćwiczenia 13:Wyszukiwanie binarne (2)

Zadanie 1
Oblicz ile jest wystąpień x w posortowanej tablicy A.

Wskazówka: da się to zrobić w czasie logarytmicznym.

Zadanie 2
Znajdź maksimum w ciągu bitonicznym, czyli takim, że istnieje 1<=k<=n takie, że dla każdego 1 < j<=k A[j-1] < A[j] oraz dla każdego k < j <=n A[j-1] > A[j]. Uwaga: ciąg bitoniczny może być ciągiem rosnącym (lub malejącym) i wtedy największy element jest w A[n] (odpowiednio A[1]).

Zadanie 3.
Pokaż, że nie da się znaleźć w czasie logarytmicznym maksimum w ciągu słabo bitonicznym, czyli takim, że wszystkie nierówności są nieostre.

Zadanie 4
Tablicę posortowaną rosnąco przesunięto cyklicznie w prawo o k. Wyznacz najmniejsze k, które mogło spowodować takie przesunięcie (dla k >= n oczywiście przesunięcie się zacykla mod n).

Ćwiczenia 14: Zadanie o dwóch medianach

Zadanie o dwóch medianach. Tej samej długości tablice A i B:array[1..n] of Integer są posortowane rosnąco i zawierają rozłączne wartości. Ze względu na to, że łączna liczba elementów jest parzysta, możemy dwa środkowe co do wartości elementy spośród nich uznać za mediany: małą m i dużą M. Wyznacz je. (chodzi o element n-ty i n+1-wszy co do wartości w obu tablicach łącznie).

Oczywiście chodzi o to, żeby zrobić to w czasie logarytmicznym.

Ćwiczenia 15: Przesunięcie cykliczne tablicy

Przesuń tablicę o k elementów w prawo. (Zadanie nr 9 z Wazniaka, ćwiczenia nr 2: tablice)

Ćwiczenia 16: Wieże Hanoi

Na wykładzie były wieże Hanoi. Proponuję zrobić takie zadania wariantowe:

1. Wieże Hanoi z zabronionym przejściem między wieżą 1 i 2.

2. Wieże Hanoi z zabronionym przejściem między wieżą 1-->2, 2-->3, 3-->1, czyli można tylko w jednym kierunku przenosić krążki

3. Wieże Hanoi z zabronionym przejściem między wieżą 1-->3 oraz 3-->1, czyli wieża 1 i 3 mają kontakt jedynie z 2 i wszelki transfer między nimi musi odbywać się przez pośrednika.

4. Wieże Hanoi ogólne z informacją z której wieży na którą można przenosić zadaną za pomocą logicznej tablicy dasie[i,j] dla i,j=1,2,3.

Ćwiczenia 22: (Listy 2)

Zadanie 1

Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.

Dodatkowe warianty:

• który z kolei wyleci interesujący nas numer j?
• jaki numer bedzie m-ty od końca? (podstawowe zadanie jest dla m=1)

Zadanie 2

Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).

Zadanie 3

Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.

Zadanie 4

Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.

Ćwiczenia 22: Listy (2)

Zadanie 1

Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.

Zadanie 2

Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).

Zadanie 3

Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.

Zadanie 4

Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.

Ćwiczenie 17: Rekursja (2)

Zadanie główne

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy liczb naturalnych większych od zera ustawionych w kolejności nierosnącej.
Np. dla n = 3:
3 = 3
3 = 2+1
3 = 1+1+1

Wskazówka 1
Użyj dodatkowej tablicy do przechowywania początków rozkładów. Uważaj, aby nie kopiować tej tablicy przy każdym wywołaniu rekurencyjnym!

Wskazówka 2
Funkcja rekurencyjna powinna mieć parametr wskazujący jak duże składniki mogą być użyte do rozkładu pozostałej liczby.

Zadanie 2

Analogicznie, tylko że interesuje nas liczba podziałów na sumy składników będących liczbami Fibonacciego. Można oczywiscie zawczasu stablicować sobie liczby Fibonacciego. To będzie rzecz jasna prosta modyfikacja podanego rozwiązania.

Zadanie 3

Analogicznie, tylko że liczby Fibonacciego muszą być różne.

Ćwiczenia 18: Binaria (1)

Zaczynamy od reprezentacji liczb całkowitych. Przyjmijmy jako podstawowe jednobajtowe liczby w kodzie U2. Zadania:

1. Znajdź reprezentację binarną w U2 liczb (przykładowo:)
0 00000000
4 00000100
-4 11111100
-1 11111111
127 01111111
-127 10000001
-128 10000000

2. Jaką liczbę reprezentują (przykładowo)
00000101 5
01010101 85
10101010 -86 (jak się doda do poprzedniej to wyjdzie -1)

3. Liczby wymierne: znajdź reprezentację okresową liczb
1/128 0.0000001(0)
3/128 0.0000011(0)
1/7 0.(001)
3/11 0.(0100010111)
7/13 0.(1000010011101)

4. Liczby w kodzie binarnym o podstawie (-2)
Znajdź reprezentację w tym kodzie liczb z przedziału (-20..20):
+ -
0 0
1 1 11
2 110 10
3 111 1101
4 100 1100
5 101 1111
6 11010 1110
7 11011 1001
8 11000 1000
9 11001 1011
10 11110 1010
11 11111 110101
12 11100 110100
13 11101 110111
14 10010 110110
15 10011 110001
16 10000 111000
17 10001 111011
18 10110 111010
19 10111 111101
20 10100 111100
itd. Warto zwrócić uwagę na urodę reprezentacji liczb 11 oraz -10. :)

5. Napisz algorytm znajdujący taką reprezentację dla dowolnej liczby całkowitej
6. Napisz algorytm dodający jedynkę do liczby zapisanej w tym układzie - reprezentujemy liczbę w tablicy bitowej.
7. Porównaj dwie liczby dane w dwóch tablicach bitowych
8. Zaneguj liczbę zamazując wynikiem oryginalną wartość w tablicy bitowej

Ćwiczenia 19: Binaria (2)

Zaczynamy od przykładów reprezentowania liczb w notacji zmiennopozycyjnej z wykładu (jest opisana na ważniaku), czyli 3 bity na cechę i 4 na mantysę bez ukrywania bitu 1/2 i z roznormalizowaniem wartości dla najmniejszej cechy 100 (chodzi o to, że przy najmniejszej cesze pozwalamy na mantysy mniejsze co do modułu od 1/2; nie tracimy w ten sposób jednoznaczności zapisu liczby, bo i tak mniejszej cechy nie ma).

Zaczynamy od prostych ułamków skończonych. Przedstaw w podanej reprezentacji możliwie dobre przybliżenia liczb:

5/8
5/16
5/128
5/256
5/512
5/1024
5/2028 (czyli zero)

Potem ułamki okresowe:

2/7:
3/7:
1/5
1/10
1/11
1/13

Dalej ćwiczymy dodawanie
1/11 + 1/13 =
1/13+5/8 =

Następnie robimy zadania 1-3 z wazniaka: http://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania/Reprezentacja_liczb/Ćwiczenia. Omawiamy błąd względny wykonanych obliczeń i zauważamy, że jest on rzędu 2^{-t}

Ćwiczenia 20: wskaźniki

const M = 100;
      D = 100;
type Tab = array[0..D-1] of ^array[0..M-1];
     Str = record 
       T:Tab;
       poczD,konD, poczM, konM:integer;
     end;

function Wstaw(var S:Str; liczba: integer):boolean;
//wstawiamy liczbę do struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu, 
//S.T[S.konD]^[S.konM] to pierwsze wolne miejsce w S
//Wstaw staje się false wtedy i tylko wtedy, gdy struktura S jest pełna 
begin 
  if (S.konD=S.poczD and S.konM+1=S.poczM) or ((S.konD+1) mod D = S.poczD and S.konM=M-1 and S.poczM=0) then 
    Wstaw:=false
  else begin 
    Wstaw:=true;
    if S.konM = 0 and S.poczD <>S.konD then New(S.T[S.konD]);
    S.T[S.konD]^[S.konM]:=liczba;
    S.komM:=(S.komM+1) mod M;
    if S.konM=0 then S.konD:=(S.konD+1) mod D;
  end;
end;

function Pobierz(var S:Str; var liczba: integer):boolean;
//pobieramy liczbę ze struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu, 
//S.T[S.konD]^[S.konM] to pierwsze wolne miejsce w S
//Pobierz staje się false wtedy i tylko wtedy, gdy struktura S jest pusta 
begin 
  if (S.konD=S.poczD and S.konM=S.poczM) then 
    Pobierz:=false
  else begin 
    Pobierz:=true;
    liczba:=S.T[S.poczD]^[S.poczM];  
    S.poczM:=(S.poczM+1) mod M;
    if S.poczM=0 then begin 
      if S.konD <> S.pocz then Dispose(S.T[poczD]);
      S.poczD:=(S.poczD+1) mod D;
    end;
  end;
end;

const N = 100;
type rodzaj = (napis, liczba)
     Dane = record 
       case co:rodzaj of
         napis: (s:string)
         liczba: (l:liczba)
       end;
     Eltab = record
       klucz:integer; 
       case co:rodzaj of
         napis: (wsk:^string)
         liczba: (l:liczba)
       end;
var T: array[0..N] of Eltab

procedure Wstaw(klucz: integer; var d: Dane); 
//wstawiamy dane z d do tablicy T na pierwsze wolne miejsce, zaczynając od indeksu klucz mod (N+1)
//zakładamy, że są wolne miejsca w tablicy T 
var k:integer;
begin
  k:=klucz mod (N+1);
  while T[k].klucz <> -1 do k:=(k+1) mod (N+1);
  T[k].klucz:=klucz;
  T[k].co:=d.co;
  case d.co of
    napis: New(T[k].wsk); T[k].wsk^:=d.s;
    liczba: T[k].l:=d.l
  end; 
end;

function Daj(klucz: integer; var d: Dane):boolean;
//pobieramy liczbę lub napis z tablicy T skojarzonych z kluczem klucz
//zakładamy, że są wolne miejsca w tablicy T 
var i:integer;
begin
  k:=klucz mod (N+1); 
  while T[k].klucz <> klucz and T[k].klucz <> -1 do k:=(k+1) mod (N+1);
  if T[k].klucz = -1 then
    Daj:=false
  else begin
    Daj:=true;
    d.co:=T[k].co;
    case d.co of
      napis: d.s:=T[k].wsk^;
      liczba: d.l:=T[k].l;
    end;
  end; 
end;

const N = 100;
type rodzaj = (pełny, pusty); 
     Eltab = record 
       case rodzaj of
         pełny: (d:T)
         pusty: (nast:integer)
       end;
     Str = record 
       T:array[1..N] of Eltab;
       pierwszy:integer;
     end;

procedure InitT(var S:Str);
//wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje się równy 1
var i:integer;
begin
  for i:=1 to N do S.T[i].nast:=(i+1) mod (N+1);
  S.pierwszy:=1;
end;

function NewT(var S:Str; var nowy:integer):boolean;
//nowy to indeks któregoś z dotychczas pustych pól w S.T; jeśli takich nie ma, to New będzie miało wartość false
begin
  if S.pierwszy = 0 then 
    New:=false
  else begin
    New:=true;
    nowy:=S.pierwszy;
    S.pierwszy:=S.T[S.pierwszy].nast;
  end;
end;

procedure DisposeT(var S:Str; d:integer);
//zwalniamy indeks d w tablicy S.T
begin
  S.T[d].nast:=S.pierwszy;
  S.pierwszy:=d;
end;

Ćwiczenia 21: Listy (1)

Zadanie 1. Utwórz listę z konkretnych 3 elementów, np 2,3,5.

zadanie 2: Utwórz listę zawierającą wartości z tablicy A[1..n] of integer.

Zadanie 3. Odwróć listę

Zadanie 4. Scalanie posortowanych list. Chodzi o przekierowanie wskaźników dwóch posortowanych list tak, aby powstała jedna posortowana lista.

Zadanie 5. Napisz procedurę Usuń(var l1:lista; l2:lista) która usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są posortowane niemalejąco.

Tutaj musimy ustalić, jak rozumiemy zadanie w zależności od tego, co robimy z elementami powtarzającymi się na jednej bądź drugiej liście.

a) Załóżmy najpierw, że usuwamy wszystkie elementy z l1, które mają choć jedną wspólną wartość z jakimś elementem l2.

b) A teraz usuńmy elementy na zasadzie odejmowania multizbiorów reprezentowanych przez te listy, czyli z listy l1 usuwamy tylko tyle wartości, ile ich jest na l2.

Zadanie 6. Flaga holenderska na liście
Niech czerwone, to są elementy ujemne, białe równe zero, a czerwone - dodatnie. Przestaw listę tak, aby wszystkie ujemne liczby poprzedzały zerowe, a te z kolei dodatnie.