Wstęp do programowania / Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 6 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
 
 
To są zadania na wskaźniki.
 
To są zadania na wskaźniki.
  
Linia 13: Linia 12:
 
# pobierz (usuwając) pierwszą liczbę ciągu.
 
# pobierz (usuwając) pierwszą liczbę ciągu.
 
Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe
 
Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe
są przydzielane i zwalniane w miarę potrzeby (zaletą tej implementacji jest to, że dość elastycznie dostosowuje się do aktualnego rozmiaru ciągu, nie wymagając tylu wskaźników, co zwykła lista).
+
są przydzielane i zwalniane w miarę potrzeby (zaletą tej implementacji jest to, że dość elastycznie dostosowuje się do aktualnego rozmiaru ciągu, nie wymagając tylu wskaźników co zwykła lista).
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Ze względu na cykliczne przesuwanie się ciągu w obrębie tablic wygodnie je wszystkie indeksować od zera.
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Ze względu na cykliczne przesuwanie się ciągu w obrębie tablic, wygodnie jest je wszystkie indeksować od zera.
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''const''' M = 100;
 
  '''const''' M = 100;
 
       D = 100;
 
       D = 100;
Linia 32: Linia 35:
 
  //wstawiamy liczbę do struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu,  
 
  //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
 
  //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  
+
  //Wstaw staje się false wtedy i tylko wtedy, gdy struktura S jest pełna  
 
  '''begin'''
 
  '''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'''
 
   '''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'''
Linia 50: Linia 53:
 
  //pobieramy liczbę ze struktury S (S.T[S.poczD]^[S.poczM] to pierwsza liczba w ciągu,  
 
  //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
 
  //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  
+
  //Pobierz staje się false wtedy i tylko wtedy, gdy struktura S jest pusta  
 
  '''begin'''
 
  '''begin'''
 
   '''if''' (S.konD=S.poczD '''and''' S.konM=S.poczM) '''then'''
 
   '''if''' (S.konD=S.poczD '''and''' S.konM=S.poczM) '''then'''
Linia 68: Linia 71:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 2 (Haszowanie)==
 
== Zadanie 2 (Haszowanie)==
Linia 77: Linia 80:
 
liczba), gdzie napis jest typu string, zaś liczba typu integer.
 
liczba), gdzie napis jest typu string, zaś liczba typu integer.
 
Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji
 
Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji
użyj tablicy [0..N] elementów odpowiedniego typu. Wstawianie ma polegać na obliczeniu klucz mod (N+1), jeśli pod tym indeksem jest wolne miejsce (-1), to wstawiamy, w przeciwnym przypadku szukamy liniowo (cyklicznie) pierwszego wolnego miejsca. Wyszukiwanie analogicznie. Zakładamy, że nigdy nie będzie wkładane więcej niż N elementów (to m.in. upraszcza wyszukiwanie indeksu dla danego klucza, zawsze jest co najmniej jedno wolne miejsce).
+
użyj tablicy [0..N] elementów odpowiedniego typu. Wstawianie ma polegać na obliczeniu klucz mod (N+1); jeśli pod tym indeksem jest wolne miejsce (-1), to wstawiamy, w przeciwnym przypadku szukamy liniowo (cyklicznie) pierwszego wolnego miejsca. Wyszukiwanie analogicznie. Zakładamy, że nigdy nie będzie wkładane więcej niż N elementów (to m.in. upraszcza wyszukiwanie indeksu dla danego klucza, zawsze jest co najmniej jedno wolne miejsce).
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Typ Dane to rekord z wariantami string i integer. Dane nie nadaje się na typ elementów tablicy; tam lepiej użyć rekord z wariantami
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Typ Dane to rekord z wariantami string i integer. Dane nie nadają się na typ elementów tablicy; tam lepiej użyć rekordu z wariantami
 
wskaźnik do napisu i liczba. Można by tak zdefiniować też Dane, ale nie widać ku temu powodów.
 
wskaźnik do napisu i liczba. Można by tak zdefiniować też Dane, ale nie widać ku temu powodów.
 
</div>
 
</div>
</div>}}
+
</div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''const''' N = 100;
 
  '''const''' N = 100;
 
  '''type''' rodzaj = (napis, liczba)
 
  '''type''' rodzaj = (napis, liczba)
Linia 140: Linia 146:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 3 (New i dispose dla typu T)==
 
== Zadanie 3 (New i dispose dla typu T)==
Linia 148: Linia 154:
 
# pole(-a) z pewnymi dodatkowymi informacjami (jakimi?)
 
# pole(-a) z pewnymi dodatkowymi informacjami (jakimi?)
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
W elementach tablicy albo trzymamy dane, albo indeks następnego wolnego elementu tablicy (trzeba jeszcze gdzieś pamiętać indeks pierwszego wolnego elementu).
 
W elementach tablicy albo trzymamy dane, albo indeks następnego wolnego elementu tablicy (trzeba jeszcze gdzieś pamiętać indeks pierwszego wolnego elementu).
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''const''' N = 100;
 
  '''const''' N = 100;
 
  '''type''' rodzaj = (pełny, pusty);  
 
  '''type''' rodzaj = (pełny, pusty);  
Linia 167: Linia 177:
 
Inicjalizacja T, funkcja NewT i procedura DisposeT:
 
Inicjalizacja T, funkcja NewT i procedura DisposeT:
 
  '''procedure''' InitT(var S:Str);
 
  '''procedure''' InitT(var S:Str);
  //wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje sie równy 1
+
  //wszystkie pola ustawiamy na puste, nast wskazują na następne pole lub zero; pierwszy staje się równy 1
 
  '''var''' i:integer;
 
  '''var''' i:integer;
 
  '''begin'''
 
  '''begin'''
Linia 177: Linia 187:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
  '''function''' NewT(var S:Str; var nowy:integer):boolean;
 
  '''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
+
  //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'''
 
  '''begin'''
 
   '''if''' S.pierwszy = 0 '''then'''  
 
   '''if''' S.pierwszy = 0 '''then'''  
Linia 200: Linia 210:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 4 (Sortowanie tablicy wskaźników do napisów)==
 
== Zadanie 4 (Sortowanie tablicy wskaźników do napisów)==
 
Dana jest tablica A typu array[1..N] of ^string. Posortuj tę tablicę, używając porządku leksykograficznego (słownikowego) na słowach. Załóż, że dana jest funkcja compare(s,t:string):boolean, która ma wartość true wtedy i tylko wtedy, gdy słowo s jest leksykograficznie mniejsze od słowa t.
 
Dana jest tablica A typu array[1..N] of ^string. Posortuj tę tablicę, używając porządku leksykograficznego (słownikowego) na słowach. Załóż, że dana jest funkcja compare(s,t:string):boolean, która ma wartość true wtedy i tylko wtedy, gdy słowo s jest leksykograficznie mniejsze od słowa t.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Użyj dowolnego algorytmu sortowania. Zamiast przesuwać obiekty, przesuwaj wskaźniki.
 
Użyj dowolnego algorytmu sortowania. Zamiast przesuwać obiekty, przesuwaj wskaźniki.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''procedure''' Sort(var A:array[1..N] of ^string);
 
  '''procedure''' Sort(var A:array[1..N] of ^string);
 
  //sortujemy leksykograficznie tablicę wskażników do słów
 
  //sortujemy leksykograficznie tablicę wskażników do słów
Linia 229: Linia 243:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>

Aktualna wersja na dzień 16:10, 28 maj 2020

To są zadania na wskaźniki.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__


Zadanie 1 (Tablica wskaźników do tablic)

Zaimplementuj strukturę danych reprezentującą ciąg liczb z operacjami:

  1. wstaw liczbę na koniec ciągu,
  2. pobierz (usuwając) pierwszą liczbę ciągu.

Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe są przydzielane i zwalniane w miarę potrzeby (zaletą tej implementacji jest to, że dość elastycznie dostosowuje się do aktualnego rozmiaru ciągu, nie wymagając tylu wskaźników co zwykła lista).

Wskazówka 1

Rozwiązanie 1

Zadanie 2 (Haszowanie)

Zaimplementuj strukturę danych z operacjami:

  1. Wstaw(klucz: integer; var d: Dane); (var zwiększa efektywność)
  2. Daj(var klucz: integer; var d: Dane);

Wstaw wstawia do struktury danych parę (klucz, napis) lub (klucz, liczba), gdzie napis jest typu string, zaś liczba typu integer. Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji użyj tablicy [0..N] elementów odpowiedniego typu. Wstawianie ma polegać na obliczeniu klucz mod (N+1); jeśli pod tym indeksem jest wolne miejsce (-1), to wstawiamy, w przeciwnym przypadku szukamy liniowo (cyklicznie) pierwszego wolnego miejsca. Wyszukiwanie analogicznie. Zakładamy, że nigdy nie będzie wkładane więcej niż N elementów (to m.in. upraszcza wyszukiwanie indeksu dla danego klucza, zawsze jest co najmniej jedno wolne miejsce).

Wskazówka 1

Rozwiązanie 1

Zadanie 3 (New i dispose dla typu T)

Zaimplementuj własne operacje new i delete dla elementów typu T. Użyj w tym celu tablicy [1..N] zawierającej rekordy z dwoma wariantami:

  1. pole typu T
  2. pole(-a) z pewnymi dodatkowymi informacjami (jakimi?)

Wskazówka 1

Rozwiązanie 1

Zadanie 4 (Sortowanie tablicy wskaźników do napisów)

Dana jest tablica A typu array[1..N] of ^string. Posortuj tę tablicę, używając porządku leksykograficznego (słownikowego) na słowach. Załóż, że dana jest funkcja compare(s,t:string):boolean, która ma wartość true wtedy i tylko wtedy, gdy słowo s jest leksykograficznie mniejsze od słowa t.

Wskazówka 1

Rozwiązanie 1