KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Schuivend venster voor niet-negatieve waarden

Een schuivend venster houdt een aaneengesloten deel van een array bij en verschuift de grenzen zonder telkens de hele som opnieuw te berekenen. De variant die het venster verkleint, vereist niet-negatieve invoerwaarden.

Versie: C23; repository compiler flag, production runtime not attested

Syntax

Use this shrinking-window rule only when all input values are nonnegative and the target is strictly positive. Use a running-sum type that can represent every intermediate sum without overflow, including the sum immediately after adding an element and before shrinking the window. Maintain left and right window boundaries and add each entering value to the running sum. While the current sum is at least the target, compare the current window length with the shortest found so far and update it if needed. Then subtract the leftmost value and advance the left boundary, even if that removal drops the sum below the target. An empty window has sum zero, so the positive target ensures that the loop stops before attempting to remove another element.

Een schuivend venster heeft een linker- en een rechtergrens. Wanneer de rechtergrens opschuift, wordt de volgende waarde bij de lopende som opgeteld. Zodra de som de drempel bereikt, schuift de linkergrens op zolang aan de voorwaarde wordt voldaan. De waarden die uit het venster verdwijnen, worden afgetrokken. Elk element komt hoogstens één keer in het venster en gaat er hoogstens één keer uit. Het doorlopen kost dus lineaire tijd.

Het is essentieel dat de invoerwaarden niet-negatief zijn. Door een niet-negatief getal toe te voegen kan de som niet dalen, en door het links weg te halen kan de som niet stijgen. Door dit monotone gedrag kun je het venster veilig verkleinen. Bij negatieve waarden gaat die redenering niet meer op en is een ander algoritme nodig.

Het voorbeeld zoekt het kortste aaneengesloten deel met een som van minstens 7. Voor 2, 1, 5, 2, 3, 2 geeft het programma 2 als uitvoer, omdat het deel 5, 2 aan de voorwaarde voldoet.

Voorbeelden

#include <stddef.h>
#include <stdio.h>

int main(void) {
    const int values[] = {2, 1, 5, 2, 3, 2};
    const size_t count = sizeof values / sizeof values[0];
    const int target = 7;
    size_t left = 0;
    size_t best = count + 1;
    int sum = 0;

    for (size_t right = 0; right < count; ++right) {
        sum += values[right];
        while (sum >= target) {
            const size_t length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left++];
        }
    }

    if (best == count + 1) printf("none\n");
    else printf("%zu\n", best);
    return 0;
}

Resultaat

2

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen