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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 262: Linia 262:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Użyj podobnego pomysłu, jak przy mnożeniu chłopów rosyjskich. Pamiętaj, że mnożenie ma się tak do dodawania, jak potęgowanie do mnożenia.  
+
Użyj podobnego pomysłu jak przy mnożeniu chłopów rosyjskich. Pamiętaj, że mnożenie ma się tak do dodawania, jak potęgowanie do mnożenia.  
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 294: Linia 294:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Kluczowe jest użycie dodatkowej tablicy B rozmiaru N, w której pod indeksem i przechowuje się minimalną wartość kończącą podciąg niemalejący o długości i w dotychczas przejrzanej części tablicy A,  od 1 do k. Żeby uwzględnić A[k+1] należy w tablicy B odnależć miejsce na A[k+1] (najlepiej binarnie).
+
Kluczowe jest użycie dodatkowej tablicy B rozmiaru N, w której pod indeksem i przechowuje się minimalną wartość kończącą podciąg niemalejący o długości i w dotychczas przejrzanej części tablicy A,  od 1 do k. Żeby uwzględnić A[k+1], należy w tablicy B odnależć miejsce na A[k+1] (najlepiej binarnie).
 
</div>
 
</div>
 
</div>}}
 
</div>}}

Wersja z 21:42, 15 lis 2006

<<< Powrót do modułu Składnia i semantyka instrukcji

To są zadania na wyszukiwanie binarne.

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


Zadanie 1 (Pierwsze wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce pierwszego wystąpienia x (lub 0 gdy nie ma żadnego x)

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Zadanie 2 (Ostatnie wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce ostatniego wystąpienia x (lub 0 gdy nie ma żadnego x)

Wskazówka 1

{{{3}}}


Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Zadanie 3 (Liczba wystąpień x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Wyznacz liczbę wystąpień x w tablicy A.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 4 (Wartość równa indeksowi)

Dana jest posortowana rosnąco tablica A typu array[1..N] of integer. Sprawdź czy występuje w niej element o wartości równej swojemu indeksowi. Jeśli tak, to wyznacz ten indeks, jeśli nie, to funkcja ma dać wartość 0.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 5 (Maksimum w ciągu bitonicznym)

Dana jest tablica A typu array[1..N] of integer, w której wartości ułożone są w ciąg bitoniczny (czyli istnieje 1 ≤ i ≤ N, takie że dla wszystkich k, takich że 1 ≤ k < i zachodzi A[k] < A[k+1] a dla wszystkich k, takich że i ≤ k < N zachodzi A[k] > A[k+1]). Znajdź maksimum w tym ciągu.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 6 (Pierwiastek z x)

Napisz program obliczający sufit z pierwiastka z x, dla xεN, x > 0 (oczywiście bez operacji pierwiastek).

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Inna wersja zadania

A jak znaleźć podłogę z pierwiastka z x ?

Wskazówka 3

{{{3}}}

Rozwiązanie 3

{{{3}}}

Zadanie 7 (BinPower)

Dla zadanych x,n > 0 wyznacz xn (oczywiscie bez exp i ln).

Wskazówka 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}

O ile istnieją proste algorytmy mnożące w czasie wielomianowym (choćby szkolne słupki), to w przypadku potęgowania nie ma oczywistego szybkiego algorytmu potęgującego. Można spytać, po co usprawniać kod potęgowania, gdy wykładniki w naturze wcale nie sa takie duże. Nic bardziej mylnego! W jednym z najpopularniejszych algorytmów kryptograficznych - kodowaniu RSA - używa się potęgowania o wykładnikach będących bardzo dużymi liczbami (zazwyczaj stukilkudziesięciocyfrowymi!). Poleglibyśmy sromotnie, gdybyśmy próbowali mnożyć odpowiednią liczbę razy przez siebie podstawę potęgowania.

Zadanie 8 (Najdłuższy podciąg niemalejący)

Dana jest tablica A typu array[1..N] of integer, N > 1. Należy obliczyć długość najdłuższego podciągu niemalejącego w A.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}