Co to jest algorytm przesuwnego okna? Przykłady?

Question

Podczas rozwiązywania problemu z geometrią natrafiłem na podejście o nazwie Algorytm okna przesuwnego.

Nie można znaleźć żadnych materiałów/informacji na ten temat.

O czym jest algorytm?

Answer 1

Zasadniczo przesuwne okno jest podlistą, która przebiega nad kolekcją leżącą u podstaw. To znaczy, jeśli masz tablicę jak

[a b c d e f g h] 

przesuwne okno o rozmiarze 3 będzie działać na nim jak

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

Jest to przydatne, jeśli na przykład chcemy obliczyć średnią działa, lub jeśli chcesz utworzyć zestaw wszystkich sąsiednich par itp.

Answer 2

To jest kod protokołu przesuwanego okna dla tablicy o rozmiarze n, gdzie suma liczb k jest przechowywana razem w innej sumie tablicowej. Poniższy kod znajduje się w Javie .

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]); 
     } 
    } 
}