Informatyka MIMUW

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.

1. Potęgowanie liczb całkowitych (z akumulatorem).
   
   Rozwiązania
2. [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
3. 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
4. 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
5. 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]$.
6. 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ą?