ASD, wykład, K2

Ćwiczenia

1. Przecinanie się odcinków

Dano cztery punkty na płaszczyźnie A(1,2), B(3;5), C(5,1), D(2,4). Pokazać czy odcinki AB i CD przecinają się. Przedstawić proces rozwiązania (na odwrocie kartki).

TAK / NIE (niepotrzebne skreślić)

1 krok. Obliczenie wyznaczników dla punktów ABC, ABD, CDA, CDB:

det(ABC) = (x_ay_b + x_by_c + x_cy_a) - (x_cy_b + x_by_a + x_ay_c) = 1*5+3*1+5*2 - 5*5-3*2-1*1 = -14

det(ABD) = (x_ay_b + x_by_d + x_dy_a) - (x_dy_b + x_by_a + x_ay_d) = 1*5+3*4+2*2 - 2*5-3*2-1*4 = 1

det(CDA) = (x_cy_d + x_ay_c + x_dy_a) - (x_ay_d + x_dy_c + x_cy_a) = 5*4+1*1+2*2 - 1*4-2*1-5*2 = 9

det(CDB) = (x_cy_d + x_by_c + x_dy_b) - (x_by_d + x_dy_c + x_cy_b) = 5*4+3*1+2*5 - 3*4-2*1-5*5= -6

Wniosek: Żaden wyznacznik nie jest równy 0, a więc żadne trzy punkty nie SA współliniowe

2 krok. Porównanie znaków wyznaczników parami:

sign(det(ABC)) <> sign(det(ABD)) and
sign(det(CDA)) <> sign(det(CDB))

po podstawieniu wartości:

sign (-14) <> sign (1) and sign (9) <> sign (-6) jest prawdą!

Wniosek: odcinek AB przecina odcinek CD

2. Reprezentacja grafów

4. Dano graf:: Przedstawić inne reprezentacje tego grafu.

a) macierz sąsiedztwa:

b) lista krawędzi:

c) lista incydencji:

Macierz sąsiedztwa

	A	B	C	D	E	F
A		1				1
B	1					1
C				1		1
D			1		1
E				1		1
F	1	1	1		1

Lista krawędzi:

A-B, A-F, B-F, C-D, C-F, D-E, E-F

Lista incydencji:

A	B,F
B	A,F
C	D,F
D	C,E
E	D,F
F	A,B,C,E

3. Wyszukiwanie wzorca

Dano tekst: ABBBABAAABABBABAA

Oraz wzorzec: ABBA

Ile razy w trakcie wyszukiwania wzorca w tekście dojdzie do porównania liter zgodnie z algorytmem Brute-Force

↓↓↓↓↓↓↓↓↓↓↓

ABBBABAAABABBABAA

ABBA | +4

ABBA | +1

ABBA | +1

ABBA | +1

ABBA | +3

ABBA | +1

ABBA | +2

ABBA | +2

ABBA | +3

ABBA | +1

ABBA | +4

________________________

| 23

Dano tekst: Carpe diem quam minimum credula postero

Oraz wzorze:c nimum

Ile razy w trakcie wyszukiwania wzorca w tekście dojdzie do porównania liter zgodnie z algorytmem BM (Boyera-Moora)

Carpe diem quam minimum credula postero

nimum | +1

nimum | +2

nimum | +1

nimum | +1

nimum | +5

___________________________________________

10

4. Lista 2-kierunkowa

Dano listę 2-kierunkową zawierająca n-elementów. Każdy element posiada składową wskażnik1 wskazujący następnika, oraz wskażnik2 wskazujący poprzednika. Mamy dostęp do specjalnego elementu Head wskazującego na pierwszy element listy. Podać algorytm wstawiania nowego elementu w k-tej pozycji listy, przy k = [1...n+1]. W trakcie wstawiania można korzystać tylko z jednej dodatkowej zmiennej POMOC wskazującej na element listy

Wstawianie w środku:

void Wstaw(T_lista *BIEZACY, typ_danych x)

{ T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));

nowy->dane=x;

nowy->wskaznik1=BIEZACY->wskaznik1; //2

nowy->wskaznik2=BIEZACY; //3

BIEZACY->wskaznik1=nowy; //4

nowy->wskaznik1->wskaznik2=nowy; //5 }

Wstawianie na początku

void Wstaw(T_lista **HEAD,typ_danych x)

{ T_lista *nowy=(T_lista *)malloc(sizeof(T_lista));

nowy->dane=x; nowy->wskaznik1=*HEAD;

nowy->wskaznik2=NULL; *HEAD=nowy; }

---