0 Daumen
307 Aufrufe

(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 :)

Avatar von

Beim 1 fall mit der rückgabe von 1 ist es klar, im zweiten fall wird a immer kleiner und im 3 fall wird b immer kleiner, also sollten auch diese terminieren.

Im letzten Fall wird jedoch c größer?!?

In Deinen Überlegungen sollte was mit ner Potentialfunktion vorkommen - was wurde dazu in der Vorlesung gesagt?

Die aufgabe gehört eher zur stacklounge!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community