Sử dụng otomat cài đặt các phép toán cơ sở

Bài toán: Cho 2 số a, b ở cơ số n bất kỳ, hãy cài đặt các phép toán +, -, *, /
Trong đó: a, b được biểu diễn tương tự như hệ đếm cơ số 10 quen thuộc của chúng ta, tức là:

a = a(k)a(k - 1)… a(i) … a(2)a(1) ; với a(i) thuộc [0, n – 1]

A. Biểu diễn nhị phân (hệ đếm cơ số 2) cài đặt phép toán: +, -
Cách 1: Phương pháp thuần túy, sử dụng các lệnh IF THEN ELSE
Giải thuật:

Nhận xét: Với phương pháp thuần túy này áp dụng cho hệ đếm cơ số lớn, cơ số 256 chẳng hạn thì độ phức tạp về thời gian là rất lớn. Và ở trên các phép toán cơ sở là gán và so sánh.



Cách 2: Sử dụng Otomat có Ra cài đặt phép toán cộng

Ta đi tổ chức 2 mảng nhớ (3 chiều):
+ Ra [s, a(i), b(i)]
+ Nhớ [s, a(i), b(i)]

Xây dựng 2 bảng trạng thái Nhớ và Ra cho phép toán cộng:

Giải thuật chương trình:

Nhận xét:
Việc sử dụng otomat có ra để cài đặt phép toán cộng trên cho kết quả với thời gian tốt hơn rất nhiều so với phương pháp thuần túy trên. Nhưng việc khó ta phải làm là phải xây dựng được các bảng trạng thái cho chương trình. Và không gian bộ nhớ lưu trữ là tốn hơn rất nhiều so với phương pháp thuần túy.
Vậy phụ thuộc khả năng của hệ thống để áp dụng cho hợp lý.

Tương tự ta cũng có bảng trạng thái Ra và Nợ cho phép toán trừ:

Ta đi tổ chức 2 mảng nhớ (3 chiều):
+ Ra [s, a(i), b(i)]
+ Nợ [s, a(i), b(i)]
+ Giải thuật giống phép cộng

B. Biểu diễn nhị phân (hệ đếm cơ số 2) cài đặt phép toán: *, /
a. Sử dụng phép cộng ở trên ta đã làm được để cài đặt phép nhân
Bài toán: Cho 2 số a, b có kích thược tương ứng m, n bit.
Thuật toán: Tương tự với phép nhân thông thường (theo phương pháp tính bằng tay)

Input: a, b
Output: c = a + b
1. Khởi tạo 1 thanh ghi tạm c : m + n bit
2. Duyệt bit trong b, có 2 trường hợp xảy ra
   a) b(i) = 0 : dịch con trỏ tại c(i) sang c(i + 1)
   b) b(i) = 1 : ta thực hiện 2 thao tác sau
        +) c = a + c tại vị trí bit là i về phía bên trái
        +) dịch c(i) sang c( i + 1) - con trỏ i
3. Kết thúc: c(m + n + 1) = nhớ.

Mã giả: Pseudo code

Dạng 1: Chưa mịn
. còn tiếp
Dạng 2: Mịn
. còn tiếp

C. Biểu diễn hệ đếm cơ số 4 các phép toán: +, -, *, /
Thuật toán thực hiện tương tự như trong hệ đếm cơ số 2 và ta có các bảng trạng thái như dưới đây

Kết quả:  1231 + 1210 = 3101 - hệ đếm cơ số 4 sử dụng otomat để tính toán.

D. Tự động sinh các bảng trạng thái cho hệ đếm cơ số n bất kỳ.

. Còn tiếp