Thuật toán chuyển đổi cơ số và hướng dẫn viết code bằng Pascal

Có thể bạn thích

Nếu đã học qua Tin học 10 thì chắc bạn sẽ biết đến định nghĩa cơ số và làm thế nào để chuyển đổi giữa các cơ số, khi chuyển đổi từ Binary (hệ nhị phân) sang Decimal (hệ thập phân) thì sẽ có một cách đổi riêng, khi chuyển từ cơ số Heximal (hệ thập lục phân) sang Octal (hệ bát phân) sẽ có một cách khác và đổi ngược lại từ Octal sang Heximal thì lại là một vấn đề... Giả sử trong thi cử, bạn không thể biết trước được giám khảo sẽ cho đề là chuyển đổi từ cơ số nào sang cơ số nào, vì có tới 210 cách để giám khảo cho, thế thì khả năng mà chúng ta học thuộc tất cả là không thể. Không còn cách nào khác, bạn phải hiểu được bản chất của các cơ số để ứng dụng cho tất cả. 

Mục đích hướng tới của bài viết này là nắm được bản chất và thiết kế được thuật toán.

Cơ sở lý thuyết - Chuyển đổi hệ thập phân sang hệ khác

Mình sẽ lấy một ví dụ về số 19 (10) (định nghĩa con số "n" trong "(n)" là hệ đếm, trong ví dụ 19 có hệ đếm là cơ số 10), mình sẽ làm một vài chuyển đổi sau:

• 19 (10) = 10011 (2)
• 19 (10) = 13 (16)
• 19 (10) = 23 (8)
• 19 (10) = 18 (11)
• ...

Nếu nhìn kĩ, các bạn sẽ nhận thấy tất cả các con số cuối cùng được tạo ra sau chuyển đổi chính là số dư sau khi thực hiện phép chia số 19 với cơ số mà nó đang muốn chuyển đổi tới.

(19 mod 2 = 1; 19 mod 16 = 3; 19 mod 8 = 3; 19 mod 11 = 8;...)

Giờ con số tiếp theo sẽ được tạo như thế nào? Rất đơn giản, sau khi đã thực hiện tìm số dư ở bên trên, bạn hãy lấy số đó chia lấy nguyên với cơ số, tiếp tục lấy số nguyên đó và thực hiện tìm số dư như bên trên, viết kết quả tìm được vào trước số hiện tại. Vậy thì cách chuyển đổi chỉ vỏn vẹn trong 2 bước cố định: chia lấy dư và chia lấy nguyên.

Lấy ví dụ ở trên: 19 (10) > ? (11) ?!

• B1, chia lấy dư (19 mod 11 = 8). 
• B2, chia lấy nguyên (19 div 11 = 1), xong lấy nguyên đó tiếp tục chia lấy dư (1 mod 11 = 1), viết vào trước số hiện tại. 

Vì bước tiếp theo (1 div 11 = 0), do đó ta dừng lại và hoàn thành, kết quả là 18 (11).

Tóm lại, kỹ thuật sẽ được gói gọn lại trong những dòng sau:

Giả sử có số A (10) và hệ cơ số n muốn chuyển, R sẽ là kết quả sau khi chuyển.

{Thực hiện vòng lặp} 
    R = (A mod n) & R; {Chia lấy dư rồi viết vào trước}
    A = A div n; {Chia lấy nguyên} 
{A = 0? kết thúc vòng lặp}

Ta rút ra được công thức: 

Trong một hệ đếm cơ số b (b > 1), một chuỗi các con số d₁ … d_n biểu diễn số d₁bⁿ⁻¹ + d₂bⁿ⁻² + … + d_nb⁰, với điều kiện 0 ≤ d_i < b.

(Trích dẫn từ Wikipedia)

Hãy cố gắng suy nghĩ tại sao lại có công thức này nhé!

Tiến gần hơn - chuyển đổi từ hệ cơ số A sang hệ cơ số B

Giờ nâng lên một chút, làm thế nào để chuyển từ hệ A bất kì sang hệ B bất kì? Áp dụng cơ sở lý thuyết bên trên để suy nghĩ một chút nào! Giờ là phương pháp, chỉ vỏn vẹn 1 dòng ngắn ngủi thôi!

Phương pháp: A > 10 > B

Áp dụng tính chất bắc cầu, ta sẽ sử dụng hệ thập phân làm hệ cơ số trung gian để chuyển đổi A và B. Sử dụng công thức bên trên để đổi từ A > 10, sử dụng cách còn lại để chuyển từ 10 > B.

Bây giờ bạn có thể áp dụng vào viết chương trình rồi, hãy thử làm trước khi tham khảo code bên dưới bạn nhé.

Code tham khảo

Mình sẽ mình họa thuật toán bằng ngôn ngữ Pascal.

program ConvertProgram; // by DuongTran (OwlTek) - owltek.blogspot.com
var A: string;
    X: integer;
    Y: integer;
function DecTo(A,n:integer):string;
var res,t: string;
begin
t := '0123456789ABCDEF';
Repeat
    res := t[(A mod n)+1] + res;
    A := A div n;
Until A = 0;
DecTo := res;
end;
function ToDec(A: string; n: integer):integer;
var res,i: integer;
begin
    res := 0;
    for i := Length(A) downto 1 do begin
    res := res + (Ord(A[i]) - 48)*Trunc(exp((Length(A)-i)*ln(n)));
end;
ToDec := res;
end;
procedure Convert(A:string;X,Y: integer);
var t: string;
      k: integer;
      F: text;
begin
k := ToDec(A,X);
t := DecTo(k,Y);
Writeln(t);
end;
BEGIN
A := '10011'; // {Nhập giá trị A}
X := 2; // {Nhập cơ số của giá trị A}
Y := 10; // {Nhập cơ số cần chuyển đổi}
Convert(A,X,Y); // Kết quả
END.

Một số lưu ý khi sử dụng code

• Nếu bạn muốn sử dụng code hoặc muốn chia sẻ code lại trên blog hay website của bạn, vui lòng để lại nguồn dẫn đến bài viết này.
• Trong quá trình biên dịch, mình nhận được kết quả... "hơi kì quặc", và mình phát hiện ra trình biên dịch Free Pascal có vấn đề nên mình đã biên dịch trên trang RexTester để kiểm tra và nhận được kết quả đúng, mình cũng khuyến khích biên dịch trên trang này.
• Đặc biệt giá trị A bên trên có kiểu dữ liệu là String, lí do là vì ở nhiều hệ đếm có độ dài của giá trị là rất dài, nếu như mặc định xem số đó là hệ thập phân thì rất lớn, điển hình là hệ nhị phân. Do đó nếu chọn kiểu Integer hay LongInt thì sẽ không đủ bộ nhớ.
• Code trên chỉ giới hạn đến hệ cơ số thập lục phân (16) và tất nhiên là không có hệ "nhất phân", do đó bạn cần nhập giá trị X, Y sao cho 1 < X, Y < 17 (X, Y phải là số nguyên).
• Code hiện tại chưa được chú thích, mình sẽ cố gắng chú thích trong thời gian sớm nhất.

Kết lại

Qua bài viết này, chúng ta đã nắm được bản chất của việc chuyển đổi cơ số và viết được thuật toán để chuyển đổi. Hi vọng bạn sẽ nắm rõ sau khi đọc bài viết này. Nếu có bất kì thắc mắc hoặc nghi vấn gì thì hãy comment bên dưới cho mình biết nhé, mình sẽ giúp đỡ nhiệt tình nhất có thể!

Have a nice day!