Springen naar inhoud

Combinaties (geldige) Torens van Hanoï


  • Log in om te kunnen reageren

#1

puzzelmans

    puzzelmans


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 10 juni 2012 - 22:30

Hallo,

Ben op zoek naar:

- dé formule voor het bepalen van het aantal mogelijke "opstellingen" met n (voor de eenvoud: 1 <= n <= 9) schijven (van verschillende diameter) verdeeld over drie stapels;

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;

- bij uitbreiding: de bepaling van het aantal "geldige" binnen de verzameling van mogelijke "oplossingen", mits het toepassen van één (of meer) eenvoudige(?) regel(s);

- bij gebrek hieraan, een - liefst eenvoudige - methode (algoritme) om de "geldige" deelverzameling te bepalen, bij voorkeur niet met "brute force", eventueel via bactracking;

Mvg,
Puzzelmans

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

#2

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 11 juni 2012 - 15:29

Hallo,

Ben op zoek naar:

- dé formule voor het bepalen van het aantal mogelijke "opstellingen" met n (voor de eenvoud: 1 <= n <= 9) schijven (van verschillende diameter) verdeeld over drie stapels;

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;

- bij uitbreiding: de bepaling van het aantal "geldige" binnen de verzameling van mogelijke "oplossingen", mits het toepassen van één (of meer) eenvoudige(?) regel(s);

- bij gebrek hieraan, een - liefst eenvoudige - methode (algoritme) om de "geldige" deelverzameling te bepalen, bij voorkeur niet met "brute force", eventueel via bactracking;

Mvg,
Puzzelmans


De formule is heel eenvoudig:

H(n)=2H(n-1)+1

Met:
H(n)= Toren met n schijven
H(n-1)= Toren met n-1 schijven

Wat wil je met de rest bereiken?

Ps. Uiteraard met H(1)=1

#3

puzzelmans

    puzzelmans


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 11 juni 2012 - 20:02

Bedankt voor je antwoord, maar is dat niet de formule voor het (minimaal) aantal benodigde stappen om een toren van n schijven te verplaatsen naar een andere positie? Zonder recursie ook te berekenen als H(n) = 2^n - 1 ?

Wat ik graag zou weten is: op hoeveel manieren kan ik n schijven verdelen over 3 stapels (extra: wanneer de "volgorde" van de stapels al dan niet belangrijk is) ? En: hoeveel van deze "verdelingen" zijn "geldig" als "Hanoï-opstelling" ?

Het zou leuk zijn als ook het antwoord op de tweede vraag niet proefondervindelijk moet worden vastgesteld...

Mvg,
Puzzelmans

Veranderd door puzzelmans, 11 juni 2012 - 20:03


#4

tempelier

    tempelier


  • >1k berichten
  • 1766 berichten
  • Ervaren gebruiker

Geplaatst op 12 juni 2012 - 11:23

Willekeurig is vrij gemakkelijk te vinden.

Stapel alles op eerste van de torens en kijk op hoeveel manieren dat kan.

Je kunt nu deze stapel in drie lagen verdelen de bovenste verplaats je naar een tweede toren met behoud van de volgorde en vervolgens de middelste laag naar de derde toren kijk nu op hoeveel manieren dit kan.
Zo' n laag kan natuurlijk leeg zijn.

Nu is het nog niet geheel klaar het hangt er nu van af wat er als verschillend gezien wordt.
Dus of het omwisselen van twee torens wel of niet als een verschillende mogelijkheid wordt gezien.

Veranderd door tempelier, 12 juni 2012 - 11:24

In de wiskunde zijn er geen Koninklijke wegen Majesteit.

#5

puzzelmans

    puzzelmans


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 13 juni 2012 - 03:19

Bedankt voor de tip !
Ik had echter gehoopt dat er een formule zou bestaan, i.p.v. een proefondervindelijke methode... Misschien zit die wel in de beschrijving verstopt: voor stap 1 zou dat m.i. het aantal permutaties van n elementen zijn, m.a.w. P(n) ofwel n!
Maar dan krijg ik het al moeilijk: op hoeveel manieren kan ik deze n elementen over 3 stapels verdelen, waarbij elke stapel benoemd is (dus de "volgorde" van de stapels is belangrijk), en van 0 tot n elemente mag bevatten ?
Ik vermoed dat de volgorde van de elementen per stapel niet belngrijk is in deze stap, omdat hiermee wel rekening gehouden is in de vorige... Tenzij je natuurlijk stap 1 overslaat, en bij het verdelen in stapels dus wél rekening houdt met de volgorde per stapel. Hmm... Help! ;-)

#6

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 08:10

Is dat geen herhalingscombinatie voor het tweede deel?

#7

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 09:15

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;


Variatie, herhalingsvariatie, combinatie, herhalingscombinatie. Welk van de vier ga je hiervoor gebruiken...

#8

tempelier

    tempelier


  • >1k berichten
  • 1766 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 10:46

Bedankt voor de tip !
Ik had echter gehoopt dat er een formule zou bestaan, i.p.v. een proefondervindelijke methode... Misschien zit die wel in de beschrijving verstopt: voor stap 1 zou dat m.i. het aantal permutaties van n elementen zijn, m.a.w. P(n) ofwel n!
Maar dan krijg ik het al moeilijk: op hoeveel manieren kan ik deze n elementen over 3 stapels verdelen, waarbij elke stapel benoemd is (dus de "volgorde" van de stapels is belangrijk), en van 0 tot n elemente mag bevatten ?
Ik vermoed dat de volgorde van de elementen per stapel niet belngrijk is in deze stap, omdat hiermee wel rekening gehouden is in de vorige... Tenzij je natuurlijk stap 1 overslaat, en bij het verdelen in stapels dus wél rekening houdt met de volgorde per stapel. Hmm... Help! ;-)

Die formule is er dus maar je moet hem wel afleiden.

Die stapels verdelen is ook niet zo moeilijk af te leiden zie het als twee snijvlakken die precies tussen twee schijven moeten worden aangebracht.
In de wiskunde zijn er geen Koninklijke wegen Majesteit.

#9

puzzelmans

    puzzelmans


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 13 juni 2012 - 19:51

Die formule is er dus maar je moet hem wel afleiden.

Die stapels verdelen is ook niet zo moeilijk af te leiden zie het als twee snijvlakken die precies tussen twee schijven moeten worden aangebracht.


Best grappig, ik had ook al zitten denken over één of andere metafoor, de plakjes/worst was er één van, maar echt geholpen heeft het toen niet... 't Is te lang geleden dat ik dit op school leerde en/of nog toepaste.

Nog maar eens proberen: hoe verdeel ik n plakjes over drie stapeltjes waarbij elk stapeltje 0 tot n plakjes mag bevatten? Volgens mij heb ik n+1 mogelijke "snij-vlakken", voor(bij) de uiteinden telt ook. Ook mogen de beide "gebruikte snij-vlakken" samenvallen. En dan val ik weer stil... Misschien moet ik toch maar eens eerst de theorie opfrissen?

#10

tempelier

    tempelier


  • >1k berichten
  • 1766 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 20:03

Je kunt het ook ander oplossen, misschien wel zo makkelijk.


Haal alle schijven van de torens, pak nu een willekeurig schijf en plaats die op een toren.

Dat geeft 3*n mogelijkheden

Pak daarna weer een schijf er zijn er dan (n-1) ovder en plaats die op een willekeurige toren enz.
In de wiskunde zijn er geen Koninklijke wegen Majesteit.

#11

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 21:46

Nochtans ben je er zo wel hoor. Herinner je je een herhalingscombinatie uit de theorie?

Je hebt n+1 mogelijke snijvlakken.
Je kiest er 2 uit.
De gebruikte snijvlakken mogen samenvallen.

Dus:
Je kiest 2 keer uit n+1 met herhaling (gezien de snijvlakken mogen samenvallen). De volgorde waarin je de 2 snijvlakken kiest maakt niet uit (kies je eerst de ene, dan de andere, of maak je dezelfde keuze omgekeerd, dan is dit dezelfde opdeling). Een herhalingscombinatie dus.

Daarnaast voor je tweede punt: Heb je het antwoord voor de geldige opstellingen? Welk van de vier is hier geschikt?

#12

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 21:52

Je kunt het ook ander oplossen, misschien wel zo makkelijk.


Haal alle schijven van de torens, pak nu een willekeurig schijf en plaats die op een toren.

Dat geeft 3*n mogelijkheden

Pak daarna weer een schijf er zijn er dan (n-1) ovder en plaats die op een willekeurige toren enz.


Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.

#13

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 13 juni 2012 - 21:57

Daarnaast voor je tweede punt: Heb je het antwoord voor de geldige opstellingen? Welk van de vier is hier geschikt?


Een tip om het te zien: verdeel je schijven in drie stapels, een stapel voor de toren links, een stapel voor de middelste toren, een stapel voor de rechtse toren (mogen ook "lege stapels" zijn). Met elk zo'n verdeling van je schuiven komt precies één geldige opstelling overeen, namelijk de drie stapels geordend van groot naar klein.

Veranderd door kee, 13 juni 2012 - 22:05


#14

tempelier

    tempelier


  • >1k berichten
  • 1766 berichten
  • Ervaren gebruiker

Geplaatst op 14 juni 2012 - 12:03

Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.

Klopt ja mijn metode deugt niet.

Veranderd door tempelier, 14 juni 2012 - 12:03

In de wiskunde zijn er geen Koninklijke wegen Majesteit.

#15

puzzelmans

    puzzelmans


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 20 juni 2012 - 12:25

Nochtans ben je er zo wel hoor. Herinner je je een herhalingscombinatie uit de theorie?

Je hebt n+1 mogelijke snijvlakken.
Je kiest er 2 uit.
De gebruikte snijvlakken mogen samenvallen.

Dus:
Je kiest 2 keer uit n+1 met herhaling (gezien de snijvlakken mogen samenvallen). De volgorde waarin je de 2 snijvlakken kiest maakt niet uit (kies je eerst de ene, dan de andere, of maak je dezelfde keuze omgekeerd, dan is dit dezelfde opdeling). Een herhalingscombinatie dus.


Bedankt voor deze - onontbeerlijke - tip !!!

Zo had ik het namelijk nog niet bekeken, d.w.z. vanuit de snijvlakken i.p.v. de schijven...

Mijn eerste "indruk" was evenwel dat hier enkele randgevallen (ten onrechte) herhaald zouden worden bij de te "telling"... Na enige bezinning heb ik mijn mening herzien, maar dat is (mede) de verklaring voor deze ietwat late reactie.

Mvg,
Puzzelmans





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures