ASD Ćwiczenia 5: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
Linia 27: Linia 27:
 
=='''Zadanie 3'''==
 
=='''Zadanie 3'''==
  
Zaproponuje algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.
+
Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.
  
  
Linia 40: Linia 40:
 
2) <math>x_3</math> z <math>x_4</math>
 
2) <math>x_3</math> z <math>x_4</math>
  
3) porównanie mniejszych elementów z każdej z par
+
3) porównanie mniejszych elementów z każdej z par.
  
 
</div>
 
</div>
Linia 53: Linia 53:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Wykorzystaj fakt, ze każdy <math>n</math>-wierzchołkowy graf spójny zawiera co najmniej <math>n-1</math> krawędzi.
+
Wykorzystaj fakt, że każdy <math>n</math>-wierzchołkowy graf spójny zawiera co najmniej <math>n-1</math> krawędzi.
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 21:13, 3 gru 2006

Zadanie 1

Narysuj drzewo decyzyjne sortujące 4 elementy, którego wysokość wynosi .

Wskazówka

Zadanie 2

Zaproponuje algorytm sortujący 4 elementy za pomocą co 5 porównań.


Wskazówka

Zadanie 3

Zaproponuj algorytm sortujący 5 elementów za pomocą co najwyżej 7 porównań.


Wskazówka

Zadanie 4

Udowodnij, że każdy algorytm wyznaczający element minimalny w zbiorze -elementowym wykonuje w pesymistycznym przypadku co najmniej porównań.

Wskazówka

Zadanie 5

Zaproponuj algorytm, który w ciągu długości wyznacza elementy maksymalmy i minimalny wykonując co najwyżej porównania, gdy jest parzyste, a co najwyżej , gdy jest nieparzyste.

Wskazówka