Springen naar inhoud

Algoritmen Orde van toename


  • Log in om te kunnen reageren

#1

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 20 februari 2013 - 21:11

Hey,

Ik snap niet goed hoe ik mijn T(n) moet bereken van onderstaand algoritme.

Som:= 0
VOOR j:= 1 TOT n
	   VOOR i:= 1 TOT j
			  Som := som + …
	   EINDE-VOR
EINDE-VOOR
VOOR k := 1 TOT n
	   Som := som + k
EINDE-VOOR

De uitkomst is T(n) = LaTeX , ik begrijp echter niet goed hoe men aan deze uitkomst komt.

Zou iemand mij kunnen helpen met dit stap voor stap op te lossen?

Dank bij voorbaat,
Roger

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 20 februari 2013 - 21:44

Het lastige zijn waarschijnlijk die lussen:
Laten we beginnen met de onderste loop: je voert die uit voor k = 1 tot n. Je voert dus n keer uit wat daar binnen in staat. Je krijg een term in n.

De bovenste loop met die geneste loop binnenin:
Hier helpt het om eens stap voor stap te kijken wat er gebeurt.
Voor j = 1 voer je de binnenste loop 1 keer uit.
Voor j = 2 voer je de binnenste loop 2 keer uit.
...
Voor j = n voer je de binnenste loop n keer uit.
In totaal heb je de binnenste loop dus 1+2+...+n keer uitgevoerd. Hier zou je een rij in moeten herkennen: simpelweg de rij met LaTeX . Je hebt normaal ooit wel eens geleerd hoe je de partieelsom van zo'n rij kan berekenen. Bereken dus LaTeX (hint).

Is het zo duidelijk?

#3

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 20 februari 2013 - 22:31

Hey,

Ik heb getracht het hieronder zo goed mogelijk uit te werken doch kom ik niet aan de modeloplossing.

Om te beginnen met de som := 0, die is constant en daar zullen we c1 aan toekennen.

We gaan ervan uit dat de som van de geneste loop constant is (c2) en met de formule die je gaf blijkt inderdaad dat die geneste lussen neerkomen op LaTeX .

Bij de laatste lus gaan we er ook vanuit dat de som := ... daar constant is (c3), we voeren die lus daar n keer uit dus zouden we c3* n moeten krijgen.

Alles tesamen geeft dit mij: c1 + c3*n + LaTeX .

Roger

Veranderd door Energyfellow, 20 februari 2013 - 22:31


#4

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 20 februari 2013 - 22:40

Je hebt dus 2n te weinig in vergelijking met de gegeven oplossing.

Hier ben ik niet zeker van maar kan het zijn dat die kost komt omdat je 2 keer een loop van 1 tot n doet? Dat loopen zelf kost ook nog enige tijd, onafhankelijk van wat er in de loop zelf nog gebeurt. (De kost van die loop van 1 tot j zit dan al bij in de kost c2.)

#5

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 21 februari 2013 - 11:06

Ik vind de oplossing die erbij gegeven is erg raar. Immers, wat heeft het voor zin om een constante c3 te definieren als je daar vervolgens 2 bij op gaat tellen? Dan kun je toch net zo goed gewoon een constante c4 definieren die gelijk is aan c3+2 ?

Tenzij ergens bij de opgave expliciet gegeven is wat c3 betekent.

Veranderd door Math-E-Mad-X, 21 februari 2013 - 11:08

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 21 februari 2013 - 11:26

c3 staat volgens mij voor de kost van het stukje "Som := som + k". Zoals ik hierboven zeg vermoed ik dat er nog een kost 2n bijkomt voor het uitvoeren van die loops van 1 tot n. Conceptueel houdt het wel steek om dat dan niet bij in die c3 te stoppen.

Opmerking moderator :

Ik verplaats dit topic overigens ook even naar 'Programmeren'.

#7

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 21 februari 2013 - 23:05

Dave,

Het is wel degelijk de juiste oplossing.
Geplaatste afbeelding

Mvg,
Roger

Ik heb wel nog een vraagje. Ik ondervind dat ik het volledig uitwerken van zulke partiële sommen nog niet volledig onder de knie heb.
Geplaatste afbeelding

Hoe begin ik eraan om dit op te lossen?

Dank bij voorbaat,
Roger

#8

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 22 februari 2013 - 00:43

Mja die 2n kan ik niet verklaren. Voor je andere vraag: zie je ander topic.

#9

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 22 februari 2013 - 11:08

c3 staat volgens mij voor de kost van het stukje "Som := som + k". Zoals ik hierboven zeg vermoed ik dat er nog een kost 2n bijkomt voor het uitvoeren van die loops van 1 tot n. Conceptueel houdt het wel steek om dat dan niet bij in die c3 te stoppen.

Maar dan zou je dat ook moeten doen voor die dubbele loop, dus dan zou er ook nog een extra term n^2 bij moeten komen..

Trouwens, wat ik ook vreemd vind is dat die pseudo-code in het Nederlands is. Dat heb ik echt nog nooit gezien. Geeft me het gevoel dat de schrijver van de opgave niet echt professioneel is.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#10

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 22 februari 2013 - 11:20

Ik denk dat je best eens aan je leerkracht vraagt hoe het precies zit.

Trouwens, wat ik ook vreemd vind is dat die pseudo-code in het Nederlands is. Dat heb ik echt nog nooit gezien. Geeft me het gevoel dat de schrijver van de opgave niet echt professioneel is.

Ik heb het zelf in het middelbaar ook ooit zo gezien :P Maar sinds dan inderdaad nooit meer.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures