Bài toán chuyển đổi cơ số
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (109.15 KB, 10 trang )
Chuyển đổi cơ số
Đoàn Phương Nam
Chúng ta đã có dịp làm quenvới xử lý số lớn ở các tập báo trước. Trong bài báo này tôi xin
được trao đổithêm với bạn đọc chủ đề trên thông qua bài toán chuyển đổi một số từ cơ số
nàysang cơ số khác. Đây là một bài toán khá quan trọng và đầy lý thú. Đối với conngười
thì cơ số thập phân (cơ số 10) là rất quen thuộc, chúng ta thường thaotác, tính toán trên hệ
cơ số 10. Nhưng đối với máy tính thì khác, cơ số 10không phải là?sở trường? mà lại làcơ
số nhị phân (tức cơ số 2). Chính vì vậy bất kì ai học Tin học đều phải hiểucơ số, biết cách
chuyển một số từ cơ số này sang cơ số khác.
Giới thiệu qua về cơ số
Trong hệ thống thập phân mộtsố có thể được phân tích bằng tổng của luỹ thừa 10. Như
vậy: 2808
10
= 2*10
3
+ 8*10
2
+ 0*10
1
+ 8*10
0
Cũng vậy, trong hệ cơ số kmột số M ở hệ cơ số k có thể phân tích bằng tổng luỹ thừa k. Ví
dụ với k = 28thì 289
28
= 2*28
2
+ 8*28
1
+ 9*28
0
Bài toán chuyển đổi cơ số S sang cơ số D
Cho một xâu W là biểu diễncủa một số ở cơ số S. Hãy tìm biểu diễn của số đó ở cơ số D
(S, D <= 35).Nếu trong trường hợp cơ số lớn hơn 10 thì ký tự?A? tương ứng với số 10, ký
tự?B?tương ứng với số 11,..., ký tự?Y?tương ứng với số 35.
Dữ liệu vàotrong file coso.inp códạng:
+ Dòng thứ nhất gồm hai số Svà D;
+ Dòng thứ hai là một xâu W(độ dài của xâu <101).
Kết quả rafile coso.out gồm một dòng duy nhấtlà một xâu ký tự, biểu diễn của số đó ở cơ
số D.
Coso.out
35 10
XYXYXYXYXY
Coso.inp
2679667322982089
Thuật toán:
Để chuyển một số từ cơ số Ssang hệ cơ số D trước tiên ta đổi số đó sang hệ cơ số thập
phân (cơ số 10). Sauđó đổi tiếp số vừa đổi sang cơ số D.
- Để chuyển một số sang cơ sốthập phân, ta áp dụng trực tiếp cách phân tích đã giới thiệu ở
trên. W= w
1
w
2
..w
N
= w
1
*S
N-1
+ w
2
*S
N-2
+..+ w
N
*S
0
= (..((w
1
*S+w
2
)*S+w
3
)..)*S+w
N
. Tatính
theo độ ưu tiên trong ngoặc (vì tính như thế sẽ mất ít phép tính toánnhất). Vì W có thể rất
lớn, như vậy từng giá trị trong ngoặc cũng có thể rấtlớn, ta không thể dùng các kiểu số có
sẵn để lưu trữ mà phải dùng xâu để lưu.Để tính giá trị biểu thức trên ta phải thao tác hai
loại phép toán đó là : nhânmột số lớn với S (S<=35) và cộng một số lớn với một số <=35.
- Để chuyển một số từ cơ sốthập phân sang cơ số D, ta chia số đó cho D phần dư sẽ là ký
tự cuối cùng củabiểu diễn đó. Sau đó ta lại lấy thương của phép chia vừa rồi chia tiếp cho
D,phần dư nhận được sẽ là ký tự đứng sát trước của ký tự cuối cùng. Cứ làm nhưvậy cho
đến khi thương bằng không. Như vậy để chuyển một số từ cơ số thập phânsang cơ số D ta
phải có thao tác phép toán là: chia một số lớn cho số D(D<=35) và lấy dư.
Trong bài viết 'Lập trình với các số Khổng lồ? củatác giả Lê Mạnh Dũng ở số 8 năm 2001,
tác giả đã đề cập tới việc tính toán vớicác số lớn. Song nếu áp dụng thuật toán đó để giải
bài này thì e rằng làm phứctạp bài toán và mất nhiều thời gian cài đặt cũng như thời gian
chạy. Vì thuậttoán mà tác giả Lê Mạnh Dũng đã đề cập là thuật toán xử lý hai số lớn còn
cácphép toán cần trong chương trình này là xử lý một số lớn với một số nhỏ.
Thuật toán cộng một số lớn với một số nhỏ
function cong(x:string;num:longint): string;
var nho,tong,k :longint;
kq :string;
begin
kq:=x; nho:=num;{đặt số cần cộng vào nho}
for k:=length(x) downto 1 do
begin
tong:=ord(x[k])-48+nho;
nho:=tong div 10;
kq[k]:=char(tong mod 10+48);
if nho=0 then break;
end;
while nho>0 do
begin
kq:=char(nho mod 10+48)+kq;
nho:=nho div 10;
end;
cong:=kq;
end;
Thuật toán cộng trên đây chophép cộng một số lớn chứa trong kiểu string cộng với một số
lớn kiểu longint.Thuật toán này dễ cài đặt, dễ hiểu và hiệu suất cao. Có một chú ý duy nhất
lànho (nhớ) có thể lớn hơn 10.
Thuật toán nhân một số lớn với một số nhỏ
functionnhan(x:string;num:longint):string;
var kq :string;
k,nho,tich :longint;
begin
nho:=0;kq:='';
for k:=length(x) downto 1 do
begin
tich:=num*(ord(x[k])-48)+nho;
nho:=tich div 10;
kq:=char(tich mod 10+48)+kq;
end;
while nho>0 do
begin
kq:=char(nho mod 10+48)+kq;
nho:=nho div 10;
end;
nhan:=kq;
end;
Thuậttoán nhân trình bày ở trên?y trang?thuật toán nhân với số có một chữ số. Ta không
cần quan tâm nó có bao nhiêu chữsố cứ coi nó chỉ là số có một chữ số. Song cũng giống
như thuật toán cộng nhớcó thể lớn. Không đơn thuần nhớ chỉ là số có một chữ số. Chính
điều này làm takhó nhận ra thuật toán trên.
Thuật toán chia một số lớn cho một số nhỏ
functionchiăx:string;num:longint;var du:integer):string;
var nho,k :longint;
kq:string;
begin
nho:=0; kq:='';
for k:=1 to length(x) do
begin
nho:=nho*10+ord(x[k])-48;
kq:=kq+char(nho div num+48);
nho:=nho mod num;
end;
du:=nho;
while (length(kq)>0)and(kq[1]='0') do delete(kq,1,1);
chia:=kq;
end;
Thuậttoán chia một số lớn cho một số nhỏ ở trên thao tác từ trái qua phải, mỗi lầnhạ một
phần tử xuống, gộp vào biến nhớ, thực hiện phép chia trực tiếp được (vìsố chia là một số
nhỏ). Nếu là phép chia hai số lớn thì việc này không thể thựchiện được vì số chia cũng là
số lớn. Do đó nếu muốn thực hiện phép chia hai sốlớn ta phải thử phần thương từ 0 đến 9.
Nhưvậy ta đã có các công cụ quan trọng để giải bài toán cơ số. Sau đây là chươngtrình cụ
thể.
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
uses crt;
const
max_cs = 35;
max = 40;
digit: string='0123456789ABCDEFGHIJKLMNOPQRSTUVWXY';
fi = 'coso.inp';
fo = 'coso.out';
var N_S,N_10 : string;
S,D : integer;
procedure docf;
var f :text;
begin
assign(f,fi);
reset(f);
readln(f,S,D);
