Algorytmy i Struktury Danych

Pierwszym, narzucającym się rozwiązaniem jest proste policzenie sumy elementów tablicy od T [ i ] do T [ j ] i zwrócenie wyniku. Gdyby to był pojedynczy problem, to oczywiście tak należałoby postąpić. Tutaj jednak musimy wyznaczyć m takich sum. Aby nie powtarzać zliczania elementów tablicy, utwórzmy tablicę tzw. sum prefiksowych. Element i-ty tej tablicy jest sumą elementów elementów od T [ 0 ] do T [ i-1 ].

Przykład:

Załóżmy, że mamy tablicę T o następującej zawartości:

T	indeks	0	1	2	3	4	5	6	7	8	9
T	zawartość	-5	3	8	12	4	-7	-2	1	0	-6

Wyliczamy dla tej tablicy tablicę sum prefiksowych. Pierwszy element tej tablicy jest zawsze równy 0. Następne elementy powstają przez dodanie do elementu poprzedniego kolejnego elementu z tablicy T. Tablica sum prefiksowych ma o 1 element więcej niż tablica T.

S	indeks	0	1	2	3	4	5	6	7	8	9	10
S	zawartość	0	-5	-2	6	18	22	15	13	14	14	8

Aby teraz otrzymać sumę elementów od T [ i ] do T [ j ] wystarczy odjąć S [ j+1 ] - S [ i ]. Dlaczego? S [ j + 1 ] jest sumą kolejnych elementów od T [ 0 ] do T [ j ]. S [ i ] jest sumą elementów od T [ 0 ] do T [ i-1 ], mamy:

S [ j + 1 ] - S [ i ] = T [ 0 ] + T [ 1 ] + ... + T [ j -1 ] = T [ j ] - T [ 0 ] - T [ 1 ] - ... - T [ i-2 ] - T [ i - 1 ] = T [ i ] = T [ i + 1 ] + ... + T [ j-1 ] = T [ j ]

Widzisz zatem, że w sumie pozostają tylko elementy od T [ i ] do T [ j ].

Rozwiązanie problemu będzie dwuetapowe. W pierwszym etapie wyliczamy tablicę sum prefiksowych S. W drugim etapie odczytujemy m, po czym m razy odczytujemy indeksy i oraz j. Wyznaczamy sumę od T [ i ] do T [ j ] jako różnicę S [ j = 1 ] - S [ i ] i zwracamy wynik. Zaletą tego rozwiązania jest to, że sumy liczymy raz w czasie O ( n ).

Algorytm liczenia sum częściowych tablicy za pomocą sum prefiksowych

Wejście:

T	–	tablica z elementami do sumowania.
n	–	liczba elementów w tablicy T.
m	–	liczba sum, m ∈ C.
i, j	–	indeksy w tablicy T. i, j ∈ C.

Wyjście:

m sum częściowych tablicy T.

Elementy pomocnicze

S	–	tablica sum prefiksowych o rozmiarze n + 1.
k	–	indeks, k ∈ C.

Lista kroków

K01:	S [ 0 ] ← 0	pierwsza suma równa zero
K02:	Dla k = 0, 1, ..., n - 1: wykonuj S [ k + 1 ] ← S [ k ] + T [ k ]	suma prefiksowa
K03:	Czytaj m	liczba sum częściowych
K04:	Dla k = 1, 2, ..., m: wykonuj kroki K05...K06
K05:	Czytaj i, j	odczytujemy indeks początku i końca sumy częściowej
K06:	Pisz S [ j + 1 ] - S [ i ]	zwracamy sumę częściową od T [ i ] do T [ j ]
K07:	Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy tablicę T o 15 pseudolosowych elementach. Następnie wylicza dla tej tablicy sumy prefiksowe, po czym generuje 10 razy losowe indeksy i oraz j i wypisuje sumy częściowe od T [ i ] do T [ j ].

Pascal

// Sumy prefiksowe
// Data: 26.09.2015
// (C)2015 mgr Jerzy Wałaszek
//---------------------------

program project1;

const N = 15;                       // Liczba elementów
      M = 10;                       // Liczba sum częściowych

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  T : array [ 0..N-1 ] of integer;
  S : array [ 0..N ]   of integer;
  i, j, k, x : integer;
begin
  Randomize;                        // Inicjujemy generator pseudolosowy
  for k := 0 to N - 1 do            // Ustawiamy tablicę T
    T [ k ] := random ( N ) - random ( N );
  S [ 0 ] := 0;
  for k := 0 to N-1 do              // Wyliczamy sumy prefiksowe
    S [ k+1 ] := S [ k ] + T [ k ];
  write ( 'T = ' );                 // Wyświetlamy obie tablice
  for k := 0 to N - 1 do write ( T [ k ] :4 );
  writeln;
  write ( 'S = ' );
  for k := 0 to N do write ( S [ k ] :4 );
  writeln;
  writeln;
  for k := 1 to M do    // Wyliczamy sumy częściowe
  begin
    i := random ( N );  // Losujemy indeksy
    j := random ( N );
    if i > j then
    begin
      x := i; i := j; j := x;
    end;
    writeln ( 'Suma od T [ ', i:2, ' ] do T [ ', j:2, ' ] wynosi ', S [ j + 1 ] - S [ i ] );
  end;
end.

C++

// Sumy prefiksowe
// Data: 26.09.2015
// (C)2015 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 15;                // Liczba elementów
const int M = 10;                // Liczba sum częściowych

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main( )
{
  int T [ N ], S [ N+1 ], i, j, k;

  srand ( time ( NULL ) );       // Inicjujemy generator pseudolosowy
  for( k = 0; k < N; k++ )            // Ustawiamy tablicę T
    T [ k ] = ( rand( ) % N ) - ( rand( ) % N );
  S [ 0 ] = 0;
  for( k = 0; k < N; k++ )       // Wyliczamy sumy prefiksowe
    S [ k+1 ] = S [ k ] + T [ k ];
  cout << "T = ";                // Wyświetlamy obie tablice
  for( k = 0; k < N; k++ ) cout << setw ( 4 ) << T [ k ];
  cout << endl << "S = ";
  for( k = 0; k <= N; k++ ) cout << setw ( 4 ) << S [ k ];
  cout << endl << endl;
  for( k = 0; k < M; k++ )       // Wyliczamy sumy częściowe
  {
    i = rand( ) % N;  // Losujemy indeksy
    j = rand( ) % N;
    if( i > j ) swap ( i, j );
    cout << "Suma od T [ " << setw ( 2 ) << i
         << " ] do T [ " << setw ( 2 ) << j
         << " ] wynosi " << S [ j + 1 ] -S [ i ] << endl;
  }
  return 0;
}

Basic

' Sumy prefiksowe
' Data: 26.09.2015
' (C)2015 mgr Jerzy Wałaszek
'---------------------------

const N = 15                       ' Liczba elementów
const M = 10                       ' Liczba sum częściowych

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer T ( 0 To N-1 )
Dim As Integer S ( 0 To N )
Dim As Integer i, j, k

Randomize                          ' Inicjujemy generator pseudolosowy
For k = 0 To N - 1                 ' Ustawiamy tablic T
  T ( k ) = Int ( N * ( Rnd - Rnd ) )
  S ( 0 ) = 0
Next
For k = 0 To N-1                   ' Wyliczamy sumy prefiksowe
  S ( k+1 ) = S ( k ) + T ( k )
Next
Print "T = ";                      ' Wyświetlamy obie tablice
For k = 0 To N - 1: Print Using "####";T ( k );: Next
Print
Print "S = ";
For k = 0 To N: Print Using "####";S ( k );: Next
Print
Print
For k = 1 To M         ' Wyliczamy sumy częściowe
  i = Int ( Rnd * N )  ' Losujemy indeksy
  j = Int ( Rnd * N )  
  If i > j Then Swap i, j
  Print Using "Suma od T [ ## ] do T [ ## ] wynosi &";i;j;S ( j+1 )-S ( i )
Next
End

Wynik:

T = 2 1 5 11 6 -4 -4 -11 6 12 3 3 -4 12 1
S = 0 2 3 8 19 25 21 17 6 12 24 27 30 26 38 39

Suma od T [ 5 ] do T [ 12 ] wynosi 1
Suma od T [ 0 ] do T [ 14 ] wynosi 39
Suma od T [ 8 ] do T [ 11 ] wynosi 24
Suma od T [ 11 ] do T [ 14 ] wynosi 12
Suma od T [ 5 ] do T [ 8 ] wynosi -13
Suma od T [ 8 ] do T [ 11 ] wynosi 24
Suma od T [ 13 ] do T [ 14 ] wynosi 13
Suma od T [ 5 ] do T [ 11 ] wynosi 5
Suma od T [ 0 ] do T [ 5 ] wynosi 21
Suma od T [ 1 ] do T [ 7 ] wynosi 4

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sumy prefiksowe