Falsches Resultat (Rekursion)

Aufrufe: 924     Aktiv: 31.08.2023 um 15:22

0

Hallo zusammen,

enter image description here

Meine Lösung:

U(A,l,r)

q <- l + (l-r) /3 ansL <- U(A,1,3) ansR < U(A,4,8)

1) U(A,1,3) ansL <-U(A,1,1) ansR<-U(A,2,3)

2) U(A,4,8) ansL <-U(A,4,5) ansR<-U(A,6,8)

3)U(A,1,1) A1 = 6

4) U(A,2,3) ansL <- U(A,2,2) ansR <- U(A,3,3)

5) U(A,4,5) ansL <- U(A,4,4) ansR <-U(A,5,4)

6) U(6,8) ansL <- U(A,6,6) ansL <- U(A,7,6)

7) U(A,2,2) A[2] = 4

8) U(A,3,3) A[3] = 2

9) U(A,4,4) A[4] = 9

10) U(A,5,4) return -inf

11) U(A,6,6) A[6] = 8

12) U(A,7,6) return -inf

Was mache ich falsch? Die Lösung soll 9 sein.

Diese Frage melden
gefragt

Student, Punkte: 66

 
Kommentar schreiben
1 Antwort
0

Wrote a small PYTHON-program, but it returns "recursion-depth error". I had to add some if..elif...else-blocks in order to deal with the "-inf" value. Additional, a python-array starts with index 0, so the access to its elements must be coded A[l-1] instead of A[l]. If you say, the result has to be 9, I wonder why the program doesn't give that result. Perhaps I made an error ... anyway, feel free to try yourself.

# what does unknown(arr,1,8) return?
import math 
arr = [6,4,2,9,2,8,7,5] 
def unknown(a, l, r):
    if l > r:
        return "-inf"
    elif l==r:
        return a[l-1]
    else:
        q=l+math.floor((r-1)/3)
        al=unknown(a,l,q)
        ar=unknown(a,q+1,r)
        if al=="-inf" and ar=="-inf":
            return a[l-1]
        elif ar=="-inf" and al==type('int'):
            return al
        elif al=="-inf" and ar==type('int'):
            return ar
        elif al>ar:
            return al
        else:
            return ar

print(unknown(arr,1,8))
Diese Antwort melden
geantwortet

Softwareentwickler, Punkte: 10

 

Kommentar schreiben