Bài toán chuyển đổi cơ số

Chuyển đổi cơ số
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*102 + 0*101 + 8*100
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ì 28928 = 2*282 + 8*281 + 9*280
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= w1w2..wN= w1*SN-1 + w2*SN-2 +..+ wN*S0= (..((w1*S+w2)*S+w3)..)*S+wN. 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