JustPaste.it

Przeliczenia na inny zapis pozycyjny

4a5b07583fcf0f9259849b16a69ecb54.gif

W poprzednich dwóch rozdziałach nauczyliśmy was obliczać wartość liczby zapisanej w dowolnym systemie pozycyjnym. Teraz zajmiemy się zadaniem odwrotnym - jak przedstawić daną liczbę w systemie pozycyjnym o podstawie p.

Problem sprowadza się do znalezienia kolejnych cyfr zapisu liczby w systemie docelowym. Wartość liczby L jest równa zgodnie ze wzorem:

L = Cn-1 pn-1 + Cn-2 pn-2 + ... + C2 p2 + C1 p + C0

Do wydobycia poszczególnych cyfr Ci , i = 0,1,2,...,n-1, są nam potrzebne dwa działania:

  • div - dzielenie całkowitoliczbowe - określa ile całkowitą ilość razy dzielnik mieści się w dzielnej, na przykład:
    9 div 4 = 2, gdyż 4 mieści się w 9 2 razy.
  • mod - reszta z dzielenia całkowitoliczbowego, na przykład:
    9 mod 4 = 1, gdyż 4 mieści się w 9 dwa razy, co daje 8 i pozostaje reszta 1.
    Reszta z dzielenia jest zawsze mniejsza od dzielnika (dlaczego?).

Oba działania występują powszechnie we wszystkich językach programowania. Wyjątkiem jest JavaScript, który posiada swobodne typy danych, zatem brak w nim dzielenia całkowitoliczbowego, ale można sobie z tym w prosty sposób poradzić.

Realizacja operacji div i mod
Pascal div
mod
a div b
a mod b
C++ div
mod
a / b
a % b
Basic div
mod
a \ b
a MOD b
Python div
mod
a // b
a % b
JavaScript div
mod
Math.floor(a / b)
a % b

Jeśli podzielimy L przez p, otrzymamy:

849839c5ca6993e510656d0aaab8e824.gif

Ostatnia cyfra C0 nie dzieli się przez p (każda cyfra jest  mniejsza od podstawy systemu), zatem będzie resztą z dzielenia całkowitoliczbowego L przez p. Pozostała część wyrażenia jest jak widać podzielna przez p. Zauważ, iż w wyniku dostajemy liczbę z mniejszą ilością cyfr. W porównaniu z poprzednią liczbą wszystkie cyfry są przesunięte o 1 pozycję w prawo - teraz najmłodszą cyfrą jest C1. Operację powyższą powtarzamy aż do znalezienia wszystkich cyfr zapisu liczby.

2d3769e54fd03ed353549980e60c4e06.gif

 

Przedstawić w systemie piątkowym liczbę 139(10).

L = 139
p = 5

C0 = L mod p = 139 mod 5 = 4
L = L div p = 139 div 5 = 27

C1 = L mod p = 27 mod 5 = 2
L = L div p = 27 div 5 = 5

C2 = L mod p = 5 mod 5 = 0
L = L div p = 5 div 5 = 1

C3 = L mod p = 1 mod 5 = 1
L = L div p = 1 div 5 = 0
- kończymy, ponieważ wynik dzielenia daje wartość 0.

139(10) = 1024(5).

Praktycznie działania te wykonujemy w słupku dzieląc całkowitoliczbowo liczbę przez podstawę systemu i wypisując reszty z dzielenia. Gdy rachunki zakończymy, otrzymane reszty odczytujemy w kierunku z dołu do góry otrzymując kolejne cyfry zapisu liczby.

522785311ef56952e47b43942bdfa5e3.gif

 

Przedstawić w systemie czwórkowym liczbę 2743(10).

2743 div 4 =  685  i reszta 3
685 div 4 =  171  i reszta 1
171 div 4 =  42  i reszta 3
42 div 4 = 10  i reszta 2
10 div 4 = 2  i reszta 2
2 div 4 = 0  i reszta 2 - koniec, ponieważ wynik dzielenia wynosi 0

2743(10) = 222313(4).

 

Przedstawić w systemie dziewiątkowym liczbę 35921(10).

35921 div 9 =  3991  i reszta 2
3991 div 9 = 443  i reszta 4
443 div 9 = 49  i reszta 2
49 div 9 = 5  i reszta 4
5 div 9 = 0  i reszta 5 - koniec

35921(10) = 54242(9).

 

Przedstawić w systemie trójkowym liczbę 325748(10).

325748 div 3 =  108582  i reszta 2
108582 div 3 = 36194  i reszta 0
36194 div 3 = 12064  i reszta 2
12064 div 3 = 4021  i reszta 1
4021 div 3 = 1340  i reszta 1
1340 div 3 = 446  i reszta 2
446 div 3 = 148  i reszta 2
148 div 3 = 49  i reszta 1
49 div 3 = 16  i reszta 1
16 div 3 = 5  i reszta 1
5 div 3 = 1  i reszta 2
1 div 3 = 0  i reszta 1 - koniec

325748(10) = 121112211202(3).

62a6759aaae254a2599cbea1497e651e.gif

Podsumujmy podane dotychczas informacje w formie algorytmu.

85931f6972510ed119107abc2bf2505c.gif

Dane wejściowe

L - przeliczana liczba, L dec279eb9127279c4c1a873466bf8680.gif N + {0}
p - podstawa docelowego systemu pozycyjnego, p dec279eb9127279c4c1a873466bf8680.gif N,  p dec279eb9127279c4c1a873466bf8680.gif {2,3,...,10}

Dane wyjściowe

Ciąg znaków s reprezentujący zapis liczby L w systemie pozycyjnym o podstawie p.

Zmienne pomocnicze i funkcje

s - przechowuje docelowy zapis liczby.
c - przechowuje wartość cyfry, c dec279eb9127279c4c1a873466bf8680.gif N + {0}
kod(znak) - funkcja zwraca kod ASCII znaku
znak(kod) - zwraca znak ASCII o podanym kodzie

080cf4066344ac93b77636c8efd6c16e.gif

krok 1: Czytaj L i p
krok 2: s 9c321fc56eb300cce36189726f8be622.gif ""
krok 3: c 9c321fc56eb300cce36189726f8be622.gif L mod p
krok 4: s 9c321fc56eb300cce36189726f8be622.gif znak(c + kod('0')) + s
krok 5: L 9c321fc56eb300cce36189726f8be622.gif L div p
krok 6: Jeśli L = 0, to pisz s i zakończ algorytm. Inaczej idź do kroku 3.

1aaf285a62f3d30874b75652a2978b5d.gif

 

Odczytujemy liczbę L, którą chcemy przeliczyć oraz podstawę p docelowego systemu pozycyjnego. Podany algorytm pracuje poprawnie tylko dla podstaw p od 2 do 10 (dlaczego?).

Wyliczone cyfry będziemy odkładać w zmiennej łańcuchowej s. Inicjujemy ją pustym tekstem.

Rozpoczynamy pętlę warunkową, która będzie wykonywana, aż liczba L osiągnie wartość 0. Wewnątrz pętli obliczamy wartość ostatniej cyfry liczby L i umieszczamy wynik w zmiennej c. Aby wstawić cyfrę do zmiennej łańcuchowej s musimy ją wyrazić za pomocą kodu ASCII. Dlatego w wyrażeniu wyliczamy kod znaku cyfry jako sumę wartości cyfry oraz kodu cyfry 0. Na przykład dla cyfry 5 otrzymamy kod 5 + 48 = 53 (cyfra 0 ma w ASCII kod 48). Znak o kodzie 53 to właśnie cyfra 5. Obliczony kod cyfry przekształcamy w znak i łączymy z zawartością łańcucha s. Bardzo ważna jest tutaj kolejność łączenia. Cyfra musi być dopisana przed poprzednio wyliczonymi cyframi, ponieważ algorytm wyznacza cyfry od końca zapisu liczby. Po dołączeniu cyfry do łańcucha liczbę L dzielimy całkowitoliczbowo przez p i przechodzimy do sprawdzenia warunku zakończenia pętli. Jeśli po operacji dzielenia liczba L nie jest równa zero, to nie zostały jeszcze wyznaczone wszystkie cyfry, zatem pętla kontynuuje się. Jeśli natomiast liczba L jest równa zero, zmienna s zawiera komplet cyfr liczby w docelowym systemie pozycyjnym. Wychodzimy z pętli, wypisujemy zawartość łańcucha s i kończymy algorytm.


b89cd85a6a9e025492d2929fe6ab85d1.gif

0e3348a34d7b66d40ae912202969351d.gif    
   
   

a281595a3d2099a88f7817bbe86bcec5.gif

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Na podstawie algorytmu tworzymy programy wyznaczające zapis podanej liczby dziesiętnej w systemie pozycyjnym o podstawie od 2 do 10. Zwróć uwagę, iż algorytm nie sprawdza poprawności danych wprowadzonych przez użytkownika. Jeśli użytkownik poda podstawę systemu docelowego równą 1, to pętla warunkowa nigdy nie zakończy się dla L > 0 (dlaczego?). Zastanów się nad sposobami usunięcia tych wad.

Wydruk z uruchomionego programu
Przeliczanie podanej liczby na zapis
w systemie pozycyjnym o podstawie p
------------------------------------
(C)2005 mgr J. Walaszek I LO Tarnów

Podaj liczbę = 25

Podaj p (2..10) = 4

25(10) = 121(4)

KONIEC. Naciśnij dowolny klawisz...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
// Znajdowanie reprezentacji liczby
// w systemie pozycyjnym o podstawie
// p równej od 2 do 10
//----------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//----------------------------------

program przelicz;

{$APPTYPE CONSOLE}

var
s : string;
c,L,p : cardinal;

begin
writeln('Przeliczanie podanej liczby na zapis');
writeln('w systemie pozycyjnym o podstawie p');
writeln('------------------------------------');
writeln('(C)2005 mgr J. Walaszek I LO Tarnow');
writeln;
write('Podaj liczbe = '); readln(L);
writeln;
write('Podaj p (2..10) = '); readln(p);
writeln;
write(L,'(10) = ');
s := '';
repeat
c := L mod p;
s := char(c + ord('0')) + s;
L := L div p;
until L = 0;
writeln(s,'(',p,')');
writeln;
writeln('Nacisnij klawisz ENTER...');
readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Znajdowanie reprezentacji liczby
// w systemie pozycyjnym o podstawie
// p równej od 2 do 10
//----------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//----------------------------------

#include <iostream>
#include <string>

using namespace std;

main()
{
string s;
unsigned c,L,p;
char z[1];

cout << "Przeliczanie podanej liczby na zapis\n"
"w systemie pozycyjnym o podstawie p\n"
"------------------------------------\n"
"(C)2005 mgr J. Walaszek I LO Tarnow\n\n"
"Podaj liczbe = "
;
cin >> L;
cout << "\nPodaj p (2..10) = ";
cin >> p;
cout << "\n" << L << "(10) = ";
s = "";
do
{
c = L % p;
s = char(c + 48) + s;
L = L / p;
} while(L != 0);
cout << s << "(" << p
<< ")\n\nNacisnij ENTER...\n";
cin.getline(z,1);
cin.getline(z,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Znajdowanie reprezentacji liczby
' w systemie pozycyjnym o podstawie
' p równej od 2 do 10
'----------------------------------
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'----------------------------------


Option Explicit On

Module
Module1

Sub Main()

Dim s As String
Dim
c, L, p As UInteger

Console.WriteLine("Przeliczanie podanej liczby na zapis")
Console.WriteLine("w systemie pozycyjnym o podstawie p")
Console.WriteLine("------------------------------------")
Console.WriteLine("(C)2005 mgr J. Walaszek I LO Tarnów")
Console.WriteLine()
Console.Write("Podaj liczbę = ") : L = Val(Console.ReadLine)
Console.WriteLine()
Console.Write("Podaj p (2..10) = ") : p = Val(Console.ReadLine)
Console.WriteLine()
Console.Write("{0}(10) = ", L)
s = ""
Do
c = L Mod p
s = Chr(c + Asc("0")) + s
L = L \ p
Loop Until L = 0
Console.WriteLine("{0}({1})", s, p)
Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Znajdowanie reprezentacji liczby
# w systemie pozycyjnym o podstawie
# p równej od 2 do 10
#----------------------------------
# (C)2005 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#----------------------------------

print "Przeliczanie podanej liczby na zapis"
print "w systemie pozycyjnym o podstawie p"
print "------------------------------------"
print "(C)2005 mgr J. Walaszek I LO Tarnow"
print
L = int(raw_input("Podaj liczbe = "))
print
p = int(raw_input("Podaj p (2..10) = "))
print
print
"%d(10) =" % L,
s = ""
while L:
s = chr(L % p + 48) + s
L //= p
if s == "": s = "0"
print "%s(%d)" % (s, p)
print
raw_input
("Nacisnij klawisz ENTER...")
JavaScript
<html>
<head>
</head>
<body>
<div align=
"center">
<form style=
"BORDER-RIGHT: #ff9933 1px outset;
PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset;
PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px;
BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px;
BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"

name="frmprzelicz">
<h3 id=
"data_out" style="text-align: center">
Wyznaczanie zapisu liczby L<br>
w systemie pozycyjnym o podstawie p</h3>
<p style="TEXT-ALIGN: center">
(C)2005 mgr Jerzy Wałaszek&nbsp;&nbsp; I LO w Tarnowie
</p>
<hr>
<div align=
"center">
<table border=
"0" cellpadding="4" style="border-collapse: collapse">
<tr>
<td align=
"right">Liczba =</td>
<td>
<input value=
"23314" name="inp_l" size="20" style="text-align: right">
</td>
</tr>
<tr>
<td align=
"right">Podstawa (2...10) =</td>
<td>
<input value=
"5" name="inp_p" size="20" style="text-align: right">
</td>
</tr>
</table>
</div>
<p style=
"TEXT-ALIGN: center">
<input onclick=
"main();" type="button" value="Przelicz" name="B1">
</p>
<p id=
"out_t" style="TEXT-ALIGN: center">...</p>
</form>

<script language=javascript>


// Znajdowanie reprezentacji liczby
// w systemie pozycyjnym o podstawie
// p równej od 2 do 10
//----------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//----------------------------------

function main()
{
var s,t,p,L,c;

p = parseInt(document.frmprzelicz.inp_p.value);
L = parseInt(document.frmprzelicz.inp_l.value);
s = "<font color=Red><b>Złe dane</b></font>";
if(!isNaN(p) && !isNaN(L))
{
s = ""; t = L + "<sub>(10)</sub> = ";
do
{
c = L % p;
s = String.fromCharCode(c + 48) + s;
L = Math.floor(L / p);
} while(L != 0);
s = t + s + "<sub>(" + p + ")</sub>";
};
document.getElementById("out_t").innerHTML = s;
}
</script>
</div>
</body>
</html>
 

58f33662c4401ccf4e772131b99abefe.gif

Wyznaczmy złożoność obliczeniową zaprezentowanego algorytmu przy znajdowaniu reprezentacji liczby L w systemie pozycyjnym o podstawie p.. Za operację dominującą przyjmijmy 1 obieg pętli warunkowej. Każdy obieg zmniejsza wartość liczby L p razy. Obiegi wykonywane są do momentu, aż L osiągnie wartość 0. Zatem ich ilość wyraża się wzorem:

245858d00de2860ada6b177c6b3d9423.gif

Ze wzoru wynika, iż algorytm jest klasy O(logp n), gdzie n oznacza wartość liczby, której reprezentację wyznaczamy w systemie pozycyjnym o podstawie p.

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.


 

Źródło: mgr Jerzy Wałaszek