Matematik
Carmen serier
en carmen serie er
1 1 1 3 5 9 17 31
Altså 1 1 1 og derefter er det summen af de 3 forgående led.
1) Skriv et program der viser de første 15 i carmen serien
2) skriv en funktion der beregner det n'te element i carmen serien
3) skriv en dynamisk funktion, der beregner det n'te element i carmen serien
og sammenlign tiden det tager med funktionen i 2)
På forhånd tak!
Svar #1
13. juli 2014 af Physant (Slettet)
1)
m=15
u=c()
u[1]=1
u[2]=1
u[3]=1
for(i in 4:m){
u[i]=u[i-1]+u[i-2]+u[i-3]
}
u
plot(u,col="blue",main="carmen")
# 1 1 1 3 5 9 17 31 57 105 193 355 653 1201 2209
Inden jeg fortsætter med 2) og 3) skal jeg have det gjort helt klart, hvad du egentlig mener. Du ønsker, at se på hvor lang tid funktionen i 2) tager om at udregne det n'te element og tilsvarende for funktionen i 3) ?
Svar #2
13. juli 2014 af peter lind
Hvad skal du have hjælp til ?
Spørgsmål 1 er afhængig af hvilket programsprog du kender. Det burde ikke volde de store problemer. Det kan også laves i et regneark.
2. Det er er en 3. ordens lineær differensligning. Hvad kender du til det ? Der findes løsningsmetoder, der ligner lineære differentialligninger. Du skal finde den karakteriske ligning og løse den
3. Hvad er en dynamisk funktion ?
Svar #3
13. juli 2014 af thomaslarsen90Arocketmailcom (Slettet)
#1 ja, det er.. Jeg ved bare ikke hvordan jeg kan konstruere sådan to funktioner
altså en en dynamisk funktion er ligeosm en rekursiv ligning, hvor den bare ikke "gemmer" de forrige værdier. Så en dynamisk funtion er hurtigere end den statiske funktion, fordi den statiske hele tiden skal gemme værdierne for at skabe de nye værdier.
Svar #4
13. juli 2014 af peter lind
Rekursive beregninger gemmer data på en stak. den gemmer ikke de foregående værdier, men opgaven hvorefter den kalder funktionen flere gange. rent hukommelsesmæssigt går det langsommer end med den direkte beregning.
Svar #5
13. juli 2014 af Physant (Slettet)
carmen=function(n){
if(3<n){
carmen(n-1)+carmen(n-2)+carmen(n-3)
}
else{1}
}
# Initialiserer dp til -1
dp = 1:50
for (i in 1:length(dp)) {
dp[i] = -1
}
carmenDynamisk <- function (n) {
if (dp[n + 1] == -1) {
if (3 < n) {
dp[n + 1] <<- carmenDynamisk(n - 1) + carmenDynamisk(n - 2)+carmenDynamisk(n - 3)
} else {
dp[n + 1] <<- 1
}
}
dp[n + 1]
}
carmen(26)
# Det tager 6 sekunder
carmen(28)
# Det tager 19 sekunder
carmen(30)
## Det tager 1 minut og 2 sekunder
carmenDynamisk(30)
# Det tager blot 1/10 sekund.
Det ses tydeligt, at beregningstiden for carmen(x) vokser eksponentielt hurtigt.
Det ses også, at carmenDynamisk(x) er markant hurtigere end carmen(x).
Tidskompleksitet er et sjovt og interessant emne. I et af mine seneste projekter,
skrev jeg et program, som kan finde bestemte gener hos patienter med cancer.
Det tog over en halv time at få et output.
Svar #6
13. juli 2014 af thomaslarsen90Arocketmailcom (Slettet)
super! mange tak! :D Jeg skal vist lige læse koden igennem et par gange, da programmering ikke er min stærke side :p
Må jeg se det andet program, som tager over en halv time at køre? det kunne være sjovt at se
Svar #7
14. juli 2014 af hesch (Slettet)
#3: At en funktion er rekursiv, betyder at der refererer til sig selv ( at den benytter sine egne outputværdier i sine beregninger ). Din Carmen serie kan betragtes som en 3. ordens differensfunktion, og som sådan anvender den sine 3 sidste output ved beregning af et nyt output. Derfor må den nødvendigvis gemme sine 3 sidste output på en stak i et skifteregister, hvor værdierne rykker en plads for hver gennemregning.
Eksempelvis kan overføringsfunktionen for et rekursivt digitalt filter, ved z-transformation skrives:
y(z) / x(z) = ( 0,5z-1 - 0,3z-2 ) / ( 1 - 0,5z-1 - 0,4z-2 ) =>
y(z) z0 = ( 0,5z-1 - 0,3z-2 ) x(z) + ( 0,5z-1 + 0,4z-2 ) y(z)
Operatoren z-n angiver en "tidsforsinkelse" på n samples ( n gennemregninger ). Det grønne led udgør rekursivdelen af filteret ( brug af tidligere output, y(z) ). Udelader du det grønne led, er filteret ikke længere rekursivt, idet output fra filteret så alene afhænger af input, x(z).
Eftersom gennemregningen er den samme, sample for sample, bliver sammenhængen mellem regnetid og antal led i Carmenserien lineær.
Din Carmen serie kan, ved den z-transformerede, skrives noget i retning af:
y(z) = ( z-1 + z-2 + z-3 ) y(z)
. . . hvor man så initialiserer:
y(z) z-1 = y(z) z-2 = y(z) z-3 = 1
Jeg skal senere skrive en stump kode, der viser metodikken med et skifteregister.
Hvis ovenstående er en dynamisk beregning, må jeg spørge: Hvad er en statisk beregning ?
Svar #9
14. juli 2014 af hesch (Slettet)
#7: Prøver igen: Programudskrift vedhæftet. ( Pascal ).
Målt regnetid for første 30 elementer i Carmenserien ≈ 10 μs. ( exclusive udskrifter ).
Men altså, det kan jo gøres langt hurtigere, fx ved at programmere i assembler.
Svar #10
15. juli 2014 af Stats
Programmer i Assembler...
Du er binde gal hesch. Det er et af det sværeste programmeringssprog!
Mvh Dennis Svensson
Svar #11
15. juli 2014 af hesch (Slettet)
#10: Nej, svært er det ikke, specielt ikke for en Intelprocessor, da den er lidt "primitiv" i sin struktur, for nu at sige det mildt. Den kan simpelthen ikke så meget. Men sproget varierer jo fra processor til processor, og det kan være hjernevridende at skifte fra èn processor til en anden, for hvordan er det nu lige man gør med denne her ? Det tager et par timer at omstille sig, førend sproget "flyder". Man skal tænke på en anden måde fordi den nye processor har en anden struktur, der udnyttes ved at programmere den anderledes.
Det er sjovt og udfordrende, ikke svært.
Skriv et svar til: Carmen serier
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.