Sáng tạo trong Thuật toán và Lập trình Tập I

6
CHƢƠNG 1
GIẢI MỘT BÀI TOÁN TIN Phần này sẽ giới thiệu một số bước thường vận dụng trong quá trình giải các bài
toán tin.
1. Bước đầu tiên và là bước quan trọng nhất là hiểu rõ nội dung bài toán.
Đây là yêu cầu quen thuộc đối với những người làm toán. Để hiểu bài toán theo
cách tiếp cận của tin học ta phải gắng xây dựng một số thí dụ phản ánh đúng các
yêu cầu đề ra của đầu bài rồi thử giải các thí dụ đó để hình thành dần những hướng
đi của thuật toán.
2. Bước thứ hai là dùng một ngôn ngữ quen thuộc, tốt nhất là ngôn ngữ toán học đặc
tả các đối tượng cần xử lí ở mức độ trừu tượng, lập các tương quan, xây dựng các
hệ thức thể hiện các quan hệ giữa các đại lượng cần xử lí.
3. Bước thứ ba là xác định cấu trúc dữ liệu để biểu diễn các đối tượng cần xử lí cho
phù hợp với các thao tác của thuật toán.
Trong những bước tiếp theo ta tiếp tục làm mịn dần các đặc tả theo trình tự từ trên
xuống, từ trừu tượng đến cụ thể, từ đại thể đến chi tiết.
4. Bước cuối cùng là sử dụng ngôn ngữ lập trình đã chọn để viết chương trình hoàn

Đặc tả: Gọi hai chữ số của số tự nhiên cần tìm x là a và b, ta có:
(1) x = ab.
(2) a, b = 0..9 (a và b biến thiên trong khoảng 0..9).
(3) a > 0 vì x là số có hai chữ số.
(4) (ab, ba) = 1.
Ta kí hiệu x' là số đối xứng của số x theo nghĩa của đầu bài, khi đó ta có đặc tả như
sau:
(5) x = 10..99 (x biến thiên từ 10 đến 99, vì x là số có hai chữ số).
(6) (x, x') = 1.
Nếu x = ab thì x' = ba. Ta có thể tính giá trị của x' theo công thức:
x' = (chữ số hàng đơn vị của x) * 10 + (chữ số hàng chục của x).
Kí hiệu Đơn(x) là toán tử lấy chữ số hàng đơn vị của số tự nhiên x và kí hiệu
Chục(x) là toán tử lấy chữ số hàng chục của x, ta có:
x' = Đơn(x)*10 + Chục(x).
Tổng hợp lại ta có đặc tả:
Số cần tìm x phải thoả các tính chất sau:x = 10..99 (x nằm trong khoảng từ 10 đến
99).
(7) x' = Đơn(x)*10 + Chục(x).
(8) (x, x') = 1 (ước chung lớn nhất của x và x' bằng 1).
Đặc tả trên được thể hiện qua ngôn ngữ phỏng trình tựa Pascal như sau:
(9) for x:=10 to 99 do
if ucln(x, đơn(x)*10+Chục(x))=1 then Lấy(x);
trong đó, ucln(a,b)là hàm cho ước chung lớn nhất của hai số tự nhiên a và b;
Lấy(x) là toán tử hiển thị x lên màn hình hoặc ghi x vào một mảng nào đó với mục
đích sử dụng lại, nếu cần.
Ta làm mịn đặc tả (10):
ucln(a, b): Thuật toán Euclid là chia liên tiếp, thay số thứ nhất bằng dư của nó
khi chia cho số thứ hai rồi hoán vị hai số.
(*-----------------------------------
Tim uoc chung lon nhat cua hai so

1. n := Tim;
2. Xem(n);
Bước 1. Tìm và ghi vào mảng s các số thoả điều kiện đầu bài, n là số lượng các số
tìm được.
Bước 2. Hiển thị các phần tử của mảng s[1..n] chứa các số đã tìm được.
Toán tử x' được viết dưới dạng hàm cho ta số tạo bởi các chữ số của x theo trật tự
ngược lại. Ta đặt tên cho hàm này là SoDao (số đảo). Hàm có thể nhận giá trị vào là
một số tự nhiên có nhiều chữ số.
Để tạo số đảo y của số x cho trước, hàm SoDao lấy dần các chữ số hàng đơn vị của
x để ghép vào bên phải số y:
y := y*10 + (x mod 10)
Sau mỗi bước, chữ số hàng đơn vị đã lấy được loại hẳn khỏi x bằng toán tử:
x := x div 10
Chỉ thị {$B-} trong chương trình NTCN (nguyên tố cùng nhau) dưới đây đặt chế
độ kiểm tra biểu thức lôgic vừa đủ. Khi đã xác định được giá trị chân lí cần thiết thì
không tiến hành tính tiếp giá trị của biểu thức đó nữa. Thí dụ, với các lệnh
x := 1; y := 5;
if (x > 5) and (x + y < 7)then y := y + 1
else y := y-1;
trong chế độ {$B-}, sau khi tính được giá trị chân lí (x > 5) = false, chương
trình sẽ bỏ qua nhân tử logic (x + y < 7), vì tích lôgic của false với giá trị tuỳ ý
cho ta false. Trong trường hợp này lệnh y := y - 1 sẽ được thực hiện. Ngược lại,
nếu ta đặt chỉ thị {$B+} thì chương trình, sau khi tính được (x > 5) = false vẫn
tiếp tục tính giá trị của (x + y < 7) rồi lấy tích của hai giá trị tìm được (false
and true = false) làm giá trị của biểu thức điều kiện trong cấu trúc rẽ nhánh nói
Sáng tạo trong Thuật toán và Lập trình Tập I

9
var x,d: integer;
begin
d := 0; {So luong cac so can tim }
for x := 10 to 99 do
if Ucln(x,SoDao(x)) = 1 then
begin
d := d + 1; s[d]:= x;
end;
Tim := d;
end;
(*------------------------------------
Hien thi mang s[1..n] tren man hinh.
--------------------------------------*)
procedure Xem(n: integer);
var i: integer;
begin
writeln;
for i := 1 to n do write(s[i]:4);
writeln;
end;
BEGIN
n := Tim; Xem(n); writeln;
Sáng tạo trong Thuật toán và Lập trình Tập I

10
write(' Tong cong ',n,' so'); readln;
END.

return a;
}
static int SoDao(int x)
{ int y = 0;
do { y = y*10+(x%10); x /= 10; } while (x!=0);
return y;
}
} // SoThanThien
} // SangTao1
Cải tiến
Ta vận dụng tính đối xứng đã nhận xét ở phần trên để cải tiến chương trình. Như
vậy chỉ cần khảo sát các số x = ab, với a > b  0. Trường hợp a = b ta không
xét vì khi đó x' = x và do đó Ucln(x, x) = x  10  1.
Nếu b = 0 ta có x = 10a và x' = a. Ta thấy Ucln(10a, a) = a = 1 khi và chỉ
khi a = 1. Do đó ta xét riêng trường hợp này. Khi ab = 10 ta có (10, 1) = 1.
Vậy 10 chính là một số cần tìm và là số đầu tiên.
Sáng tạo trong Thuật toán và Lập trình Tập I

11
Mỗi khi tìm được hai chữ số a và b thoả điều kiện a > b và Ucln(a*10 + b, b*10 +
a) = 1 ta đưa a*10 + b vào kết quả, nếu b > 0 ta đưa thêm số đảo b*10 + a vào kết quả.
(* Pascal *)
(*-------------------------------------
So Than thien: Phuong an 2
---------------------------------------*)
function Tim2: integer;
var a,b,d: integer;

4. Nếu dãy a, b, c lập thành một cấp số cộng thì số đứng giữa b là trung bình
cộng của hai số đầu và cuối: b = (a + c)/2 hay 2b = a+c.
Từ (4) ta suy ra (a + c) là số chẵn. Do c lẻ, (a + c) chẵn nên a lẻ.
Nếu biết a và c ta tính được x = 100a +10(a + c) / 2 + c
= 100a + 5(a + c) + c = 105a + 6c.
Vì chỉ có 5 chữ số lẻ là 1, 3, 5, 7 và 9 nên tổ hợp của a và c sẽ cho ta 25 số.
Tổ chức dữ liệu
Sáng tạo trong Thuật toán và Lập trình Tập I

12
Ta tạo sẵn mảng nguyên 5 phần tử ChuSoLe[1..5] và gán trước các giá trị 1, 3,
5, 7, 9 cho mảng này. Trong Turbo Pascal (TP) việc này được thực hiện thông qua khai
báo:
const ChuSoLe: array[1..5] of integer = (1,3,5,7,9);
Chú ý rằng khai báo này phải đặt trong mục const là nơi khai báo hằng.
Trong C# ta khai báo như sau:
int [] ChuSoLe = {1,3,5,7,9};
Ý nghĩa của dòng khai báo trên là như sau: Xin cấp phát một biến mảng kiểu
nguyên có 5 phần tử với chỉ dẫn từ 1 đến 5, tên biến là ChuSoLe. 5 phần tử của biến
được gán trước các trị 1, 3, 5, 7 và 9.
Sau đó, mỗi khi cần, ta chỉ việc duyệt mảng ChuSoLe là thu được toàn bộ các
chữ số lẻ theo trật tự đã khai báo trước.
Chú ý
Thủ tục inc(d) trong chương trình TP dưới đây tăng giá trị của biến d lên thêm 1 đơn
vị, tức là tương đương với câu lệnh d := d + 1 và ++d (C#). Tương tự, thủ tục
dec(d) sẽ giảm giá trị của biến d xuống 1 đơn vị, tương đương với câu lệnh d := d
– 1 và --d (C#).

end;
Tim := d;
end;
Sáng tạo trong Thuật toán và Lập trình Tập I

13
(*---------------------------------------
Hien thi mang s[1..n] moi dong 20 so
-----------------------------------------*)
procedure Xem(n: integer); tự viết
BEGIN
n := Tim; Xem(n); writeln;
write('Tong cong ',n,' so'); readln;
END.
// C#
using System;
namespace SangTao1
{
class SoCapCong
{
static void Main(string[] args)
{
Show(Find());
Console.WriteLine("\n fini");
Console.ReadLine();
}
static int[] Find()