---

Hej

Jeg har fået en opgave om en 2 base logaritme, som jeg sidder lidt
fast i.

Håber der er nogle som kan give mig et skub i den rigtige retning.

En definition på en recurrence

T(1) = 0
T(n) = T(n/2) +1

Formlen for recurrencen for T(n) er lg n (basen er 2),

Opgaven lyder at man skal bevise via induktion at dette er korrekt.

Så vidt jeg kan se, så kan man vel gøre det her:

T(n)    = T(n/2) +1
   = lg n/2 + 1   <-- antager at T(n) = lg n
   = lg n - lg 2 + 1   <-- bruger reglen lg 1/a = -lg a
   = lg n - 1 + 1   <-- beregner lg 2, hvilket er 1
   = lg n       <-- reducerer -1 + 1

Det skulle bevise at T(n) = lg n.... men der mangler jo ligesom en
eller anden form for induktions bevis.

Jeg har prøvet finde et mønster i dette her, og kunne se følgende:

T(1) = 0
T(2) = T(2/2) + 1 = T(1) + 1 = 0 + 1

T(4) = T(4/2) +1 = T(4/4) + 1 + 1

Det ene problem jeg har er hvad hvis n = 3

F.eks.

T(3) = T(3/2) +1 = T(1,5/2) + 1 + 1 = T(0,75/2) + 1 + 1 + 1

T(3) vil aldrig nå T(1) , hvilket betyder at den vil fortsætte i den
uendelige... Skal man så skrive at recurrencen (er der nogen der
kender det danske ord for recurrence), skal være i potens af to.
d.v.s. 2.4.8, 16 etc.... eller skal formlen kunne bruger for alle tal.

På forhånd tak

Meang

---

aimat <meang@post.com> writes:

> En definition på en recurrence
>
> T(1) = 0
> T(n) = T(n/2) +1

> T(3) vil aldrig nå T(1) , hvilket betyder at den vil fortsætte i den
> uendelige... Skal man så skrive at recurrencen (er der nogen der
> kender det danske ord for recurrence), skal være i potens af to.
> d.v.s. 2.4.8, 16 etc.... eller skal formlen kunne bruger for alle tal.

Det hedder en rekusion(sformel) på dansk, og du har ganske ret i at den
givne rekursion ikke er defineret for andet end potenser af to.

..Henrik

--
"The ultimate goal of mathematics is to eliminate all need for
intelligent though" - Graffiti af ukendt i 'Concrete Mathematics'

---

aimat wrote:

> Hej
>
> Jeg har fået en opgave om en 2 base logaritme, som jeg sidder lidt
> fast i.
>
> Håber der er nogle som kan give mig et skub i den rigtige retning.
>
> En definition på en recurrence

Som Henrik Christian skriver hedder det en rekursionsformel
på dansk. Direkte oversat betyder "recurrence" vel noget i
stil med "gentagelse".

> T(1) = 0
> T(n) = T(n/2) +1

Mon ikke her skal stå

T(n) = T( rund_ned(n/2) ) + 1 ?

> Formlen for recurrencen for T(n) er lg n (basen er 2),

Mon ikke der står rund_ned( lg n ) ?

Lad os lige afprøve det. Bemærk at rund_ned (også kaldet gulv) hedder
floor på engelsk.

; log2 : naturlige tal -> naturlige tal
; udregner totalslogaritmen af n
(define (log2 n)
(inexact->exact (floor (/ (log n)
(log 2)))))

; T : naturlige tal -> naturlige tal
; "ukendt" rekursionsformel
(define (T n)
(cond
[(= n 1) 0]
[else (+ 1 (T (floor (/ n 2))))]))

(define testliste (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))

> (map T testliste)
(0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4)

(map log2 testliste)
(0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4)

> Opgaven lyder at man skal bevise via induktion at dette er korrekt.
>
> Så vidt jeg kan se, så kan man vel gøre det her:
>

Antag her at n er et tal på formen 2^k.

> T(n)    = T(n/2) +1
>    = lg n/2 + 1   <-- antager at T(n) = lg n
>    = lg n - lg 2 + 1   <-- bruger reglen lg 1/a = -lg a
>    = lg n - 1 + 1   <-- beregner lg 2, hvilket er 1
>    = lg n       <-- reducerer -1 + 1
>
> Det skulle bevise at T(n) = lg n.... men der mangler jo ligesom en
> eller anden form for induktions bevis.

Du har brugt induktionsantagelsen, da du skrev

T(n/2) = lg(n/2)

Induktionsbasis:
T(1) = 0 = log2(1) sandt

Induktionsskridt:
Bevis at T(n)=log2(n) under antagelse af at
der for alle m mindre end n gælder T(m) = log2(m)

Ovenfor har du brugt at n/2 er mindre end n (når n>1).

En metode er at benytte induktion til at vise sætningen
for

0 1 2 x
2 , 2 , 2 ... 2

Det har du vist godt styr på allerede.

k k+1 k
Vis så at 2 < n < 2 => T(n) = T( 2 ) = k = rund_ned( log2(n) )

k
Hint: Sammenlign T( rund_ned( n/2 )) med T( 2 )

> Det ene problem jeg har er hvad hvis n = 3
>
> F.eks.
>
> T(3) = T(3/2) +1 = T(1,5/2) + 1 + 1 = T(0,75/2) + 1 + 1 + 1

> T(3) vil aldrig nå T(1) , hvilket betyder at den vil fortsætte i den
> uendelige...


Enten betyder n/2 i opgaven heltalsdivision, eller også mangler
der et rund ned.

--
Jens Axel Søgaard