hoeveel routes heb je bij 13 steden?

Hoe stel je hiervoor een algoritme op?

Toegevoegd na 5 minuten:
Of hoe los je dit op een andere manier snel op?

Verwijderde gebruiker

10 jaar geleden

in: Wiskunde

719

719 keer bekeken

Heb je meer informatie nodig om de vraag te beantwoorden? Reageer dan hier.

Antwoorden (2)

Het aantal verbindingswegen bij 13 steden is 13*12/2.
Pak een willekeurige stad, en je kunt 12 verbindingswegn tekenen. Naar elke andere stad één. Dat kun je dus vanuit elk van de 13 steden doen. dus 12*12. Maar je hebt ze dan allemaal twee keer getekend. Een keer van de ene stad naar de andere, en een keer van de andere naar de ene. Vandaar dus delen door 2.

(Lees meer...)

Reddie

10 jaar geleden

gvrox

10 jaar geleden

Nu het aantal routes nog :)

Ligt eraan wat je met routes bedoelt. Als je bedoelt dat je 1 route alle 13 steden aangedaan moeten worden en dat je bij iedere stad moet kunnen beginnen met de route, dan is het eenvoudig. Dan is het dus namelijk hetzelfde als alle mogelijke volgordes van die steden. Je kunt dan voldoen met de berekening 13 faculteit oftwel 6.227.020.800 mogelijke routes. Als er ook minder dan 13 steden aangedaan mogen worden dan moet je bij bovengenoemd getal 12 faculteit, 11 faculteit, 10 faculteit etc. optellen.

Toegevoegd na 10 minuten:
Vergeet mijn laatste zin. Als het namelijk mogelijk is om minder dan 13 steden aan te doen, dan wordt de formule heel anders. Je hebt dan namelijk van iedere lagere faculteit 13 mogelijkheden. Dus 13! + 13(12!) + 13(11!) + 13(10!) etc.

(Lees meer...)

Verwijderde gebruiker

10 jaar geleden

kierkegaard47

10 jaar geleden

Ook die verbetering klopt niet precies. Stel dat je bv. het aantal routes voor 11 steden (uit een totaal van 13) zou willen bepalen. Dan vraag je eigenlijk naar hoeveel "rijtjes van 11" uit een totaal van 13 kunt maken waarbij de volgorde er toe doet, ofwel (wiskundig gezegd) het aantal permutaties van 11 uit 13. Er zijn 13 'eerste steden' waar je uit kunt kiezen, 12 'tweede steden' etc, dus krijg je 13* 12 * ... * 4 * 3 ofwel 13!/2! Algemener kan je k steden uit 13 bezoeken op 13! / (13-k)! manieren als de volgorde er toe doet. Je sommatieformule zou dus worden: 13!/0! + 13!/1! + 13!/2! + 13!/3! +13!/4! ... 13!/13!= 13! ( 1 + 1/2! +1/3! + ... 1/13!) Die laatste uitdrukking zijn precies de eerste termen van de taylorontwikkeling van e^x rond 0. Deze reeks convergeert dan ook superhard naar e=2.71828.. en je kan dan ook afleiden dat bovenstaande uitdrukking veel sneller berekend kan worden als e^0 * 13! naar beneden afgerond.= 16.926.797.486 (zie voor een strakkere afleiding hiervan o.a. http://math.stackexchange.com/questions/161314/what-is-the-sum-of-following-permutation-series-np0-np1-np2-cdots-npn
) En dan is er natuurlijk nog de mogelijkheid om routes mee te nemen waarbij steden méér dan eens aangedaan worden...

kierkegaard47

10 jaar geleden

euh... waar ik 'e^x rond 0' schreef, en 'e^0' had ik natuurlijk 'e^x rond 1' en 'e^1' moeten schrijven, mijn excuses.

Weet jij het beter..?

Het is niet mogelijk om je eigen vraag te beantwoorden Je mag slechts 1 keer antwoord geven op een vraag Je hebt vandaag al antwoorden gegeven. Morgen mag je opnieuw maximaal antwoorden geven.

0 / 2500