Liczby Wyczerpujące

Definicja

Liczby Wyczerpujące w systemie liczbowym o bazie b to taka liczba, która zawiera co najmniej jedną każdą cyfrę w danym systemie liczbowym. Liczba Wyczerpująca nie może mieć na początku cyfr 0. W każdym systemie istnieje takich liczb nieskończenie wiele i zawsze istnieje możliwość wyznaczenia liczby najmniejszej w danym systemie.

Przykład

Załóżmy, że jesteśmy w systemie binarnym. Wtedy najmniejszą liczbą Wyczerpującą jest 10₂, ponieważ zawiera wszystkie możliwe cyfry. 11₂ już nie jest, ponieważ same cyfry 1, ale liczba 100₂ już jest. Poniżej została przedstawiona tabelka systemów od binarnego do dziesiętnego z podaną najmniejszą liczbą Wyczerpującą:

Pewnie nietrudno zauważyć, że najprostszym sposobem na uzyskanie liczby Wyczerpującej polega na zapisaniu wszystkich cyfr w kolejności rosnącej, a następnie zamianie dwóch najmniej znaczących cyfr: 0 i 1.

Implementacja

W poniższej implementacji zakłada się, że wybranym systemem liczbowym będzie każdy od binarnego do dziesiętnego włącznie. Dla następnych systemów program nie będzie działał prawidłowo.

Najmniejsza liczba

Na początek napiszmy funkcję najmniejszaWyczerpujaca(), która będzie przyjmowała jeden argument b, który określi w jakim systemie liczbowym ma zostać zwrócona liczba. W celu zwiększenia wartości systemu liczbowego zwracana będzie tablica znaków, a nie typ liczbowy.

1. char* najmniejszaWyczerpujaca(int b) {
2.   char* liczba = new char[b + 1];
3.   liczba[0] = '1';
4.   liczba[1] = '0';
5.   for (int i = 2; i < b; i++)
6.     liczba[i] = '0' + i;
7.   liczba[b] = '\0';
8.   return liczba;
9. }

(2.) Utwórz listę o b + 1 znakach tj. (na każdą cyfrę systemu b oraz znak końca danych). (3., 4.) Pierwsze dwie cyfry są zawsze znane. (5. - 6.) Dalsze cyfry to kolejne cyfry w danym systemie. (7.) Na koniec należy dodać znak końca danych i (8.) zwrócić tablice reprezentującą liczbę.

Zwiększ liczbę

Kolejny krok polega teraz na dopisaniu funkcji, która pozwoli uzyskać liczbę większą o 1. Ze względu na fakt, że liczba będzie tablicą znaków to trzeba napisać własną funkcję, która doda do liczby wartość 1. Funkcja przyjmuje dwa argumenty: tablicę znaków l oraz b - system liczbowy w jakim zapisana jest liczba.

1. char* zwiekszLiczbe(char* liczba, int b) {
2.   int dl = strlen(liczba);
3.   int przenies = 1;
4.   for (int i = dl - 1; i >= 0; i--) {
5.     int wartosc = (liczba[i] - '0') + przenies;
6.     liczba[i] = (wartosc % b) + '0';
7.     przenies = (int)(wartosc / b);
8.   }

(2.) Pobierz długość liczba. (3.) Ustal początkowo, że najmniej znacząca cyfra jest zwiększana o 1. (4. - 8.) Następnie wykonaj dodawanie pisemne. Po tym procesie wartość zmiennej przenies może (9.) nie być równa zero i wtedy należy rozszerzyć tablice.

9.   if (przenies != 0) {
10.     char* data = new char[dl + 2];
11.     data[0] = przenies + '0';
12.     for (int i = 0; i < dl; i++)
13.       data[i + 1] = liczba[i];
14.     data[dl + 1] = '\0';
15.     delete liczba;
16.     return data;
17.   }
18.   return liczba;
19. }

Rozszerzanie tablicy polega na (10.) zadeklarowaniu nowej tablicy, (11.) dopisania brakującej wartości, (12. - 13.) przepisaniu pozostałych cyfr i (14.) dopisaniu znaku końca danych. Potem bardzo ważne, aby (15.) zdeaalokować poprzednią listę reprezentującą liczbę i (16.) zwrócić nowy wskaźnik na nową "liczbę". (18.) W przypadku, gdy nie ma potrzeby rozszerzania wskaźnik się nie zmienia.

Czy wyczerpująca?

W celu sprawdzenia czy liczba jest wyczerpująca spełniony musi być warunek, że wszystkie cyfry danego systemu liczbowego występują przynajmniej jeden raz. Najprostszym sposobem na implementację jest dodanie funkcji sprawdzCzyWyczerpujaca(), która zadeklaruje pomocniczą tablicę danych typu bool o długości równej ilości cyfr i ustawi wszystkie wartości na fałsz. Następnie program sprawdzi wszystkie cyfry po kolei i jeśli po pętli wszystkie wartości listy są prawdą to znaczy, że podana liczba jest wyczerpująca:

1. bool sprawdzCzyWyczerpujaca(char* liczba, int b) {
2.   bool* data = new bool[b];
3.   for (int i = 0; i < b; i++)
4.     data[i] = false;
5.   for (int i = 0; i < strlen(liczba); i++)
6.     data[liczba[i] - '0'] = true;
7.   bool wynik = true;
8.   for (int i = 0; i < b; i++)
9.     wynik &= data[i];
10.   delete data;
11.   return wynik;
12. }

(2.) Zadeklaruj tablicę, gdzie będzie zapisywane czy dany znak występuje. (3. - 4.) Ustal początkowo, że żadna liczba nie występuje. (5.) Dla każdej cyfry w liczba: (6.) ustaw odpowiedni element listy data na prawdę. (7. - 9.) Znajdź koniunkcję występowania wszystkich cyfr. Potem (10.) usuń zadeklarowaną na początku funkcji tablice i (11.) zwróć wynik.

Ciąg liczb Wyczerpujących

W celu optymalizacji szukania liczb Wyczerpujących za liczbę początkową należy przyjąć najmniejszą liczbę wskazaną przez najmniejszaWyczerpujaca(). Następnie zwiększając wartość o 1 i po kolei sprawdzając czy dana liczba jest wyczerpująca można wypisać n kolejnych liczb ciągu. Funkcja realizująca to zadanie wygląda następująco:

1. void wypisznWyczerpujacych(int b, int n) {
2.   char* data = najmniejszaWyczerpujaca(b);
3.   cout << data << endl;
4.   while (n-- > 0) {
5.     do {
6.       data = zwiekszLiczbe(data, b);
7.     } while (!(sprawdzCzyWyczerpujaca(data, b)));
8.     cout << data << endl;
9.   }
10.   delete data;
11. }

(2.) Pobierz najmniejszą liczbę i (3.) ją wypisz. (4.) Wypisz kolejne n-1 liczb: (6.) zwiększając wartość liczby, aż do (7.) znalezienia kolejnej liczby wyczerpującej. Przed skończeniem iteracji (8.) należy wypisać dane na ekran. (10.) Przed zakończeniem funkcji należy zwolnić pamięć.

Testowanie funkcji

Poniższy fragment programu wczytuje od użytkownika dwie liczby: b i n, a następnie wypisuje n pierwszych liczb Wyczerpujących w systemie b.

1. int main () {
2.   int b, n;
3.   cout << "Podaj system liczbowy: ";
4.   cin >> b;
5.   cout << "Podaj ile liczb Wyczerpujących wypisac: ";
6.   cin >> n;
7.   wypisznWyczerpujacych(b, n);
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja