Matematik
Algorithm and Data Structure.
Hej Derude.
Jeg har en opgave i Algorithm and Data-structure, som jeg ikke kan løse.
Opgaven lyder:
Ved at bruge substitution-method, bestem "the upper and lower bounds"'
p(n)=p(n/2)+p(n/3)+n.
Endvidere p(1)=1, p(2)=2,.....,
Jeg håber, at nogen, der kan algorithm vil hjælpe
Svar #1
13. maj 2015 af peter lind
Den opgave ser mærkelig ud. p(n) er slet ikke defineret i almindelighed. eks.
p(3) = p(3/2)+p(1)+3.
Du kender ikke p(3/2) så du har ingenchance forat finde den.
Skal det ikke være p(n) = p(n-2)+p(n-3) + n
Den er godt nok også mærkelig.
Kan vi ikek få den præcise tekst. ?
Ellers prøv at lav en række eller en kolonne med p(n) og se om du kan gætte en formel for p(n) derefter kan du så bevise resultatet.
Svar #2
13. maj 2015 af Niko83 (Slettet)
Desværre har jeg brugt 2-3 dage for at løse denne opgave, og den har jeg ikke løst alligevel.
Det kræver, at man er populær lidt med "Algorithm and Data Structure".
Her er en hjemmeside. http://homepages.math.uic.edu/~jan/mcs360/substitution_method.pdf
Denne eksampel er gode, men svært at anvende til min opgave.
Tak, at du vil hjælpe. Hvis nogen derude er populær med "Algorithm and Data Structure",
så please giv "a shot"
Svar #3
13. maj 2015 af peter lind
Din henvisning er til rekursiv algoritme. Det kan bare ikke bruges på den opgave du har angivet. Kan vi ikke få den præcise tekst ? evt som billede
Svar #4
13. maj 2015 af Niko83 (Slettet)
Det er Task.2:
opgave 1) og opgave 2 eller opgave 2.1 og opgave 2.2.
Plus: CLRS = http://syedwaqarahmad.webs.com/documents/t._cormen_-_introduction_to_algorithms_3rd_edition.pdf
Svar #5
13. maj 2015 af peter lind
Jeg havde helt misforstået opgaven
Jeg vil foreslå at du gætter på noget i retning af c*n*log6(n) NB logaritme med grundtal 6
Det er et rent gæt alene baseret på eksemplet samt at det ikke skal være svært. Jeg aner ikke om det virker
Interessant bog du henviser til i #4. Jeg har søgt på CLRS men programmet kan ikke finde det
Skriv et svar til: Algorithm and Data Structure.
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.