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
Laatste berichten
-
15:53
positie
-
14:16
do-re-mi-fa-so vliegtuigen 7
-
14:16
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
-
13:57
De Euro Nederlandse 100 qubit computer komt eraan
-
11:32
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 6
-
11:31
geen minkowski-ruimte toch? Doe ik dit nou fout? 14
-
10:42
projectiel 8
-
10:37
Verschil tussen deze 2 vragen 5
-
09:48
Schroefdraad berekening 4
-
09:25
[scheikunde] berekeningen labo vitamine c bepaling 1
-
19:29
[wiskunde] rode en witte ballen verdelen 8
-
17:23
Rotatie van het heelal 41
-
22 apr
Weerfrustratie 5
-
22 apr
Muntje opgooien 14
-
21 apr
Reactiviteit silyl enol ethers 1
-
21 apr
Criterium voor vochtretentie
-
21 apr
speciale rel. theorie 5
-
21 apr
Vogels in de stad zijn goede klussers
-
21 apr
Ervaringen met "herontdekkingen" 15
-
20 apr
Herleiden afmetingen vanaf een foto 19
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Combinaties (geldige) Torens van Hanoï
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 614
Re: Combinaties (geldige) Torens van Hano
De formule is heel eenvoudig:puzzelmans schreef: ↑zo 10 jun 2012, 23: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
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
-
- Berichten: 8
Re: Combinaties (geldige) Torens van Hano
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
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
-
- Berichten: 4.320
Re: Combinaties (geldige) Torens van Hano
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.
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.
In de wiskunde zijn er geen Koninklijke wegen Majesteit.
-
- Berichten: 8
Re: Combinaties (geldige) Torens van Hano
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!
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!
-
- Berichten: 400
Re: Combinaties (geldige) Torens van Hano
Is dat geen herhalingscombinatie voor het tweede deel?
-
- Berichten: 400
Re: Combinaties (geldige) Torens van Hano
puzzelmans schreef: ↑zo 10 jun 2012, 23:30
- 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...
-
- Berichten: 4.320
Re: Combinaties (geldige) Torens van Hano
Die formule is er dus maar je moet hem wel afleiden.puzzelmans schreef: ↑wo 13 jun 2012, 04: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!
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.
-
- Berichten: 8
Re: Combinaties (geldige) Torens van Hano
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.tempelier schreef: ↑wo 13 jun 2012, 11:46
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.
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?
-
- Berichten: 4.320
Re: Combinaties (geldige) Torens van Hano
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.
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.
-
- Berichten: 400
Re: Combinaties (geldige) Torens van Hano
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?
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?
-
- Berichten: 400
Re: Combinaties (geldige) Torens van Hano
Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.tempelier schreef: ↑wo 13 jun 2012, 21: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.
-
- Berichten: 400
Re: Combinaties (geldige) Torens van Hano
kee schreef: ↑wo 13 jun 2012, 22:46
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.
-
- Berichten: 4.320
Re: Combinaties (geldige) Torens van Hano
Klopt ja mijn metode deugt niet.kee schreef: ↑wo 13 jun 2012, 22:52
Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.
In de wiskunde zijn er geen Koninklijke wegen Majesteit.
-
- Berichten: 8
Re: Combinaties (geldige) Torens van Hano
Bedankt voor deze - onontbeerlijke - tip !!!kee schreef: ↑wo 13 jun 2012, 22: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.
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
