Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Posuvné okno pro nezáporné hodnoty

Posuvné okno udržuje souvislý úsek pole a posouvá jeho hranice, aniž by pokaždé znovu sčítalo všechny prvky. Varianta se zmenšováním okna vyžaduje nezáporné vstupní hodnoty.

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

Syntaxe

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.

Posuvné okno vymezují levá a pravá hranice. Při posunu pravé hranice se k průběžnému součtu přičte další hodnota. Jakmile součet dosáhne prahu, levá hranice se posouvá doprava, dokud podmínka platí, a odebírané hodnoty se odečítají. Každý prvek vstoupí do okna nejvýše jednou a nejvýše jednou ho opustí. Průchod proto trvá lineární čas.

Podmínka nezáporných vstupních hodnot je zásadní. Přičtení nezáporného čísla nemůže součet snížit a jeho odebrání zleva ho nemůže zvýšit. Díky této monotónnosti lze okno bezpečně zmenšovat. U záporných hodnot tato úvaha neplatí a je potřeba jiný algoritmus.

Příklad hledá nejkratší souvislý úsek se součtem alespoň 7. Pro 2, 1, 5, 2, 3, 2 program vypíše 2, protože úsek 5, 2 splňuje podmínku.

Příklady

#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;
}

Výsledek

2

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje