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.

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.

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].

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.

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. }

• Kod źródłowy Implementacja