Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2009 mgr Jerzy Wałaszek I LO w Tarnowie

Przykładowe zastosowania klasy vector

Wyszukiwanie zadanej ilości liczb pierwszych

Zdefiniujmy nasz problem:

Umieścić w wektorze n (n > 2) początkowych liczb pierwszych.

Najefektywniejszą metodą znajdowania liczb pierwszych są tzw. sita (ang. Sieves). W naszym serwisie znajdziesz opis kilku z nich:

Sito Eratostenesa
Sito Liniowe
Sito Atkina-Bernsteina

Jednakże dla celów edukacyjnych wykorzystamy dużo prostszy algorytm i łatwiejszy do zrozumienia - wyszukiwanie liczb pierwszych przez sprawdzanie podzielności. Opiera się on na spostrzeżeniu, iż dana liczba jest liczbą pierwszą, jeśli nie dzieli się bez reszty przez żadną poprzedzającą ją liczbę pierwszą (liczby pierwsze większe od pierwiastka z badanej liczby możemy pominąć - dlaczego?). Aby zoptymalizować algorytm, damy dwie początkowe liczby pierwsze - 2 i 3. Pozostałe będziemy już wyznaczali algorytmicznie.

Każda kolejna liczba pierwsza nie może dzielić się ani przez 2, ani przez 3. Zatem musi być postaci:

p = 6k ± 1, gdzie k = 1,2,...

Uzasadnienie tego wzoru jest proste:

Tylko 6k ± 1 daje przy podziale przez 2 i 3 resztę 1. Pozostałe przypadki są podzielne przez 2 lub przez 3:

Pozostaje jedynie 6k + 1 i 6k - 1, które nie dzielą się ani przez 2, ani przez 3, zatem mogą być liczbami pierwszymi (nie będą, jeśli dzieli je jakaś inna liczba pierwsza niż 2 i 3, co może się zdarzyć przy większym k).

Zasada działania naszego algorytmu będzie zatem następująca:

Po odczytaniu n tworzymy pusty wektor i umieszczamy w nim trzy początkowe liczby pierwsze.

W pętli, która sprawdza długość wektora z n generujemy liczby postaci 6k ± 1, a następnie sprawdzamy ich podzielność przez kolejne liczby pierwsze z wektora (pomijamy przy tym 2 i 3, ponieważ wygenerowane liczby nie dzielą się ani przez 2, ani przez 3). Sprawdzenie podzielności kontynuujemy dotąd, aż liczba pierwsza z wektora przekroczy wartość pierwiastka całkowitego z wygenerowanej liczby. Jeśli żadna z tych liczb nie dzieli wygenerowanej liczby, to jest ona pierwsza i dopisujemy ją do wektora. W ten sposób wektor zwiększa swą długość i jeśli osiągnie ona wartość n, to pętla generacji liczb pierwszych zostanie przerwana.

Wypisujemy zawartość wektora i kończymy algorytm.

Program w C++

// Program 001/2009
// I LO w Tarnowie
// Przykładowy program wykorzystujący wektor do generacji
// zadanej ilości początkowych liczb pierwszych metodą
// sprawdzania podzielności przez wcześniejsze liczby
// pierwsze
//-------------------------------------------------------

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

main()
{

  // Tworzymy pusty wektor P, który będzie przechowywał wygenerowane przez program liczby pierwsze
  
  vector<int> P;  
  
  // W wektorze umieszczamy trzy początkowe
  // liczby pierwsze 2, 3 i 5
  
  P.push_back(2); P.push_back(3); P.push_back(5);
  
  // Odczytujemy ilość liczb pierwszych do wygenerowania
  
  int n; cin >> n;
  
  // Tworzymy zmienne pomocnicze
  // p - kandydat na liczbę pierwszą
  // g - pierwiastek całkowity z p
  // k i d do generacji p wg wzoru p = 6k +- d
  
  int p, g, i, k = 1, d = 1;
  
  // W pętli poszukujemy liczb pierwszych dotąd aż wypełnią wektor P do rozmiaru n
  
  while(P.size() < n)
  {

  // Wyznaczamy kandydata na liczbę pierwszą wg wzoru p = 6k +- 1
  
    p = 6 * k + d;
    
  // Obliczamy pierwiastek całkowity z p.
  
    g = int(sqrt(p));
    
  // Sprawdzamy podzielność p przez liczby z wektora P aż do momentu, gdy przekroczą one granicę g.
  // Sprawdzanie podzielności rozpoczynamy od dzielnika 5!
  
    for(i = 2; P[i] <= g; i++)
  
  // Jeśli liczba z wektora P dzieli liczbę p, to p nie może być liczbą pierwszą - zerujemy p
  // i przerywamy pętlę.
  
      if(!(p % P[i]))
      {
        p = 0; break;
      }

  // Jeśli po zakończeniu pętli for liczba p ma wartość różną od zera, to nie była podzielna przez żadną
  // z wybranych liczb z wektora P. A zatem liczba p jest pierwsza i dopisujemy ją do wektora P.
  
    if(p) P.push_back(p);

  // Modyfikujemy zmienne pomocnicze do tworzenia następnego p
  
    if(d == -1) d = 1;
    else
    {
      d = -1; k++;
    }
  }
  
  // Wyświetlamy wynik
  
  for(i = 0; i < P.size(); i++) cout << P[i] << " ";
  
  cout << endl << endl;
  
  system("PAUSE");
}

Duże potęgi liczby 2

Zadanie jest następujące:

Wyznacz wartość 2¹⁰²⁴ z dokładnością wszystkich cyfr.

Oczywiście bardzo szybko się przekonasz, iż takiej wartości potęgi nie obliczy żaden normalny kalkulator. Również język C++ nie posiada standardowego typu danych obejmującego taki zakres liczb. Liczba 2¹⁰²⁴ w zapisie dwójkowym zbudowana jest z 1025 bitów, tymczasem największy typ całkowity unsigned long long ma ich zaledwie 64! Musimy zatem wybrać inne podejście.

Po pierwsze zauważamy, iż kolejne potęgi liczby 2 można obliczać rekurencyjnie sumując ze sobą poprzednio wyznaczoną potęgę:

2⁰ = 1
2¹ = 2 = 1 + 1 = 2⁰ + 2⁰

2² = 4 = 2 + 2 = 2¹ + 2¹

2³ = 8 = 4 + 4 = 2² + 2²

...

2ⁿ = 2^n-1 + 2^n-1

Po drugie liczbę zapamiętujemy w postaci cyfr, nad którymi wykonujemy znaną ze szkoły podstawowej operację dodawania. Cyfry sumujemy ze sobą poczynając od końca zapisu liczby. Jako nową cyfrę przyjmujemy ostatnią cyfrę sumy. Jeśli suma jest większa od 10, to przenosimy 1 do następnej pozycji. Jeśli zsumowaliśmy wszystkie cyfry i wciąż mamy przeniesienie, to dopisujemy je na początku wszystkich cyfr.

Zatem zadanie będzie następujące:

W wektorze umieszczamy cyfrę 1 - jest to początkowa potęga 2⁰. Aby zoptymalizować dodawanie cyfr liczba będzie zapisana w wektorze wspak.

W pętli wykonywanej 1024 razy dodajemy do siebie cyfry w wektorze stosując ogólne zasady dodawania.

Wyświetlamy wspak zawartość wektora.

Program w C++

[na zajęciach]

Liczby ciągu Fibonacciego

Zadanie jest następujące:

Znaleźć 1000-czną liczbę ciągu Fibonacciego.

Ciąg liczb Fibonacciego powstaje rekurencyjnie wg wzoru:

f₀ = 0
f₁ = 1
f_i = f_i-1 + f_i-2

Ze wzoru tego wynika, iż i-ta liczba Fibonacciego, i > 1, jest sumą dwóch poprzednich liczb Fibonacciego. Wypiszmy kilka początkowych liczb tego ciągu:

0  1  1  2  3  5  8  13  21  34  55  89  ...

Wartości liczb Fibonacciego szybko rosną i znów okaże się, iż zadania tego nie rozwiążemy przy pomocy standardowego typu liczb całkowitych dostępnego w C++. Zastosujemy zatem podejście z poprzedniego zadania - do przechowywania liczb Fibonacciego wykorzystamy 3 wektory. W pierwszych dwóch będziemy przechowywali zawsze dwie ostatnie liczby Fibonacciego. W trzecim będziemy tworzyli ich sumę, po czym przesuniemy zawartości tych wektorów:

F1 ← F2 ← F3

Program w C++

[na zajęciach]

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe