Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C

Posuvné okno pre nezáporné hodnoty

Posuvné okno udržiava súvislý úsek poľa a posúva jeho hranice bez toho, aby zakaždým znova sčítavalo všetky prvky. Variant so zmenšovaním okna vyžaduje nezáporné vstupné hodnoty.

Verzia: 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.

Posuvné okno vymedzuje ľavá a pravá hranica. Pri posune pravej hranice sa k priebežnému súčtu pripočíta ďalšia hodnota. Keď súčet dosiahne prah, ľavá hranica sa posúva doprava, kým podmienka platí, a odoberané hodnoty sa odpočítavajú. Každý prvok vstúpi do okna najviac raz a najviac raz ho opustí. Prechod poľom preto trvá lineárny čas.

Podmienka nezáporných vstupných hodnôt je nevyhnutná. Pripočítanie nezáporného čísla nemôže súčet znížiť a jeho odobratie zľava ho nemôže zvýšiť. Vďaka tejto monotónnosti možno okno bezpečne zmenšovať. Pri záporných hodnotách táto úvaha neplatí a treba použiť iný algoritmus.

Príklad hľadá najkratší súvislý úsek so súčtom aspoň 7. Pre 2, 1, 5, 2, 3, 2 program vypíše 2, pretože úsek 5, 2 spĺňa podmienku.

Prí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ýsledok

2

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje