|
| Hjælp til induktion, reccurrence og logari~ Fra : aimat |
Dato : 15-03-04 00:05 |
|
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
| |
Henrik Christian Gro~ (15-03-2004)
| Kommentar Fra : Henrik Christian Gro~ |
Dato : 15-03-04 00:30 |
|
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'
| |
Jens Axel Søgaard (15-03-2004)
| Kommentar Fra : Jens Axel Søgaard |
Dato : 15-03-04 12:28 |
|
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
| |
|
|