Zadanie 2: Sufiksy
Liczenie porównań w funkcji czy_mniejszy, porównywanie sufiksów słowa, sortowanie ich alfabetycznie i szukanie najmniejszego (2.1-2.4).
Rozwiązujesz bez konta, a odpowiedzi sprawdza ten sam silnik co na platformie. Postęp i powtórki zapisują się dopiero po darmowej rejestracji.
Policz porównania w pierwszej instrukcji jeżeli
Pierwsza instrukcja jeżeli w funkcji czy_mniejszy sprawdza, czy s[i] == s[j]. W arkuszu podano przykład: dla s = mascarpone, k1 = 5, k2 = 2 algorytm wykonuje 2 takie porównania (s[5] z s[2] oraz s[6] z s[3]; to drugie już się nie zgadza, ale zostało wykonane). Uzupełnij tabelę. W dwóch środkowych wierszach podaj liczbę porównań, a w ostatnim, odwrotnie, dobierz k2 tak, aby porównań było dokładnie 6 (to jest oryginalne polecenie 2.1).
| 1 | czy_mniejszy(n, s, k1, k2) |
| 2 | i ← k1 |
| 3 | j ← k2 |
| 4 | dopóki (i ≤ n oraz j ≤ n) wykonuj |
| 5 | jeżeli (s[i] == s[j]) |
| 6 | i ← i+1 |
| 7 | j ← j+1 |
| 8 | w przeciwnym razie |
| 9 | jeżeli (s[i] < s[j]) |
| 10 | zakończ z wynikiem PRAWDA |
| 11 | w przeciwnym razie |
| 12 | zakończ z wynikiem FAŁSZ |
| 13 | jeżeli (j ≤ n) |
| 14 | zakończ z wynikiem PRAWDA |
| 15 | w przeciwnym razie |
| 16 | zakończ z wynikiem FAŁSZ |
W ostatnim wierszu luka jest w kolumnie k2, nie w kolumnie z liczbą porównań.
| s | k1 | k2 | Liczba porównań w pierwszej instrukcji jeżeli |
|---|---|---|---|
| mascarpone | 5 | 2 | 2 |
| abcaabbaabbccba | 4 | 8 | |
| ababababb | 1 | 3 | |
| aaaaaaaaaa | 2 | 6 |
Do uzupełnienia: 3