1 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
Mục lục
2 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
I. Giải chuỗi phương trình phản ứng hóa học
I.1. Mô tả bài toán
1. Bài toán
Bài toán giải chuỗi phương trình phản ứng có dạng phản ứng dây chuyền, trong đó
một chất có thể phản ứng với chất khác để tạo thành chất mới, chất mới lại có thể phản
ứng để tạo thành chất mới khác…Trong mỗi phản ứng có thể sẽ có một hoặc vài chất
không biết (thường được ký hiệu bởi các kí tự A,B,C …). Yêu cầu của bài toán là xác
định được các chất này.
Ví dụ : cho chuỗi phương trình phản ứng:
hãy xác định các chất A
1
, A
2
, B
1
, B
2
, C
1
, C
2
, D
1
, D
2
, E
1
, E

2
, F
1
, F
2
, F
3
.
2. Cách giải
• Bước 1: Thông thường nên liệt kê lại danh sách các phản ứng.
Ví dụ:
…
• Bước 2: sử dụng kiến thức đã biết (các luật trong database) về các phản ứng hóa
học có thể xảy ra áp dụng lên từng phương trình phãn ứng, ta sẽ có được danh
sách các chất có khả năng là chất chưa biết.
Ví dụ:
N
2
+ A
1
t
0
A
2
B
1
B
2
+H
2

O
t
0
C
1
C
2
+NaOH
D
1
D
2
H
2
O + CO
2
E1
E
2
F
2
A
1
F
3
F
1
B
1
H

2
O
3 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
o ở pt(1) sau khi áp dụng các luật ta có được kết luận :A
2
có khả năng là một
trong 2 chất “Chất E” và “chất F”.
o ở pt(2) sau khi áp dụng các luật ta có được kết luận :A
2
có khả năng là một
trong 2 chất “Chất E” và “chất K”.
• Bước 3: kết hợp các khả năng ở các phương trình khác nhau để suy ra kết luận
cuối cùng.
Ví dụ : từ kết luận về chất của A
2
ở 2 phương trình ta suy ra được A
2
là “chất E” (do
“chất E” là khả năng xuất hiện ở cả 2 pt).
I.2. Cấu trúc dữ liệu
1. Chat (chất)
• Danh sách các nguyên tố hóa học
• Danh sách các hệ số ứng với các nguyên tố
Ví dụ: chất H2SO4 được lưu thành [[H,S,O],[2,1,4]]
2. Rule(phương trình phản ứng có thể xảy ra, lưu trữ trong
database)
• Tập các chất phản ứng
• Tập các chất kết quả
• Tập các chất xúc tác (kiểu name)
4 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e

Ví dụ: phương trình phản ứng :
Được lưu như sau:
3. Ptpu (là phương trình phãn ứng input vào có chứa biến)
• Tập các biến phản ứng (kiểu name)
• Tập các chất phản ứng
• Tập các biến kết quả (kiểu name)
• Tập các chất kết quả
• Tập các chất xúc tác (kiểu name)
Ví dụ: phương trình :
5 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
(trong đó A, B là biến) được lưu như sau:
I.3. Thuật giải
1. Mô tả
• Input: danh sách các phương trình phản ứng, danh sách các rule trong database
(toàn cục)
• Ouput: kết quả (biến A là chất …, biến B là chất …).
• Biến:
o Allbien: lưu trữ lại các chất có khả năng là biến tương ứng trên từng
phương trình.
o Allnamebien: lưu trữ lại các tên của các biến.
o Listchatkhanang: lưu trữ lại các chất có khả năng sao khi loại bỏ các chất
không xuất hiện ở tất cả các phương trình mà biến đó có mặt.
2. Thuật toán
• B1: ứng với mỗi ptpu trong danh sách phương trình phản ứng nhập vào làm
o ứng với mỗi rule trong tập luật trong database làm
 Nếu rule áp dụng được cho ptpu thì
• Chattiemnangvt := rule[1] minus ptpu[2]
• Chattiemnangvp:=rule[2] minus ptpu[4]
• ứng với mỗi bienpu trong ptpu[1] làm
o nếu bienpu đã có trong allnamebien

 thêm chattiemnangvt vào allbien tương ứng
o ngược lại
 thêm chattiemnangvt vào allbien mới
• ứng với mỗi bienpu trong ptpu[3] làm
o nếu bienpu đã có trong allnamebien
 thêm chattiemnangvp vào allbien tương ứng
o ngược lại
 thêm chattiemnangvp vào allbien mới
• B2: for i from 1 to nops(allnamebien) làm
o Chatkhanang:={};
o For chat in allbien[i][1] làm
 Flagall:=1;
 For ichat from 2 to nops(allbien[i]) làm
• Nếu chat không thuộc allbien[i][ichat] thì
o Flagall:=0;
o Break;
6 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
 If flagall = 1 then chatkhanang := chatkhanang union {chat};
o Thêm chatkhanang vào listchatkhanang
• B3:for i from 1 to nops(listchatkhanang)
o Xuất allnamebien[i]
o If nops(listchatkhanang[i])=1 thì
 Xuất “là” listchatkhanang[i]
o Else
 For ptpu in phương trình phãn ứng input
• Nếu allnamebien[i] thuộc ptpu[1] thì
o For kntru in (ptpu[1] minus {allnamebien[i]}) làm
 Postru:=Search(kntru,allnamebien)
 Nếu nops(listchatkhanang[postru])=1
• Listchatkhanang[i]:=listchatkhanang[i]

minus listchatkhanang[postru]
• Nếu allnamebien[i] thuộc ptpu[3] thì
o For kntru in (ptpu[3] minus {allnamebien[i]}) làm
 Postru:=Search(kntru,allnamebien)
 Nếu nops(listchatkhanang[postru])=1
• Listchatkhanang[i]:=listchatkhanang[i]
minus listchatkhanang[postru]
 Xuất “là” listchatkhanang[i]
I.4. Dữ liệu mẫu
1. Bài toán
Cho chuổi phương trình phãn ứng sau:
(1)
(2)
(3)
(4)
(5)
Hãy xác định các chất A, B, C, D, E, F, G, L, M.
2. Minh họa chạy thuật toán
7 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
Các luật cần thiết:
(1)
(2)
(3)
(4)
(5)
Chạy chương trình:
• Bước 1: xác định các chất tiềm năng cho từng biến:
o ứng với pt(1), chỉ có luật (1) có thể áp dụng. kết luận A,B là KCl hoặc O2
o ứng với pt(2), chỉ có luật (2) có thể áp dụng. kết luận A là KCl; C,D,E,F là
1 trong 4 chất Cl2, MnSO4, K2SO4, H2O.

o ứng với pt(3), chỉ có luật (3) có thể áp dụng. kết luận A là KCl; G,C là K
hoặc Cl2
o ứng với pt(4), chỉ có luật (4) có thể áp dụng. kết luận G là K; L, M là KOH
hoặc H2.
o ứng với pt(5), chỉ có luật (5) có thể áp dụng. kết luận C,L là Cl2 hoặc KOH;
A,F là KCl hoặc H2O.
• Bước 2: kết hợp giữa các kết luận ở bước 1, nếu tiềm năng nào xuất hiện trong tất
cả kết luận, thì biến đó chính là chất tiềm năng đó.
o A có 4 kết luận (KCL hoặc O2),(KCL),(KCl),(KCl hoặc H2O), vậy kết luận
A là KCl.
o B có 1 kết luận (KCl hoặc O2), không thể loại bỏ.
o C có 3 kết luận (Cl2, MnSO4, K2SO4, H2O),( K hoặc Cl2),( Cl2); vậy kết
luận C là Cl2.
o D,E có 1 kết luận (Cl2, MnSO4, K2SO4, H2O); không thể loại bỏ.
o F có 2 kết luận (Cl2, MnSO4, K2SO4, H2O),( KCl hoặc H2O); vậy F là
H2O.
o …
• Bước 3: kết hợp giữa các biến trong cùng pt để loại bỏ các tiềm năng đã được biến
khác sử dụng.
8 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
o A,B cùng xuất hiện trong pt(1), A là KCl, B là KCl hoặc O2; vậy kết luận B
là O2.
o C,D,E,F cùng xuất hiện trong pt(2), C là Cl2, F là H2O; vậy kết luận D,E là
MnSO4 hoặc K2SO4.
o …
I.5. Kết quả chạy chương trình
1. Các rule
2. Danh sách phương trình phãn ứng
3. Kết quả
A la: {[[K, Cl], [1, 1]]}

B la:{[[O], [2]]}
C la: {[[Cl], [2]]}
D la:{[[K, S, O], [2, 1, 4]], [[Mn, S, O], [1, 1, 4]]}
E la:{[[K, S, O], [2, 1, 4]], [[Mn, S, O], [1, 1, 4]]}
F la: {[[H, O], [2, 1]]}
9 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
G la: {[[K], [1]]}
L la: {[[K, O, H], [1, 1, 1]]}
M la:{[[H], [2]]}
II. Mã hóa RSA
II.1. Mô tả bài toán
1. Mô tả
Do Rivest, Shamir và Adleman sáng lập vào năm 1978. Hệ RSA được xây dựng
trên cơ sở mã mũ, dựa vào định lý Euler đã đề cập trong chương trước. Trong đó khoá lập
mã là cặp (e,n) gồm số mũ e và mô-đun n. Số n được dùng ở đây là tích của hai số
nguyên tố rất lớn nào đó, n = pq, và e được chọn sao cho (e,ϕ(n)) = 1. Để mã hoá một
thông báo, trước tiên ta chuyển các chử cái thành các số tương ứng và nhóm thành các
khối với độ dài đủ lớn (tuỳ thuộc khả năng tính toán và không vượt quá n). Để mã hoá
một khối M trong văn bản, ta thực hiện theo công thức sau :
C
≡
Me(mod n), 0 < C < n
Quá trình giải mã đòi hỏi phải biết được một nghịch đảo d của e mô-đun ϕ(n).
Nghịch đảo này tồn tại theo điều kiện (e,ϕ(n)) = 1. Muốn giải mã một khối C trong văn
bản mật ta tính :
Cd
≡
(Me)d
≡
Med

≡
Mk
ϕ
(n)+1
≡
M.(M
ϕ
(n))k
≡
M (mod n)
Trong đó ed = kϕ(n)+1 đối với số nguyên k nào đó, vì ed ≡ 1(mod ϕ(n)), và do định
lý Euler ta có : Mϕ(n) ≡ 1 (mod n), khi (M,n) = 1(chú ý rằng, xác suất để M và n không
nguyên tố cùng nhau là hết sức nhỏ, vì điều đó chỉ xảy ra khi M có ước là p hoặc q). Cặp
(d,n) được gọi là khoá giải mã
10 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
Ví dụ : Giả sử lấy p = 53, q = 61, n = 53.61 = 3233, và e = 17. Trong trường hợp
đó ta có (e,ϕ(n)) = (17,52.60) = 1. Bây giờ ta mã văn bản sau :
“Đa gưi tiên”
Trước tiên ta chuyển các kí tự sang các số tương ứng theo bảng sau :
a ă â b c d đ e ê g h i k l m
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
n o ô ơ p q r s t u ư v x y
16 17 18 19 20 21 22 23 24 25 26 27 28 29
0701 102612 24120916
Do 2929 < 3233 do đó ta có thể nhóm các kí tự thành nhóm 2 kí tư :
0701 1026 1224 1209 16
Ta mã hoá theo công thức sau : C ≡ M17(mod 3233). Ở đây ta chỉ làm thử một
nhóm đầu tiên :
(701)17 ≡ 140 (mod 3233)
Để giải mã ta tìm nghịch đảo d của e theo mô-đun ϕ(n). Dùng thuật toán Euler mở

rộng tìm được d = 2753. Như vậy để giải mã ta làm như sau :
(140)2753 ≡ 701(mod 3233)
11 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
2. Thuật toán
• Chọn 2 số nguyên tố lớn p, q.
• Tính n = p*q
• Tính ϕ(n) = (p-1)(q-1)
• Tìm số nguyên e nguyên tố cùng nhau với ϕ(n) (tức ước số chung lớn nhất của e
và ϕ(n) = 1).
• Tính d là nghịch đảo mod ϕ(n) của e.
• Chuyển văn bản sang dạng số theo cơ sở n. văn bản sẽ có dạng sau: a
1
a
2
…a
n
.
• Để mã hóa văn bản tính lần lượt theo công thức:
• Để giải mã văn bản tính lần lượt theo công thức:
II.2. Cấu trúc dữ liệu
1. Định nghĩa kiểu dữ liệu mới
12 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
2. Hàm tạo khóa
3. Mã hóa
4. Giải mã
13 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
II.3. Dữ liệu mẫu và kết quả chạy chương trình
1. Dữ liệu mẫu
2. Kết quả chạy chương trình với độ dài khóa là 100
14 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e

15 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e
16 | G i ả i m ộ t s ố b à i t o á n b ằ n g M a p l e