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:

wi = pi

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:

L = Cn-1×pn-1+Cn-2×pn-2+…+C2×p2+C1×p1+C0×p0

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: 2210121₃ (aby nie mylić liczb zapisanych w innych systemach pozycyjnych z liczbami dziesiętnymi, za liczbą w indeksie dolnym podajemy podstawę systemu, w którym zapisana została liczba):

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 532014₆:

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. Natomiast wynikiem dzielenia będzie liczba, która w docelowym systemie została pozbawiona ostatniej cyfry i reszta jej cyfr przesunięta o jedną pozycję w prawo. Dla przykładu weźmy kilka liczb w różnych systemach pozycyjnych:

1012 = 5
5/2 = 2 = 102 i reszta 1

3156 = 119
119/6 = 19 = 316 i reszta 5

7289 = 593
593/9 = 65 = 729 i reszta 8

Dlaczego tak się dzieje? Odpowiedź jest bardzo prosta. Jeśli przyjrzymy się wzorowi na wartość liczby pozycyjnej L, to dojdziemy do wniosku, że:

L   = Cn-1×pn-1+Cn-2×pn-2+…+C2×p2+C1×p+C0
L/p = (Cn-1×pn-1+Cn-2×pn-2+…+C2×p2+C1×p+C0)/p
L/p = (Cn-1×pn-1)/p+(Cn-2×pn-2)/p+…+(C2×p2)/p+(C1×p)/p+C0/p
L/p = Cn-1×pn-2+Cn-2×pn-3+…+C2×p1+C1+C0/p

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 C₀ przez p. Ponieważ każda cyfra jest mniejsza od p, to reszta będzie równa C₀, czyli ostatniej cyfrze.

Podsumujmy:

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.

Algorytm przeliczania liczb na zapis w innym systemie pozycyjnym

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, ; wyznaczamy pozostałe cyfry
       to idź do kroku K02
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

Przykładowe programy

// 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; // przeliczana liczba
  p    : word; // podstawa systemu docelowego
  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 ją na stosie
    inc(sptr);
    L := L div p; // obliczamy nową wartość L
  until L = 0;

  while sptr > 0 do
  begin
    dec(sptr); // przesyłamy zawartość stosu
    write(S[sptr]); //na wyjście
  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 ją 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;
}

' 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ę
  sptr += 1 '  i umieszczamy na stosie
  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

# Przeliczanie na system o podstawie p
# Data: 11.06.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------------

# rozmiar stosu
S_MAX = 100
# stos cyfr
s = [0]*S_MAX
# indeks szczytu stosu
sptr = 0
# odczytujemy liczbę i podstawę
a = input().split()
n = int(a[0])
p = int(a[1])
while True:
    # obliczamy cyfrę
    # i umieszczamy na stosie
    s[sptr] = n % p
    sptr += 1
    # obliczamy nową wartość n
    n = n//p 
    if not n: break
# przesyłamy zawartość
# stosu na wyjście
while sptr:
    sptr -= 1
    print(s[sptr], end="")
print()
s = None

15 3

120