(Potentialfunktion)
Zeigen Sie mithilfe einer geeigneten Potentialfunktion \( \phi \), dass der folgende rekursive Algorithmus für beliebige Eingaben \( a, b, c \in \mathbb{N} \) terminiert.
Algorithmus 1: UNKNOWN \( (a, b, c) \)
if \( a-b<c \) then
return 1
if \( a \bmod 2=0 \) then
return \( 1+\operatorname{UNKNOWN}(a / 2, b, c) \)
if \( b \bmod 2=0 \) then
return \( 1+\operatorname{UnkNOWN}(a, b / 2, c) \)
return \( 1+\operatorname{UNKNOWN}(a, b, c+1) \)
Problem/Ansatz:
Ich finde keine potentialfunktion und weiß nicht wie ich die Terminierung zeigen kann. Ich bedanke mich schon im Voraus für die Hilfe :)
