Misja matura 2
Zadanie 2
Zaimplementuj w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który dokona konwersjikonwersji 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 liczbyliczba– ciąg znaków reprezentujący liczbę naturalną zapisaną w systemie liczbowym o podstawiepodstawapodstawa– 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ść liczbyliczbaw systemie dziesiętnym; liczba naturalna
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. Nasze rozwiązanie zakłada, ż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.
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().
3. Na koniec zwracamy wynik przeprowadzonej konwersji.
Przedstawiony algorytm ma złożoność O(n), zatem zrealizowaliśmy również to założenie.
Słownik
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