Soultaker schreef op vrijdag 8 december 2023 @ 12:29:
Ik zie niet direct hoe dit
worst case beter is. Je zegt zelf al dat de gecombineerde lengte worst case gelijk is aan het kleinste gemene veelvoud van de lengte van de invoerlussen. Dan creëer je worst case dus een lus van de lengte die gelijk is aan het antwoord, maar dan had je net zo goed kunnen simuleren.
Misschien begrijp ik je verkeerd, maar volgens mij is dat is niet waar? De simulatie kan veel meer stappen bevatten dan het in 1x combineren van de lus met idd de Chinese reststelling*.
Bijvoorbeeld: lus A heeft 100 stappen, met een oplossing op stap 1. Lus B heeft 101 stappen, met een oplossing op stap 50. Dan kun je dus ofwel 98 keer itereren om een oplossing te vinden, of je rekent gewoon uit dat na 49 lussen van B, de oplossingen van A en B overlappen. En dat dat zich herhaalt na LCM(100,101) stappen. Dus AB is een nieuwe lus met 10100 stappen, en een oplossing na 4999 stappen.
Bij m oplossingen in A en n oplossingen in B heb je maximaal nm overlappende oplossingen in AB. Dus voor elke oplossing in A reken je uit hoeveel stappen het kost om te overlappen met elke oplossing in B, waar mogelijk.
*edit: Wacht, is het wel de Chinese reststelling? Volgens mij wil je het omgekeerde. De oplossingen
ai van A kun je schrijven als
n = ai (mod |A|)
En de oplossingen
bj van B als
n = bj (mod |B|)
Dan dan zoek je alle
nij die voldoen voor elke combinatie van
ai en
bj
edit2: Ah, brainfart, dat is precies de Chinese reststelling, maar die geldt alleen als gcd(|A|, |B|) = 1, wat geen gegeven is. Maar goed, een stelsel van lineaire congruenties is natuurlijk ook oplosbaar als gcd(|A|, |B|) ≠ 1
[
Voor 31% gewijzigd door
.oisyn op 09-12-2023 01:48
]