Correctness, induktionsbevis
Hej!
Jag har fastnat på a)-delen på den andra algoritmen, förstår inte hur jag ska bära mig åt för att fixa ett induktionsbevis. Så skulle verkligen uppskatta lite hjälp med det!
Jag har hittat en loop invariant till första algoritmen:
Det var alltför länge sedan jag genomförde matematiska bevis, så det jag skriver nu håller troligen inte formalia. Jag tänker som följer:
Den iterativa funktionen har bevisats (eller kan antas vara bevisad) och den anropas av den rekursiva funktionen för alla n ≤ 4.
Vi behöver, genom induktion, bevisa att den rekursiva funktionen är korrekt även för n>4. Kan vi visa att den är korrekt för något udda och något jämnt tal större än 4 så räcker det som induktionsbevis (eller?).
För att beräkna x⁵, dvs då n=5, så kommer den rekursiva funktionen att anropa sig själv två gånger och multiplicera returvärdena. I Java blir n/2==2 och (n+1)/2==3. Sålunda utförs multiplikationen x²x³ vilket är samma som x⁵.
För att beräkna x⁶, dvs då n=6, så kommer den rekursiva funktionen att anropa sig själv två gånger och multiplicera returvärdena. I Java blir n/2==3 och (n+1)/2==3. Sålunda utförs multiplikationen x³x³ vilket är samma som x⁶.
Behövs något mer för ett formellt bevis?
