Springen naar inhoud

wiskundig probleem (een lange rij)


  • Log in om te kunnen reageren

#1

ngozi

    ngozi


  • 0 - 25 berichten
  • 1 berichten
  • Gebruiker

Geplaatst op 07 oktober 2013 - 20:45

wie kan mij helpen met het volgende probleem (uitleg).

de getallen van 9 cijfers die gevromd worden door de cijfers 1,2,3,4,5,6,7,8,9.
worden naar grootte gerangschikt. in de rij die ontstaat staat 123456789 vooraan.
welk getal staat op de 100.000-ste plaats.

alvast bedankt!


voor als het niet helemaal duidelijk is,
het gaat van klein naar groot.

123456798. dan komt 123456879,123456897....enz tot 987654321

Veranderd door ngozi, 07 oktober 2013 - 21:04


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

#2

dietervdf

    dietervdf


  • 0 - 25 berichten
  • 14 berichten
  • Gebruiker

Geplaatst op 07 oktober 2013 - 21:36

Tof probleem, Ik heb een methode gevonden die toch wel wat rekenwerk vereist...

Als je het probleem herleidt valt er iets op. De getallen zijn in groepjes te verdelen.
Voorbeeld: tot 4 cijfers 1 tot 4 met als eerste 1234
We verkrijgen een rij van 4! = 24 getallen.

1234
1243
1324
1342
1423
1432

2134
...

Die getallen vallen te verdelen in 4 groepen van 6 (24 mogelijkheden / aantal mogelijkheden voor de eerste plaats)
Stel dat ik het 17e getal zoek, dan weet ik zeker dat dit begint met een 3. (de eerste 6 beginnen met 1, de volgende 6 met 2 enz...)

Hierna kan je het 2 getal vinden. Daar heb ik je immers nog 3 mogelijkheden, te verdelen over 6. Ze vallen te splitsen in groepjes van 2. We zochten het 17e getal (zonder de 12 van de eerste 2 groepen hebben we nog het 5e getal over). Hierdoor zijn we zeker dat dit getal in het groepje zit dat begint met een 34.

Nu hebben we nog 2 mogelijkheden over, en dit te verdelen over 2 groepjes. Hier is het vrij logisch dat het volgende getal 1 moet zijn. Het complete 17e getal is dus 3412 (het 18e getal is 3421 en het 19 begint met een 4)


Hetzelfde principe kan je toepassen op 9 cijfers en de 100 000 ste plaats. Wel wat werk.. Er bestaat waarschijnlijk een kortere methode voor?

#3

paac

    paac


  • >250 berichten
  • 271 berichten
  • Ervaren gebruiker

Geplaatst op 25 oktober 2013 - 09:26

Grappig om dit weer eens te zien.
Onlangs heb ik dit probleem ook opgelost bij Project Euler met een algoritme.

Door slim de getallen te wisselen kon ik alle permutaties maken en dan de 1.000.000e vinden.
Later kwam ik ook het wiki-artikel erover tegen met het algoritme dat de stappen beschrijft.

Met de methode van dietervdf is het nog mogelijk om dit wat sneller te doen door een ander start punt te nemen en alleen de benodigde permuaties te maken.

Plan? I don't need a plan, just a goal. The rest will follow on its own.
Clever waste of time: Level 31


#4

paac

    paac


  • >250 berichten
  • 271 berichten
  • Ervaren gebruiker

Geplaatst op 25 oktober 2013 - 14:30

Met de methode van dietervdf is het nog mogelijk om dit wat sneller te doen door een ander start punt te nemen en alleen de benodigde permuaties te maken.


Ik had het nog niet getest, maar als je alleen het 100.000e getal wilt hebben, dan kan met de methode van dietervdf het probleem dmv pen/papier/rekenmachine in een paar stappen worden uitgerekend(had voor mezelf het algoritme nodig, dus niet in deze methode verdiept eerst).

Voorbeeld van Project Euler met 0 t/m 9 en 1 miljoenste positie gaat dan als volgt
Er zijn 10! mogelijkheden welke zijn te verdelen in 10 * 9! sub-permutaties, dan ga je 9! met 1 t/m 10 vermenigvuldigen en kijken op welke positie hij boven de waarde 1.000.000 komt
Voor begin getal 0 gaat van positie 1 t/m 1 * 9! = 362.880
Voor begin getal 1 gaat van positie 362.881 t/m 2 * 9! = 725.760
Voor begin getal 2 gaat van positie 725.761 t/m 3 * 9! = 1.088.640

Hij komt boven de 1.000.000, dus het eerste getal van de permutatie is 2.
Neem een nieuwe permutatie zonder 2 (ofwel 0, 1, 3, 4, 5, 6, 7, 8, 9) en berekend de rest-waarde
100.000.000 - 725.760 = 274.240

Herhaal nu met voor 1 t/m 9 en 8! (het is nu 8! omdat er één mogelijkheid minder is)
Voor begin getal 0 gaat van positie 1 t/m 1 * 8! = 40.320
Voor begin getal 1 gaat van positie 40.321 t/m 2 * 8! = 80.640
Voor begin getal 3 gaat van positie 80.641 t/m 3 * 8! = 120.960
Voor begin getal 4 gaat van positie 120.961 t/m 4 * 8! = 161.280
Voor begin getal 5 gaat van positie 161.281 t/m 5 * 8! = 201.600
Voor begin getal 6 gaat van positie 201.601 t/m 6 * 8! = 241.920
Voor begin getal 7 gaat van positie 241.921 t/m 7 * 8! = 282.240

Hij komt boven de 274.240, dus het tweede getal van de permutatie is 7.
Neem een nieuwe permutatie zonder 7 (ofwel 0, 1, 3, 4, 5, 6, 8, 9) en berekend de rest-waarde
274.240 - 241.920 = 32.320

Dit kun je blijven herhalen totdat je de permutatie hebt.
Hetzelfde principe werkt ook voor jou vraagstuk :)

Veranderd door paac, 25 oktober 2013 - 14:30

Plan? I don't need a plan, just a goal. The rest will follow on its own.
Clever waste of time: Level 31






0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures