Strona główna » Algorytmy » Teoria Liczb » Ciąg arytmetyczny
 

Ciąg arytmetyczny

Definicja

Ciąg arytmetyczny to taki ciąg w którym różnica dwóch kolejnych wyrazów jest stała i wynosi r. Dla takiego ciągu definiuje się następujący wzór na n + 1 wyraz:

an + 1 = an + r

gdzie: an - oznacza n-ty wyraz ciągu, a r to różnica ciągu arytmetycznego.

Przykłady

a1rKolejne wyrazy ciągu
313, 4, 5, 6, 7, ...
10510, 15, 20, 25, 30, ...
6-26, 4, 2, 0, -2, ...

Cel

Celem artykułu jest wyjaśnienie jak zaimplementować w programie funkcje, które pozwolą na obliczanie wyrazów ciągu i sprawdzanie jego cech przy pomocy języka C++.

Implementacja

n-ty wyraz

Pierwszą funkcją, która przyda się podczas implementacji innych funkcji będzie wyliczała n-ty wyraz ciągu arytmetycznego:

  1. int podajNwyraz_rekurencja(int a1, int r, int n){
  2.   if (n == 1){
  3.     return a1;
  4.   } else {
  5.     return r + podajNwyraz_rekurencja(a1, r, n - 1);
  6.   }
  7. }

Jest to wersja rekurencyjna kodu do obliczania n-tego wyrazu zgodnie z wyżej podanym kodem. (1.) Program przyjmuje trzy argumenty: a1 - pierwszy wyraz ciągu, r - różnica ciągu arytmetycznego oraz n - numer wyrazu do wyznaczenia. (2.) Jeśli numer wyrazu jest równy 1 to (3.) należy zwrócić a1. W przeciwnym wypadku (5.) zgodnie ze wzorem należy zwrócić sumę wyrazu poprzedniego oraz różnicy ciągu.

Jednak zdecydowanie lepszym rozwiązaniem jest wyliczanie n-tego wyrazu nie przy pomocy rekurencji, a gotowego stałego wzoru: an = a1 + (n - 1)r. Wtedy kod znacząco upraszcza się do jednej linijki i nie wymaga żadnej rekurencji:

  1. int podajNwyraz(int a1, int r, int n){
  2.   return a1 + (n - 1)*r;

Suma n pierwszych wyrazów

W celu zsumowania n pierwszych wyrazów ciągu i nie korzystając z wzoru podawanego na zajęciach z matematyki kod może wyglądać tak:

  1. int sumaNwyrazow(int a1, int r, int n){
  2.   int s = 0;
  3.   for (int i = 1; i <= n; i++)
  4.     s += podajNwyraz(a1, r, i);
  5.   return s;
  6. }

Jednak ponownie jak w poprzednim przypadku wystarczy specjalny wzór: i liczba operacji wykonywanych przez komputer jest stała i niezależna od ilości sumowanych wyrazów:

  1. int sumaNwyrazow_wzor(int a1, int r, int n){
  2.   return (a1 + podajNwyraz(a1, r, n))*(n/2)
  3. }

Czy ciąg arytmetyczny?

Ze względu na fakt, że ciąg arytmetyczny ma stałą różnicę pomiędzy wyrazami to z tego wynika, że . Na podstawie tej własności można napisać program, który będzie sprawdzał czy wprowadzony ciąg liczb jest ciągiem arytmetycznym:

  1. bool czyArytmetyczny(int* l, int n) {
  2.   for (int i = 1; i + 1 < n; i++)
  3.     if (double(l[i - 1] + l[i + 1]) / 2 != l[i])
  4.       return false;
  5.   return true;
  6. }

(1.) Funkcja zwraca wartość logiczną, która określa czy liczby zapisane na liście l o długości n spełniają kryterium ciągu arytmetycznego. (2.) Dla każdego wyrazu (prócz pierwszego i ostatniego): (3.) należy sprawdzić czy zachodzi warunek. Uwaga: należy pamiętać, że podczas dzielenie może dojść do błędu zaokrąglenie, dlatego sumę należy rzutować na typ double.. (4.) Jeśli choć raz warunek nie jest spełniony można od razu zwrócić fałsz. Jeśli jednak program nie przerwie pętli for to program zwróci prawdę.

Testowanie funkcji

Powyższe funkcje można sprawdzić przy pomocy poniższego programu:

  1. int main() {
  2.   int a1, r, n;
  3.   cout << "Podaj pierwszy wyraz oraz roznice r:";
  4.   cin >> a1 >> r;
  5.   cout << "Ktory wyraz ciagu podac? ";
  6.   cin >> n;
  7.   cout << podajNwyraz(a1, r, n);
  8.   cout << "Podaj ile elementow chcesz wczytac: ";
  9.   cin >> n;
  10.   int* l = new int[n];
  11.   cout << "Podaj " << n << " liczb: ";
  12.   for (int i = 0; i < n; i++)
  13.     cin >> l[i];
  14.   cout << (czyArytmetyczny(l, n) ? "" : "nie ");
  15.   cout << "jest ciąg arytmetyczny";
  16.   delete[] l;
  17.   system("pause");
  18.   return 0;
  19. }

Zadania

Zadanie 1

Napisz funkcje generuj_ciag(), która utworzy nową listę o zadanej długości n, a kolejne elementy listy będą odpowiadały kolejnym wyrazom ciągu począwszy od pierwszego wyrazu. Spróbuj napisać funkcję bez użycia funkcji o podobnym działaniu do funkcji podajNwyraz()

Zadanie 2

Napisz funkcje sumakn(), która będzie obliczała sumę wyrazów począwszy od numeru k do numeru n. Funkcja powinna mieć nagłówek sumakn(int a1, int r, int k, int n)