Zaimplementuj w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który dokona konwersjikonwersja między systemami liczbowymikonwersji liczby zapisanej w dowolnym systemie liczbowym o podstawie nie większej niż 16 na liczbę dziesiętną.
Algorytm powinien mieć złożoność nie większą niż O(n).
Specyfikacja problemu:
Dane:
n – liczba cyfr liczby
liczba – ciąg znaków reprezentujący liczbę naturalną zapisaną w systemie liczbowym o podstawie podstawa
podstawa – podstawa systemu liczbowego, z którego dokonujemy konwersji liczby do systemu dziesiętnego; liczba naturalna dodatnia, nie większa niż 16
Wynik:
liczba_dziesietny – wartość liczby liczba w systemie dziesiętnym; liczba naturalna
Uwaga!
Do zapisania algorytmu możesz wykorzystać tylko podstawowe operacje arytmetyczne: dodawanie, odejmowanie, mnożenie oraz operacje takie jak: przypisanie wartości do zmiennych, operacje porównania, operacje wywołania samodzielnie napisanych funkcji wykorzystujących wyżej wymienione operacje oraz funkcji ascii(x), która pozwala na zamianę znaku x na liczbę całkowitą równą jego kodowi ASCII. Dopuszczone jest również użycie pętli, instrukcji warunkowych, tablic oraz odwoływanie się do pojedynczego elementu tablicy. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, dostępnych w językach programowania
Przykładowe rozwiązanie
W rozwiązaniu wykorzystamy schemat Hornera (omówiony w innym e‑materiale). Nasze rozwiązanie będzie się różnić od przedstawionego w załączonym materiale tym, że podstawą systemu liczbowego, w którym jest zapisana konwertowana liczba, może być dowolna liczba nie większa od 16, oraz tym, że jako wartość początkową liczby w systemie dziesiętnym przyjmiemy wartość 0, zamiast pierwszej cyfry zapisu liczby w wybranym systemie liczbowym.
1. Definiujemy zmienne:
skladnik – zmienna pomocnicza typu całkowitego, wykorzystywana do konwersji,
liczba_dziesietny – zmienna przechowująca wynik; wartość liczby w systemie dziesiętnym; liczba naturalna,
kod – kod ASCII pojedynczej cyfry; liczba naturalna.
Linia 1. skladnik ← 0.
Linia 2. liczba podkreślnik dziesietny ← 0.
Linia 3. kod ← 0.
skladnik ← 0
liczba_dziesietny ← 0
kod ← 0
2. Dodajemy pętlę dla. Umieszczone wewnątrz niej instrukcje pozwolą przekształcić liczbę zapisaną w systemie liczbowym o podstawie podstawa do postaci dziesiętnej. Korzystamy z funkcji ascii().
Linia 1. skladnik ← 0.
Linia 2. liczba podkreślnik dziesietny ← 0.
Linia 3. kod ← 0.
Linia 5. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n wykonuj dwukropek.
Linia 6. kod ← ascii otwórz nawias okrągły liczba otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 8. jeżeli kod zamknij nawias ostrokątny znak równości ascii otwórz nawias okrągły cudzysłów A cudzysłów zamknij nawias okrągły i kod otwórz nawias ostrokątny znak równości ascii otwórz nawias okrągły cudzysłów F cudzysłów zamknij nawias okrągły dwukropek.
Linia 9. kratka konwertujemy znaki cudzysłów A cudzysłów minus cudzysłów F cudzysłów na liczby 10 minus 15.
Linia 10. skladnik ← kod minus ascii otwórz nawias okrągły apostrof A apostrof zamknij nawias okrągły plus 10.
Linia 11. w przeciwnym razie dwukropek.
Linia 12. kratka konwertujemy znaki cudzysłów 0 cudzysłów minus cudzysłów 9 cudzysłów na cyfry 0 minus 9.
Linia 13. skladnik ← kod minus ascii otwórz nawias okrągły apostrof 0 apostrof zamknij nawias okrągły.
Linia 15. liczba podkreślnik dziesietny ← liczba podkreślnik dziesietny asterysk podstawa plus skladnik.
skladnik ← 0
liczba_dziesietny ← 0
kod ← 0
dla i = 1, 2, ..., n wykonuj:
kod ← ascii(liczba[i])
jeżeli kod >= ascii("A") i kod <= ascii("F"):
# konwertujemy znaki "A" - "F" na liczby 10 - 15
skladnik ← kod - ascii('A') + 10
w przeciwnym razie:
# konwertujemy znaki "0" - "9" na cyfry 0 - 9
skladnik ← kod - ascii('0')
liczba_dziesietny ← liczba_dziesietny * podstawa + skladnik
3. Na koniec zwracamy wynik przeprowadzonej konwersji.
Linia 1. skladnik ← 0.
Linia 2. liczba podkreślnik dziesietny ← 0.
Linia 3. kod ← 0.
Linia 5. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n wykonuj dwukropek.
Linia 6. kod ← ascii otwórz nawias okrągły liczba otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 8. jeżeli kod zamknij nawias ostrokątny znak równości ascii otwórz nawias okrągły cudzysłów A cudzysłów zamknij nawias okrągły i kod otwórz nawias ostrokątny znak równości ascii otwórz nawias okrągły cudzysłów F cudzysłów zamknij nawias okrągły dwukropek.
Linia 9. kratka konwertujemy znaki cudzysłów A cudzysłów minus cudzysłów F cudzysłów na liczby 10 minus 15.
Linia 10. skladnik ← kod minus ascii otwórz nawias okrągły apostrof A apostrof zamknij nawias okrągły plus 10.
Linia 11. w przeciwnym razie dwukropek.
Linia 12. kratka konwertujemy znaki cudzysłów 0 cudzysłów minus cudzysłów 9 cudzysłów na cyfry 0 minus 9.
Linia 13. skladnik ← kod minus ascii otwórz nawias okrągły apostrof 0 apostrof zamknij nawias okrągły.
Linia 15. liczba podkreślnik dziesietny ← liczba podkreślnik dziesietny asterysk podstawa plus skladnik.
Linia 17. zwróć liczba podkreślnik dziesietny.
skladnik ← 0
liczba_dziesietny ← 0
kod ← 0
dla i = 1, 2, ..., n wykonuj:
kod ← ascii(liczba[i])
jeżeli kod >= ascii("A") i kod <= ascii("F"):
# konwertujemy znaki "A" - "F" na liczby 10 - 15
skladnik ← kod - ascii('A') + 10
w przeciwnym razie:
# konwertujemy znaki "0" - "9" na cyfry 0 - 9
skladnik ← kod - ascii('0')
liczba_dziesietny ← liczba_dziesietny * podstawa + skladnik
zwróć liczba_dziesietny
Przedstawiony algorytm ma złożoność O(n), zatem zrealizowaliśmy również to założenie.
Słownik
konwersja między systemami liczbowymi
konwersja między systemami liczbowymi
zmiana sposobu prezentacji liczby, polegająca na przedstawieniu jej wartości w innym systemie liczbowym (systemie liczbowym o innej podstawie); przykładem konwersji jest przekształcenie liczby do postaci