Strona główna » Algorytmy » Teoria Liczb » Liczby Ludic
 

Liczby Ludic

Definicja

Pierwszą liczbą Ludic jest 1. W celu wyznaczenia kolejnych liczb Lucia należy wziąć zbiór liczb naturalnych bez 1, pobrać pierwszy element k na liście, a następnie wykreślić co k-tą liczbę zaczynając od pierwszej liczby. Proces ten jest powtarzany.

Ciąg Liczb

Pierwsze 15 wyrazów liczb Ludic to: 1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47,..

Przykład

Wyznaczmy pierwsze 5 liczb Ludic. Pierwszą liczbę przyjmujemy jako 1. Kolejne operacje zostały przedstawione w tabelce.

Liczba LudicZbiór
1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ..}
2{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15..}
3{3, 5, 7, 9, 11, 13, 15..}
5{5, 7, 11, 13, ..}
7{7, 11, 13, ..}

Pierwszymi pięcioma liczbami Ludic są: 1, 2, 3, 5, 7...

Implementacja

Zadanie

Napisz program, który wczyta pewną wartość b, a następnie wypisze wszystkie liczby Ludic z zakresu [1, b]. Przetestuj działanie napisanej funkcji.

Strategia

Podczas wyznaczania liczb Ludica zostanie użyta tylko jedna lista liczb. Dodatkowo w pamięci będzie przetrzymywany indeks p. Wszystkie liczby o indeksie mniejszym od p będą liczbami, które są już znalezionymi liczbami Ludica, a liczby o indeksach o wartości co najmniej p to lista liczb z których należy wykreślać wartości. Algorytm kończy działanie, gdy p jest równa liczbie elementów na liście.

Przykład

Poniższy przykład prezentuje działanie algorytmu, który wyszuka wartości Ludica w przedziale [1, 10]. Pomiędzy wartości została wstawiona kreska |, która symbolizuje podział wyznaczany przez wartość p.

pLiczba LudicZbiór
12{1 | 2, 3, 4, 5, 6, 7, 8, 9, 10}
23{1, 2 | 3, 5, 7, 9}
35{1, 2, 3 | 5, 7}
47{1, 2, 3, 5 | 7}
5-{1, 2, 3, 5, 7 |}

W przedziale [1, 10] znaleziono następujące liczby Ludica: {1, 2, 3, 5, 7}.

Optymalizacja

Jeśli znaleziona liczba Ludica to a to następna liczba do wykreślenia to będzie 2a. Na liście może nie być tyle elementów, aby indeks 2a istniał. Oznacza to, że obliczenia można przerwać już w momencie znalezienia takiej liczby Ludica, która nie wykreśli, ani jednej liczby. W przedstawionym przykładzie pozwoliłoby to zakończyć działanie już po znalezieniu wartości 5.

Rozwiązanie

Poniższa funkcja liczbyLudica() implementuje przedstawiony wcześniej algorytm wraz z optymalizacją. Przyjmuje jeden argument b i zwraca listę liczb Ludica z zakresu [1, b].

C++
C#
  1. vector<int> liczbyLudica(int zakres) {
  2.   vector<int> lista;
  3.   for (int i = 1; i <= zakres; i++)
  4.     lista.push_back(i);
  5.   int p = 1;
  6.   while (p + 2*lista[p] < lista.size()) {
  7.     int i = p + lista[p];
  8.     while (i < lista.size()) {
  9.       lista.erase(lista.begin() + i, lista.begin() + i + 1);
  10.       i += lista[p] - 1;
  11.     }
  12.     p++;
  13.   }
  14.   return lista;
  15. }

(2. - 4.) Utwórz listę liczb z zakresu. (5.) Pomijamy wykreślanie liczb dla wartości 1 i (6.) dopóki istnieje szansa, że następna liczba Ludica k wykreśli jakąkolwiek liczbę to: (7.) obliczamy pierwszy element do wykreślenia i (8. - 11.) wykreślamy wszystkie wielokrotności tej liczby z zakresu. (10.) Tutaj należy pamiętać, że chociaż następna wielokrotność jest k pozycji dalej to po (9.) usunieciu elementu trzeba przesunięcie zmniejsza się o 1. Po wykreśleniu wszystkich elementów: (12.) zwiększamy indeks p, aby p-ta liczba została uznana za liczbę Ludica. Na koniec (14.) zwracana jest lista z odpowiednio wykreślonymi wartościami.

Testowanie funkcji

W celu przetestowania napisanego programu można posłużyć się poniższym fragmentem kodu. Wczytuje on od użytkownika wartość b, pobiera listę liczb Ludica i ją wypisuje.

C++
C#
  1. int main () {
  2.   int b;
  3.   cout << "Podaj zakres [1, b]:\n b = ";
  4.   cin >> b;
  5.   vector<int> lista = liczbyLudica(b);
  6.   cout << "\nLiczby Ludica z zakresu [1, " << b << "]\n";
  7.   for (int i = 0; i < lista.size(); i++)
  8.     cout << lista[i] << " ";
  9.   system("pause");
  10.   return 0;
  11. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1