Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemDla m par indeksów
|
Pierwszym, narzucającym się rozwiązaniem jest proste policzenie sumy
elementów tablicy
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
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
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
Rozwiązanie problemu będzie dwuetapowe. W pierwszym etapie wyliczamy tablicę
sum
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
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
|
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. |
// 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)) Next S(0) = 0 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 |
Python
(dodatek)# Sumy prefiksowe # Data: 4.03.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- import random N = 15 # Liczba elementów M = 10 # Liczba sum częściowych # ********************** # *** PROGRAM GŁÓWNY *** # ********************** T = [] S = [0] * (N + 1) for k in range(N): # Ustawiamy tablice T i S T.append(random.randrange(-N+1,N)) S[k+1] = S[k] + T[k] print("T = ", end="") # Wyświetlamy obie tablice for k in range(N): print("%4d" % T[k], end="") print() print("S = ", end="") for k in range(N+1): print("%4d" % S[k], end="") print() print() for k in range(1,M+1): # Wyliczamy sumy częściowe i = random.randrange(N) # Losujemy indeksy j = random.randrange(N) if i > j: i,j = j,i print("Suma od T[%2d] do T[%2d] wynosi %d" % (i,j,S[j+1]-S[i])) |
Wynik: |
T = -4 -3 5 -12 -7 -7 3 -7 11 1 -10 10 5 -1 -7 S = 0 -4 -7 -2 -14 -21 -28 -25 -32 -21 -20 -30 -20 -15 -16 -23 Suma od T[ 1] do T[ 3] wynosi -10 Suma od T[ 3] do T[ 7] wynosi -30 Suma od T[ 5] do T[11] wynosi 1 Suma od T[ 4] do T[10] wynosi -16 Suma od T[ 6] do T[13] wynosi 12 Suma od T[ 8] do T[13] wynosi 16 Suma od T[ 9] do T[14] wynosi -2 Suma od T[ 0] do T[ 5] wynosi -28 Suma od T[ 2] do T[ 3] wynosi -7 Suma od T[ 5] do T[ 9] wynosi 1 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.