Zadanie z TI dla 1TEA (25.01.2011)

Temat: algorytm na scalanie ciągów uporządkowanych. Schemat blokowy.

Scalanie ciągów (łączenie) jest operacją połączenia dwóch uporządkowanych rosnąco (malejąco) ciągów elementów w jeden ciąg wynikowy, również uporządkowany rosnąco (malejąco).

Specyfikacja algorytmu scalania

Scalaj(i_p, i_s, i_k)

Dane wejściowe

d[ ] - scalany zbiór

i_p - indeks pierwszego elementu w młodszym podzbiorze, i_p N

i_s - indeks pierwszego elementu w starszym podzbiorze, i_s N

i_k - indeks ostatniego elementu w starszym podzbiorze, i_k N

Dane wyjściowe

d[ ] - scalony zbiór

Zmienne pomocnicze

p[ ] - zbiór pomocniczy, który zawiera tyle samo elementów, co zbiór d[ ].

i₁ - indeks elementów w młodszej połówce zbioru d[ ], i₁ N

i₂ - indeks elementów w starszej połówce zbioru d[ ], i₂ N

i - indeks elementów w zbiorze pomocniczym p[ ], i N

Zadanie: Napisz w zeszycie wszystkie kolejne kroki dla scalania ciągu 1 4 5 6 | 2 3 7 9

Ważne: zanim opuścisz pracownie komputerową, wyłącz komputer, połóż myszkę i klawiaturę na miejsce, dosuń krzesła do stołów.