Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Sumy prefiksowe

SPIS TREŚCI
Tematy pomocnicze

Problem

Dla m  par indeksów ( i, j  ) należy wyznaczyć sumę elementów tablicy T  o indeksach od i  do j, ij.

Rozwiązanie

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
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
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, mC.
i, j  –  indeksy w tablicy T. i, jC.

Wyjście:

m sum częściowych tablicy T.

Elementy pomocnicze

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

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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.