Wstęp do programowania / Ćwiczenia 5: Różnice pomiędzy wersjami
MAdamaszek (dyskusja | edycje) m bledy skladniowe w progr. |
MAdamaszek (dyskusja | edycje) m real-->integer w naglowku |
||
| Linia 179: | Linia 179: | ||
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
'''function''' SufitZPierwiastka2(x: | '''function''' SufitZPierwiastka2(x:integer):integer; | ||
//Dla x > 0 wyznaczamy sufit z pierwiastka z x | //Dla x > 0 wyznaczamy sufit z pierwiastka z x | ||
'''var''' l,p,s : integer; | '''var''' l,p,s : integer; | ||
| Linia 187: | Linia 187: | ||
'''while''' l < p '''do''' '''begin''' | '''while''' l < p '''do''' '''begin''' | ||
s:=(l+p)div 2; | s:=(l+p)div 2; | ||
'''if''' x > s*s '''then''' l:=s+1 | '''if''' x > s*s '''then''' l:=s+1 | ||
'''else''' p:=s; | '''else''' p:=s; | ||
'''end'''; | '''end'''; | ||
| Linia 207: | Linia 207: | ||
{{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
'''function''' PodłogaZPierwiastka(x: | '''function''' PodłogaZPierwiastka(x:integer):integer; | ||
//Dla x > 0 wyznaczamy podłogę z pierwiastka z x | //Dla x > 0 wyznaczamy podłogę z pierwiastka z x | ||
'''var''' l,p,s : integer; | '''var''' l,p,s : integer; | ||
| Linia 215: | Linia 215: | ||
'''while''' l < p '''do''' '''begin''' | '''while''' l < p '''do''' '''begin''' | ||
s:=(l+p+1)div 2; | s:=(l+p+1)div 2; | ||
'''if''' x < s*s '''then''' p:=s-1 | '''if''' x < s*s '''then''' p:=s-1 | ||
'''else''' l:=s; | '''else''' l:=s; | ||
'''end'''; | '''end'''; | ||
Wersja z 13:29, 26 sie 2006
<<< Powrót do głównej strony wykładu
To są zadania na wyszukiwanie binarne.
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
Ćwiczenie 1
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)
Rozwiązanie 1
Ćwiczenie 1
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
Rozwiązanie 1
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
Rozwiązanie 1
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
Rozwiązanie 1
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
Rozwiązanie 1
Wskazówka 2
Rozwiązanie 2
Inna wersja zadania
A jak znaleźć podłogę z pierwiastka z x ?
Wskazówka 3
Rozwiązanie 3
Zadanie 7 (BinPower)
Dla zadanych x,n > 0 wyznacz xn (oczywiscie bez exp i ln).
Wskazówka 1
Rozwiązanie 1
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
Rozwiązanie 1
Ćwiczenie 1
