CKTIS / C
Drseče okno za nenegativne vrednosti
Drseče okno ohranja strnjen odsek tabele in premika njegovi meji, ne da bi vsakič znova seštelo vse elemente. Različica, ki okno oži, zahteva nenegativne vhodne vrednosti.
Različica: C23; repository compiler flag, production runtime not attested
Sintaksa
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.Drseče okno določata leva in desna meja. Ko se desna meja premakne, se naslednja vrednost prišteje k trenutni vsoti. Ko vsota doseže prag, se leva meja pomika v desno, dokler je pogoj izpolnjen, vrednosti, ki zapustijo okno, pa se odštejejo. Vsak element vstopi v okno največ enkrat in ga zapusti največ enkrat. Prehod zato poteka v linearnem času.
Pogoj, da so vhodne vrednosti nenegativne, je bistven. Prištevanje nenegativnega števila ne more zmanjšati vsote, odstranitev takega števila na levi pa je ne more povečati. Ta monotonost omogoča varno oženje okna. Pri negativnih vrednostih ta razlaga ne velja več in potreben je drug algoritem.
Primer poišče najkrajši strnjeni odsek, katerega vsota je vsaj 7. Za 2, 1, 5, 2, 3, 2 program izpiše 2, ker odsek 5, 2 izpolnjuje pogoj.
Primeri
#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;
}Rezultat
2
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.