Berekening ter vervanging van brute-force algoritme

[Verwijderd]

Wellicht een hele domme vraag, maar ik probeer het volgende uit te rekenen en wellicht weet iemand hiervoor een methode om dit te berekenen behalve brute-force.

Ik heb een array met integers van 1 t/m 65536. De waarde van deze integers worden elke keer bij elkaar opgeteld in een som, dus als volgt:

code:

Integers: 1, 2, 3, 4, 5, 6, 7, 8, ...
Totaal: 1, 3, 6, 10, 15, 21, 28, 36, ...

Wat ik nu probeer te achterhalen is op basis van een willekeurig getal, welke integer uit de originele array daarbij hoorde. Dus bijvoorbeeld waarde 12 zou als resultaat 4 moeten geven en waarde 31 zou 7 terug moeten geven.

Weet iemand die misschien wel heeft opgelet tijdens wiskunde op de basisschool hoe ik dit kan berekenen? Het is vast heel dom, maar ik kom er even niet uit. Nu doe ik het op een hele eenvoudige brute-force manier, maar dit ik erg lelijk en traag.

[orf]

Ik heb ook niet zo goed opgelet bij wiskunde. Waarom geeft waarde 12 als resultaat 4 en 31 als resultaat 7?

[Verwijderd]

orf schreef op zaterdag 14 oktober 2017 @ 20:26:
Ik heb ook niet zo goed opgelet bij wiskunde. Waarom geeft waarde 12 als resultaat 4 en 31 als resultaat 7?

Het is een beetje lastig uit te leggen, maar ik zoek de grootst mogelijke waarde uit de originele array met integers waarvan de som kleiner is dan de gezochte waarde. Misschien wordt het iets duidelijker als ik dit voorbeeld volledig uitwerk.

code:

Waarden: 1 -> 1
Waarden: 2, 3 -> 2
Waarden: 4, 5, 6 -> 3
Waarden: 7, 8, 9, 10 -> 4
Waarden: 11, 12, 13, 14, 15 -> 5
Waarden: 16, 17, 18, 19, 20, 21 -> 6
Waarden: 22, 23, 24, 25, 26, 27, 28 -> 7
Waarden: 29, 30, 31, 32, 33, 34, 35, 36 -> 8

Etc.

Ik hoop dat dit een beetje duidelijk maakt wat ik probeer te doen. Ik weet helaas niet hoe ik dit beter kan uitleggen.

[GlowMouse]

De som S_n = 0.5n(n+1) (meetkundige reeks). Je wilt dus oplossen: 12 = 0.5n(n+1). Dit is een kwadratische functie met één positieve oplossing (abc-formule). Rond die af naar beneden voor je antwoord.

[Verwijderd]

GlowMouse schreef op zaterdag 14 oktober 2017 @ 20:36:
De som S_n = 0.5n(n+1) (meetkundige reeks). Je wilt dus oplossen: 12 = 0.5n(n+1). Dit is een kwadratische functie met één positieve oplossing (abc-formule). Rond die af naar beneden voor je antwoord.

Ok, ik snap nu hoe ik de som kan berekenen voor elke integer in de array.

code:

(n / 2) * (n - 1)

(7 / 2) * (7 - 1) = 21

Ik voel me echt heel dom, maar hoe doe je precies de berekening andersom? Ik heb de abc-formule opgezocht, maar ik kom er nog niet uit.

[Voutloos]

Begin maar eerst met de slordige off-by-one errors weghalen:
Ten eerste: In je openingspost staat 12 -> 4, in je 2e post staat 12 -> 5.
Ten tweede: GlowMouse geeft een formule welke klopt met de integers vs totalen in je openingspost, en nu presteer je het om van de '+1' een '-1' te maken.

Ik had verwacht dat met n=7, je (7/2) * (7+1) = 3.5 * 8 = 28 als totaal zou willen.

[jmerle]

Handig linkje over je reeks: https://oeis.org/A000217

Het omgekeerde kan je op Stack Overflow wel wat over vinden: https://stackoverflow.com/a/2913319

Oftewel:

Om van integer (n) naar antwoord (x) te gaan:
x = n * (n + 1) / 2

Om van antwoord (x) naar integer (n) te gaan:
n = (sqrt(8 * x + 1) - 1) / 2

Om te kijken of random (x) een waarde is in de reeks van triangulaire nummers:
sqrt(8 * x + 1) % 1 == 0

[ Voor 9% gewijzigd door jmerle op 14-10-2017 21:12 ]

[Verwijderd]

Bedankt voor de hulp. Met de berekening van Stroopwafel kom ik er inderdaad uit. En ook enorm bedankt voor de linkjes. Ik moet me echt weer eens gaan verdiepen in de wiskunde .

Want ook al kan ik het nu berekenen met die formule, ik snap er nog geen reet van. Vooral die constante waarde 8 in de formule n = (sqrt(8 * x + 1) - 1) / 2 is me een raadsel. Maar nu ik weet op welke zoektermen ik moet zoeken kom ik er denk ik wel uit. Voldoende stof in ieder geval om door te nemen tijdens mijn komende X aantal WC bezoeken!

[Carbon]

Verwijderd schreef op zaterdag 14 oktober 2017 @ 21:15:
Bedankt voor de hulp. Met de berekening van Stroopwafel kom ik er inderdaad uit. En ook enorm bedankt voor de linkjes. Ik moet me echt weer eens gaan verdiepen in de wiskunde .

Want ook al kan ik het nu berekenen met die formule, ik snap er nog geen reet van. Vooral die constante waarde 8 in de formule n = (sqrt(8 * x + 1) - 1) / 2 is me een raadsel.

tip: Google op abc formule