CKTIS / C
Finestra scorrevole per valori non negativi
Una finestra scorrevole mantiene un intervallo contiguo di un array e ne sposta i limiti senza ricalcolare ogni volta l’intera somma. La variante che restringe la finestra richiede valori di input non negativi.
Versione: C23; repository compiler flag, production runtime not attested
Sintassi
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.Una finestra scorrevole è delimitata da un estremo sinistro e uno destro. Quando l’estremo destro avanza, il valore successivo viene aggiunto alla somma corrente. Una volta raggiunta la soglia, l’estremo sinistro avanza finché la condizione resta soddisfatta, e i valori rimossi vengono sottratti. Ogni elemento entra nella finestra al massimo una volta e ne esce al massimo una volta, quindi la scansione richiede tempo lineare.
È essenziale che i valori di input siano non negativi. Aggiungere un numero non negativo non può diminuire la somma, e rimuoverlo da sinistra non può aumentarla. Questo comportamento monotono permette di restringere la finestra in sicurezza. Con valori negativi, il ragionamento non vale più e serve un altro algoritmo.
L’esempio trova l’intervallo contiguo più corto la cui somma è almeno 7. Per 2, 1, 5, 2, 3, 2, il programma stampa 2 perché l’intervallo 5, 2 soddisfa la condizione.
Esempi
#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;
}Risultato
2
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.