WisFaq!

\require{AMSmath} geprint op vrijdag 29 maart 2024

Re: Re: Speelschema

JaDeX,

Bedankt voor je reactie. Kan niet verder, maar waardeer het zeer. Ben zelf begonnen met programmeren :-) Heb je voor mij nog de logica van toen. Twee keer het wiel uitvinden hoeft niet toch?

Erik

Erik van Loon
5-4-2018

Antwoord

Hallo Erik,

Het is snel te zien dat het schema met de gestelde eisen (12 teams, 12 ronden, elk team niet 2 keer tegen een ander team) niet uit te breiden is naar 12 ronden. Immers: elk team heeft maar 11 mogelijke tegenstanders, dus na maximaal 11 ronden loopt het spaak. Je zult dus wat water bij de wijn moeten doen.

Wat betreft de logica: het eenvoudigst programmeren is de 'brute force' methode. Hierbij worden systematisch alle mogelijkheden afgetast. Hier zitten dan ook overbodige berekeningen bij, zoals: stel dat er geen mogelijkheid is waarbij in de eerste ronde team A en team B tegen elkaar spelen. Dan heeft het geen zin om te onderzoeken of er een mogelijkheid is waarbij team C en team D tegen elkaar spelen. Immers, je had team C en team D ook team A en team B kunnen noemen. Echter, het inbouwen van allerlei slimmigheid om te bedenken of een bepaalde berekening wel of niet zinnig is, kost veel moeite, vergissingen, testruns enz. Bij zeer complexe problemen is dit noodzakelijk, omdat de rekentijd anders absurd lang kan worden. Bij een probleem als dit is een 'dom' brute force programma waarschijnlijk sneller klaar dan dat jij al die extra's in het programma hebt ingebouwd.

Een brute force programma zou als volgt kunnen worden opgebouwd:
Definieer een 12x12 matrix M. De rijen stellen de teams A t/m H voor, de kolommen geven de 12 ronden weer. Bij aanvang zijn alle elementen 0, dit betekent: er is nog geen spel (en geen tegenstander) toegekend. Uiteindelijk moeten de elementen het nummer van het te spelen spel weergeven.
Handig is om een tweede 12x12 matrix G (Gespeeld) te definiëren om bij te houden welke teams al tegen elkaar hebben gespeeld. De startwaarden zijn 0 (=nog niet tegen elkaar gespeeld).
We definiëren ook een variabele 'spelnummer'.

Uiteraard kunnen we in de eerste ronde spel 1 toekennen aan teams A en B, spel 2 aan C en D, spel 3 aan E en F enz. Dit doen we door de elementen M(A,1) en M(B,1) de waarde 1 te geven, M(C,1) en M(D,1) worden 2 enz.
(Het eerste element, het rijnummer, geef ik even met een letter aan zodat steeds duidelijk is dat het om een teamnummer gaat. In een programmeertaal is dit natuurlijk een getal).
In de matrix G zetten we G(1,2) en G(2,1) op 1, om aan te geven dat teams A en B tegen elkaar hebben gespeeld. Dit geldt ook voor G(3,4) en G(4,3), G(5,6) en G(6,5) enz.

Nu gaan we ronde 2 vaststellen. We zetten 'spelnummer=1' en zoeken twee teams waaraan we dit spel kunnen toekennen. Hiervoor tasten we de gehele kolom 2 af, en bekijken of aan deze voorwaarden wordt voldaan:
Wanneer het spelnummer minder is dan 6, verhogen we het spelnummer (spelnummer wordt 2) en herhalen de procedure, net zolang totdat spel 6 is toegekend.

Al snel zal dit vastlopen: Een bepaald spel kunnen we niet plaatsen. Dan moeten we van achter naar voren keuzes wissen. We annuleren het laatst gekozen team (bijbehorend element in M wordt weer 0). Als dit een tweede team bij een spel is, moeten we ook de bijbehorende elementen in de matrix G weer op 0 zetten. Vervolgens zoeken we vooruit naar een volgend team dat aan alle criteria voldoet.

Het kan zijn dat we alle wedstrijden in een bepaalde ronde moeten wissen. Dan gaan we terug naar de voorgaande ronde, en wissen daar het laatst gekozen team. Als alles netjes verloopt, zijn er uiteindelijk twee mogelijkheden:
Hopelijk lukt het hiermee. Zo niet, dan wil ik me wellicht op zo'n programmaatje storten, maar ik kan niet beloven dat ik hier binnenkort voldoende tijd voor heb. Je zou hoe dan ook eerst moeten aangeven op welke wijze de randvoorwaarden wat versoepeld kunnen worden, want -zoals eerder opgemerkt- zijn met de getelde eisen geen 12 ronden met 12 teams mogelijk.

Aanvulling (dankzij een mede-beantwoorder): op deze site vind je een heleboel oplossingen van gelijksoortige problemen. Wellicht zit er iets bruikbaars tussen:

GHvD
10-4-2018


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#86038 - Rijen en reeksen - Ouder