Springen naar inhoud

Een zo klein mogelijke omvattende rechthoek


  • Log in om te kunnen reageren

#1

Revelation

    Revelation


  • >1k berichten
  • 2364 berichten
  • Technicus

Geplaatst op 03 december 2005 - 10:54

Ik doe mee aan de voorrondes van de informatica olympiade, maar weet even niet hoe het verder moet. Het gaat om deze opdracht. Ik dacht aan een vorm van backtracking, met de grootste beginnen en dan kijken of de wat kleinere blok minder dan de helft van de grote is. Zo weet je dat je de één na grootste en diegene daarna naast de grootste kan zetten zonder dat die twee hoger dan de grootste zijn.

Heeft iemand een slimmer/beter idee?

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

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 03 december 2005 - 12:03

Het lijkt me dat in een optimale oplossing ieder vierkant met minstens één hoek aan een hoek van een ander vierkant ligt.

Dus zo:
Geplaatste afbeelding
Op deze wijze kun je een vierkant op 8 manieren aan een ander vierkant leggen, dus als je begint met de eerste heb je nog 85[.]5! mogelijkheden voor de rest (die 5! is omdat de volgorde waarin je de rest aanlegt wel van belang kan zijn). Voor het tweede vierkant wat je neerlegt maakt het bovendien niet uit waar je hem aansluit bij het eerste, want dat leidt toch alleen tot oplossingen die symmetrisch zijn, dus eigenlijk zijn er maar 84[.]5! (een kleine half miljoen) mogelijkheden. Daarvan vallen er halverwege ook nog een hele boel af (je kunt geen vierkanten neerleggen aan hoekpunten waar al eerder een vierkant aan hebt gelegd, die kun je dus als 'bezet' markeren) maar zelfs die half miljoen mogelijkheden moet prima te brute forcen zijn lijkt me :roll:
In theory, there's no difference between theory and practice. In practice, there is.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures