CKTIS / C
Fenêtre glissante pour des valeurs non négatives
Une fenêtre glissante délimite une portion contiguë d’un tableau et déplace ses bornes sans recalculer toute la somme à chaque fois. La variante qui rétrécit la fenêtre suppose que les valeurs d’entrée sont non négatives.
Version : 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.Une fenêtre glissante est délimitée par une borne gauche et une borne droite. Quand la borne droite avance, la valeur suivante est ajoutée à la somme courante. Dès que la somme atteint le seuil, la borne gauche avance tant que la condition reste satisfaite, et les valeurs retirées sont soustraites. Chaque élément entre dans la fenêtre au plus une fois et en sort au plus une fois. Le parcours prend donc un temps linéaire.
Il est essentiel que les valeurs d’entrée soient non négatives. Ajouter un nombre non négatif ne peut pas faire diminuer la somme, et le retirer à gauche ne peut pas la faire augmenter. Cette monotonie permet de rétrécir la fenêtre sans risque. Avec des valeurs négatives, ce raisonnement ne tient plus et il faut utiliser un autre algorithme.
L’exemple cherche la portion contiguë la plus courte dont la somme vaut au moins 7. Pour 2, 1, 5, 2, 3, 2, le programme affiche 2, car la portion 5, 2 satisfait la condition.
Exemples
#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;
}Résultat
2
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.