Strona główna » Algorytmy » Teoria Liczb » Liczby Harmoniczne
1n
 

Liczby Harmoniczne

https://mattomatti.com/a77

Definicja

Liczby Harmoniczne są to sumy odwrotności pierwszych n liczb naturalnych. Wzór na n-tą liczbę harmoniczną ma postać:

Prosta Implementacja

Najprostsza funkcja wyliczająca n-tą liczbę Harmoniczną można zapisać przy pomocy pojedynczej pętli for. Należy oczywiście pamiętać, że kolejne ułamki muszą zostać dodane do zmiennej double:

  1. double harmoniczna(int n){
  2.   double w = 0;
  3.   for(int i = 1; i <= n; i++)
  4.     w+=1.0/i;
  5.   return w;
  6. }

(1.) Funkcja harmoniczna() wylicza dla podanego argumentu n wartość n-tej liczby harmonicznej. (2.) Zadeklarowanie zmiennej w. (3.) Wyliczanie kolejnych wyrazów sumy i (4.) ich dodanie do w. Na koniec (5.) program zwraca wartość zmiennej w.

Taka implementacja posiada znaczącą wadę - wszystkie wyliczone wartości mogą być obarczone błędem zaokrąglenia czego przyczyną jest przechowywanie danych. Przykładem, który ma wpływ na wynik jest np. ułamek .

Implementacja

Struktura

W przypadku liczb Harmonicznych lepszym pomysłem jest napisanie funkcji harmoniczna(), która zwróci ułamek. Oczywiście, aby to osiągnąć potrzebny będzie nowy typ danych. Każdy ułamek składa się z licznika i mianownika, dlatego zadeklarowana struktura będzie miała dwie zmienne typu int:

  1. struct ulamek {
  2.   int licznik;
  3.   int mianownik;
  4. };

Dodawanie ułamków

Następny krok polega na napisaniu dodatkowej funkcji, która pozwoli dodać dwa ułamki, ponieważ dla C++ jest to całkowicie nowy typ i nie potrafi takiej operacji wykonać. Dla ułatwienie można skorzystać z poniższego wzoru na dodawanie:

  1. ulamek dodajUlamki(ulamek a, ulamek b){
  2.   ulamek w = {a.licznik*b.mianownik + b.licznik*a.mianownik, a.mianownik*b.mianownik};
  3.   return w;
  4. }

(1.) Funkcja dodająca dwa ułamki przyjmie dwie zmienne a i b typu ulamek. Wynikiem będzie typ ulamek, który będzie wynikiem a + b. (2.) Do nowej zmiennej przypisz wynik a + b i (3.) zwróć nową zmienną.

Wyliczanie liczby Harmonicznej

Ze względu na nowy typ danych potrzebne są zmiany w oryginalnym kodzie funkcji harmoniczna():

  1. ulamek harmoniczna(int n){
  2.   ulamek w = {1, 1};
  3.   ulamek a = {1, 1};
  4.   for(int i = 2; i <= n; i++){
  5.     a.mianownik = i;
  6.     w = dodajUlamki(w, a);
  7.   }
  8.   return w;
  9. }

(1.) Funkcja harmoniczna() zwraca typ ulamek dla podanego argumentu n. Zadeklarowanie zmiennej (2.) w której będzie przechowywany wynik oraz (3.) ulamek, który w każdej pętli zmieniany i dodawany. (4.) Dla każdego składnika prócz pierwszego: (5.) utwórz i-ty ułamek i (6.) sumą zmiennych w i a dodaj do w. Na koniec (8.) zwróć wynik zmiennej w.

Wypisanie typu ulamek

W celu wykorzystania napisanego kodu potrzebna jest jeszcze funkcja, która wypisze wartości przechowywane w zmiennej typu ulamek. Jej postać może wyglądać następująco:

  1. void wypiszUlamek(ulamek a){
  2.   cout << a.licznik << "/" << a.mianownik << " = " << double(a.licznik) / a.mianownik << endl;
  3. }

(1.) Funkcja wypiszUlamek() przyjmuje jeden argument a na podstawie którego (2.) wypisany jest ułamek oraz jego wartość dziesiętna.

Testowanie funkcji

Pierwsze dziesięć liczb Harmonicznych wypisuje poniższa wartość main():

  1. int main () {
  2.   for(int i = 1; i <= 10; i++){
  3.     wypiszUlamek(harmoniczna(i));
  4.   }
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz program na podstawie obecnego kodu źródłowego tak, aby spełniał poniższe punkty:

  1. Powinien wczytać liczbę n, która określi ile liczb Harmonicznych ma być wypisanych
  2. Ułamki w trakcie wykonywania programu powinny być skracane
  3. Wszystkie ułamki powinny być wypisywanie jako ułamki mieszane

Przykładowo dla argumentu n = 4 zostanie wypisane na konsoli:

  1. 1 = 1
  2. 1 1/2 = 1.5
  3. 1 5/6 = 1.83333
  4. 2 1/12 = 2.08333