Matematik

Carmen serier

13. juli 2014 af thomaslarsen90Arocketmailcom (Slettet) - Niveau: Universitet/Videregående

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! 


Brugbart svar (0)

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) ?

Vedhæftet fil:carmen.jpeg

Brugbart svar (0)

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.


Brugbart svar (0)

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.


Brugbart svar (0)

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


Brugbart svar (0)

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 ?


Brugbart svar (0)

Svar #8
14. juli 2014 af hesch (Slettet)

#7:  Programudskrift vedhæftet.


Brugbart svar (0)

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.

Vedhæftet fil:Carmen.pdf

Brugbart svar (0)

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


Brugbart svar (0)

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.