Sumy prefiksowe


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych
Zbiory rozłączne – implementacja listowa
Zbiory rozłączne – implementacja za pomocą drzew

Problem

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

 

 

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 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 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  

 

Program

Ważne:

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].

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.