Rozwiązania poniższych zadań to proste procedury operujące na liczbach całkowitych.
Ich rozwiązanie wymaga zastosowania rekurencji ogonowej.
Dla każdej procedury rekurencyjnej podaj jej specyfikację, tj. warunek wstępny i końcowy,
oraz uzasadnij jej poprawność.
Poprawność procedur rekurencyjnych można pokazać przez indukcję.
Nie zapomnij o uzasadnieniu własności stopu.
- Potęgowanie liczb całkowitych (z akumulatorem).
Rozwiązania
- [Bentley]
Dana jest funkcja \(f: \{1, 2, \dots, n\} \to {\cal Z}\).
Należy znaleźć takie \(1 \le a \le b \le n\), że suma \(\sum_{i=a}^b f(i)\) jest największa.
Napisz taką procedurę p, że \(\mathtt{p}\ f\ n = b - a + 1\) (dla \(a\) i \(b\) jak wyżej).
Rozwiązania
-
Napisz procedurę \(\mathtt{zera\_silni} : \mathtt{int} \to \mathtt{int}\), która dla danej dodatniej liczby całkowitej \(n\) obliczy ile zer znajduje się na końcu zapisu dziesiętnego liczby \(n!\).
Rozwiązania
-
Dana jest funkcja nierosnąca \(f: \mathtt{int} \to \mathtt{int}\), taka, że \(f(x+1) \ge f(x) - 1\).
Napisz procedurę, która znajduje punkt stały tej funkcji, tzn. taką liczbę \(x\), że \(f(x) = x\)
(lub jeśli punkt stały nie istnieje, to taką liczbę \(x\), że \(f(x-1) \ge x\) oraz \(f(x) \le x\)).
Rozwiązania
-
Dana jest różnowartościowa funkcja \(f: \mathtt{int} \to \mathtt{int}\).
Napisz procedurę maksima, która dla danych liczb \(l\) i \(p\) (\(l \le p\)) obliczy ile lokalnych maksimów ma funkcja \(f\) w przedziale \([l, p]\).
-
Przypomnij sobie rozwiązania zadań z poprzednich ćwiczeń.
Jeśli rozwiązałeś je nie stosując rekurencji ogonowej, to czy potrafisz je rozwiązać (lepiej) stosując ją?