Che cos'è l'algoritmo per finestre scorrevoli? Esempi?

Question

Mentre risolvo un problema di geometria, mi sono imbattuto in un approccio chiamato Algoritmo della finestra scorrevole.

Impossibile trovare materiale di studio/dettagli su di esso.

Di cosa tratta l'algoritmo?

Answer 1

In generale una finestra scorrevole è un sottoelenco che scorre su una raccolta sottostante. Vale a dire, se si dispone di una matrice come

[a b c d e f g h] 

una finestra scorrevole di dimensioni 3 correva su di essa come

[a b c] 
    [b c d] 
    [c d e] 
     [d e f] 
     [e f g] 
      [f g h] 

Questo è utile se, ad esempio, vuole calcolare una media in esecuzione, o se si voglio creare un insieme di tutte le coppie adiacenti ecc.

Answer 2

Questo è il codice del protocollo della finestra scorrevole per una matrice di dimensione n, dove somma di k numeri è memorizzata insieme in un'altra somma di array. Il seguente codice è in Java .

import java.io.*; 
class deva 
{ 
    public static void main(String args[])throws IOException 
    { 
     BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
     int n=Integer.parseInt(in.readLine()); 
     int[] a = new int[n]; 
     for(int i=0;i<n;i++) 
     a[i]=Integer.parseInt(in.readLine()); 
     int k=Integer.parseInt(in.readLine()); 
     int[] sum = new int[n-k+1]; 
     for(int i=0;i<k;i++) 
     sum[0]+=a[i]; 
     System.out.println(sum[0]); 
     for(int i=1;i<n-k+1;i++) 
     { 
     sum[i]=sum[i-1]+a[i+k-1]-a[i-1]; 
     System.out.println(sum[i]); 
     } 
    } 
}