Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI W KONSERWACJI |
|
Tematy pomocnicze |
ProblemNależy przeliczyć liczbę dziesiętną na liczbę pozycyjną przy podstawie p, 1 < p < 11 |
Systemy pozycyjne służą do zapisu dowolnych liczb za pomocą skończonej liczby znaków, zwanych cyframi. Cyfry są umieszczane na kolejnych pozycjach w zapisie liczby. Pozycje te numerujemy od strony prawej do lewej (dla części całkowitej):
cyfra: | C | C | C | … | C | C | C | |
numer pozycji: | n-1 | n-2 | n-3 | … | 2 | 1 | 0 |
W powyższym zapisie cyfry oznaczyliśmy symbolicznie literą C. Cyfra zielona C znajduje się w zapisie liczby na pozycji o numerze 1, a cyfra czerwona C na pozycji o numerze n – 2. Cały zapis składa się z n cyfr. Pozycje posiadają tzw. wagi, które określają wartości cyfr umieszczonych na tych pozycjach. Wagi pozycji obliczamy wg ich numeru. Do tego celu potrzebujemy bardzo ważnej wartości, która nosi nazwę podstawy systemu. Będziemy ją oznaczali małą literą p. Gdy znamy podstawę p i numer pozycji i-tej, to wagę pozycji obliczamy zawsze wg wzoru:
gdzie: w jest wagą, i numerem pozycji, p podstawą systemu. |
Mając te informacje, możemy w prosty sposób wyliczyć wagi wszystkich pozycji w zapisie liczby:
waga pozycji: | pn-1 | pn-2 | pn-3 | … | p2 | p1 | p0 | |
cyfra: | C | C | C | … | C | C | C | |
numer pozycji: | n-1 | n-2 | n-3 | … | 2 | 1 | 0 |
Teraz wartość tak zapisanej liczby obliczamy jako sumę iloczynów cyfr przez wagi ich pozycji. Na przykład, dla powyższego zapisu będzie to:
gdzie: L – wartość liczby, Ci – cyfra na i-tej pozycji, p – podstawa |
Cyfr jest zawsze tyle, ile wynosi podstawa systemu. Najmniejszą cyfrą jest 0. Największa cyfra ma wartość p – 1. W zapisie liczby cyfry określają, ile razy waga danej pozycji jest użyta w wartości liczby. Dla przykładu policzmy wartość liczby trójkowej: 22101213 (aby nie mylić liczb zapisanych w innych systemach pozycyjnych z liczbami dziesiętnymi, za liczbą w indeksie dolnym podajemy podstawę):
22101213 = 2·36
+ 2·35 + 1·34 +
0·33
+ 1·32 +
2·31 + 1·30 22101213 = 2·729 + 2·243 + 1·81 + 0·27 + 1·9 + 2·3 + 1·1 22101213 = 1458 + 486 + 81 + 0 + 9 + 6 + 1 22101213 = 2041 |
A teraz liczba szóstkowa 5320146:
5320146 = 5·65
+ 3·64 +
2·63 + 0·62
+ 1·61 +
4·60 5320146 = 5·7776 + 3·1296 + 2·216 + 0·36 + 1·6 + 4·1 5320146 = 38880 + 3888 + 432 + 0 + 6 + 4 5320146 = 43210 |
Nasz problem polega na przeliczeniu liczby zapisanej dziesiętnie na tę sama liczbę zapisaną w systemie o podstawie p. Wykorzystujemy tutaj prostą własność dzielenia z resztą. Otóż, jeśli podzielimy liczbę przez podstawę p, to resztą z dzielenia będzie wartość ostatniej cyfry zapisu. Dla przykładu weźmy kilka liczb w różnych systemach pozycyjnych:
101
2
= 5 5 / 2 = 2 i reszta 1 |
315
6
= 119 119 / 6 = 19 i reszta 5 |
728
9
= 593 593 / 9 = 65 i reszta 8 |
Dlaczego tak się dzieje? Odpowiedź jest bardzo prosta. Jeśli przyjrzymy się wzorowi na wartość liczby pozycyjnej, to dojdziemy do wniosku, że:
Jako wynik dzielenia całkowitego otrzymujemy wartość, która w docelowym zapisie pozycyjnym nie posiada ostatniej cyfry liczby wyjściowej – zobacz na wartości wag, które stoją przy kolejnych cyfrach – innymi słowy cyfry w wyniku dzielenia są cyframi wyjściowej liczby przesuniętymi o jedną pozycję w prawo bez ostatniej cyfry. Ostatni człon jest ułamkiem, zatem będzie resztą z dzielenia C0 przez p. Ponieważ każda cyfra jest mniejsza od p, to reszta będzie równa C0, czyli ostatniej cyfrze.
101
2
= 5 102 = 2 → 5 / 2 = 2 i reszta 1 |
3156
= 119 316 = 19 → 119 / 6 = 19 i reszta 5 |
7289
= 593 729 = 65 → 593 / 9 = 65 i reszta 8 |
Liczbę dzielimy przez podstawę p.
Reszta z dzielenia jest równa wartości ostatniej cyfry liczby
zapisanej w systemie o podstawie p.
Część całkowita z dzielenia jest równa wartości, która w systemie o podstawie
p posiada wszystkie cyfry liczby z wyjątkiem ostatniej.
Zatem, aby otrzymać wszystkie cyfry liczby w zapisie o podstawie p dzielimy liczbę cyklicznie przez p, aż otrzymamy wynik zero. Kolejne reszty dadzą nam kolejne od końca cyfry.
Dla przykładu znajdziemy zapis liczby 99999 w systemie o podstawie p = 5:
99999 / 5 = | 19999 | i reszta 4 |
19999 / 5 = | 3999 | i reszta 4 |
3999 / 5 = | 799 | i reszta 4 |
799 / 5 = | 159 | i reszta 4 |
159 / 5 = | 31 | i reszta 4 |
31 / 5 = | 6 | i reszta 1 |
6 / 5 = | 1 | i reszta 1 |
1 / 5 = | 0 | i reszta 1 |
Zatem:
99999 = 111444445 |
Zwróć uwagę, że cyfry w tym algorytmie otrzymujemy w odwrotnej kolejności – od końca. W tym miejscu wykorzystujemy własności stosu – dane wprowadzone na stos są odczytywane w kolejności odwrotnej do ich wprowadzenia. Zatem wyznaczamy kolejne cyfry, umieszczamy je na stosie, a gdy wartość liczby osiągnie 0, to przenosimy wszystkie cyfry ze stosu na wyjście – otrzymamy poprawny zapis liczby w systemie o podstawie p.
L | : | wartość liczby, L ∈ N. |
p | : | podstawa systemu docelowego, p ∈ N, 1 < p < 11 |
Kolejne cyfry zapisu liczby w systemie o podstawie p
S | : | stos cyfr |
K01: | Utwórz pusty stos S | |
K02: | S.push (L mod p) | obliczamy wartość ostatniej cyfry i umieszczamy ją na stosie |
K03: | L ← L div p | obliczamy nową wartość L |
K04: | Jeśli L > 0, to idź do kroku K02 |
wyznaczamy pozostałe cyfry |
K05: | Dopóki S.empty() = false, wykonuj kroki K06…K07 |
|
K06: | Pisz S.top() | wypisujemy cyfrę ze stosu |
K07: | S.pop() | cyfrę usuwamy ze stosu |
K08: | Zakończ |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program wczytuje kolejno liczbę L oraz podstawę p i wyznacza zapis L w systemie o podstawie p. Program nie sprawdza poprawności danych. |
Pascal// Przeliczanie na system o podstawie p // Data: 21.08.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------ program p_base; const S_MAX = 100; // rozmiar stosu var L : qword; // liczba p : word; // podstawa S : array [0..S_MAX-1] of word; // stos cyfr sptr : integer; // indeks szczytu stosu begin sptr := 0; // inicjujemy stos readln(L, p); // odczytujemy liczbę i podstawę repeat S [sptr] := L mod p; // obliczamy cyfrę i umieszczamy na stosie inc (sptr); L := L div p; // obliczamy nową wartość L until L = 0; while sptr > 0 do // przesyłamy zawartość stosu na wyjście begin dec (sptr); write (S [sptr]); end; writeln; end. |
// Przeliczanie na system o podstawie p // Data: 21.08.2012 // (C)2020 mgr Jerzy Wałaszek //------------------------------ #include <iostream> using namespace std; const int S_MAX = 100; // rozmiar stosu int main() { unsigned long long L; // liczba unsigned short p; // podstawa unsigned short S [S_MAX]; // stos cyfr int sptr = 0; // indeks szczytu stosu cin >> L >> p; // odczytujemy liczbę i podstawę do { S [sptr++] = L % p; // obliczamy cyfrę i umieszczamy na stosie L = L / p; // obliczamy nową wartość L } while(L); while(sptr) cout << S [--sptr]; // przesyłamy zawartość stosu na wyjście cout << endl; return 0; } |
Basic' Przeliczanie na system o podstawie p ' Data: 21.08.2012 ' (C)2020 mgr Jerzy Wałaszek '------------------------------ Const S_MAX = 100 ' rozmiar stosu Dim L As ULongInt ' liczba Dim p As UByte ' podstawa Dim S (S_MAX-1) As UByte ' stos cyfr Dim sptr As Integer ' indeks szczytu stosu Open Cons For Input As #1 sptr = 0 ' inicjujemy stos Input #1, L, p ' odczytujemy liczbę i podstawę Close #1 Do S (sptr) = L mod p ' obliczamy cyfrę i umieszczamy na stosie sptr += 1 L = L \ p ' obliczamy nową wartość L Loop Until L = 0 While sptr > 0 ' przesyłamy zawartość stosu na wyjście sptr -= 1 Print Using "#";S (sptr); Wend Print End |
Wynik: |
15 3 120 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.