Tải bản đầy đủ (.doc) (6 trang)

Thuật toán ấn tượng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (138.71 KB, 6 trang )

Những giải thuật ấn tượng : Biến Hình
Nguyễn Xuan Huy
NămNhâm Ngọ xin giới thiệu với các bạn một giải thuật hay do các bạn học sinh đềxuất.
Giải thuật này có thể nói là nhanh như ngựa phi.
Bàitoán (Lát nền) Người ta cần lát kín một nền nhà hình vuôngcạnh dài n = 2
k
, (k là một
số tự nhiên trong khoảng 1..6) khuyết mộtphần tư phía trên phải bằng những viên gạch
màu hình thước thợ tạo bởi 3 ôvuông đơn vị như trong hình 1. Hai viên kề cạnh phải có
hai màu khác nhau. Hãycho biết một cách lát với số màu ít nhất.
Dữ liệu vào: tệp văn bảnLATNEN.INP chứa số tự nhiên n.
Dữ liệu ra: tệp văn bảnLATNEN.OUT: Dòng đầu tiên là hai số tự nhiên: m biểu thị số viên
gạch và c làsố màu cần dùng cho việc lát nền. Tiếp đến là một phương án lát nền tìm
được,trong đó mỗi viên gạch lát được tạo bởi 3 chữ số giống nhau thể hiện màu củaviên
gạch đó. Các số trên mỗi dòng cách nhau bởi dấu cách (xem hình 1).
Thídụ,
Lời giải sau đây của bạn LêHoàng Hải, lớp 10 chuyên Tin, Đại học Khoa học Tự nhiên,
Đại học Quốcgia Hà Nội.
Để tính số viên gạch ta lấy 3phần tư diện tích chia cho 3 là diện tích 1 viên gạch thước thợ:
sogach:=((3*n*n) div 4) div 3;
Về số màu, với n = 2 thì chỉcần 1 viên gạch màu 1. Với mọi n > 2 ta cần tối đa 3 màu.
Đầu tiên ta gọi thủ tục Initđể khởi trị với hình vuông cạnh v = 2 nằm ở góc dưới trái của
nền nhà được biểudiễn dưới dạng một mảng hai chiều a:ba ô trong hình vuông 2 2 sẽđược
điền giá trị 1, ô nằm ở góc trênphải được điền giá trị 2. Gọi hình được khởi trị là A. Mỗi
bước tiếp theo tathực hiện ba thao tác biến hình sau đây (Hình 2):
Tịnh tiến A theo đường chéo để thu dược hình B (xem thủtục DichCheo).
Lật A sang phải (tức là lấy đối xứng gương qua trụctung) để thu được hình C (xem thủ tục
LatPhai).
Lật A lên trên (tức là lấy đối xứng gương qua trụchoành) để thu được hình D (xem thủ tục
LatLen).
Chú ý rằng khi lật ta cầnthực hiện thêm phép hoán đổi trị 1 và 3 cho nhau.


Mỗi lần lặp như vậy ta sẽ thuđược hình vuông cạnh tăng gấp đôi hình trước. Khi v = n ta
gọi thủ tục Fini đểghi 3 mảnh D, A và C vào tệp kết quả.
Bình luận: Thuật giải sử dụng hai phép biến hình cơ bảntrong chương trình phổ thông là
phép dời hình (tịnh tiến) và đối xứng qua trục.Việc hoán đổi trị 1 và 3 cho nhau là một ý
tưởng thông minh. Mỗi ô trong bảngđược điền đúng 1 lần do đó độ phức tạp tính toán của
thuật toán là n
2
,trong khi các bài giải khác đều phải sử dụng các phép dò tìm để xác định
màu tôvà gọi đệ quy nên thường tốn gấp đôi.
Những giải thuật ấn tượng: 2 x 5 = 10
Nguyễn Xuân Huy
Lần này xin kể về giải thuậtcủa bạn Việt Hưng, lớp 12 chuyên Tin - Nguyễn Huệ - Hà Tây.
Bài toán (chữ số cuối khác 0, thi Tin học Quốc giaIreland, 1994) Tìm chữ số cuối cùng
khác0 của n! với n trong khoảng 1..100.
Thí dụ: n = 7, kết quả = 4
n = 15, kết quả = 8
Thuật giải của bạn Việt Hưngcho phép mở rộng giới hạn của n đến hàng chục vạn, và nếu
bạn muốn, có thể tiếptục mở rộng đến hàng triệu.
ý tưởng chính của Việt Hưng nằm ở công thức: 2.5=10 (hai lần năm là mười). Thật vậy, ta
biết n! = 1.2.3...n. Các chữ số0 ở đầu phải của n giai thừa được sinh ra khi và chỉ khi trong
khai triển rathừa số nguyên tố của tích trên có chứa 2 và 5.Vậy thì trước hết ta đếm
sốlượng các thừa số 2, ký hiệu là d2 và số lượng các thừa số 5, ký hiệu là d5.Thí dụ, với n
= 15 ta có dạng khai triển ra thừa số nguyên tố của n giai thừanhư sau:
n! =1.2.3.(2.2).5.(2.3).7.(2.2.2).9.(2.5).11. (2.2.3).13.(2.7).(3.5). Do đó d2=11và d5=3. Vậy
ta có 3 cặp 2.5=10, và số mũ còn thừa của 2 sẽ làd2-d5=11-3=8.
Dễ thấy với mọi n, ta luôn cód2 >= d5 vì cứ 2 số liên tiếp thì có một số chia hết cho 2, còn
5 số liêntiếp mới có một số chia hết cho 5.
Việc còn lại là lấy tích củacác phép nhân các số còn lại. Vì các tích này không bao giờ tận
cùng bằng 0 chonên ta chỉ cần giữ lại một chữ số cuối cùng bằng cách lấy mod 10.
Để tính chữ số tận cùng của 2

k
với k = d2 - d5 khác 0 ta để ý đến tínhtuần hoàn của nó, cụ
thể là ta chỉ cần tính 2
k mod 4
với các trườnghợp: k mod 4 = 0, 1, 2 và 3.
Theo thí dụ trên ta có k mod4 = 8 mod 4 = 0, do đó chữ số cuối của 2
k
là 6.
Ta tính được6.3.3.7.9.11.3.13.7.3 mod 10 = 8.
Lưu ý rằng (a.b) mod m=((a mod m).(b mod m)) mod mcho nên ta có thể lấy mod ở các
bước trung gian.
Bình luậnNhiều bạn lầm tưởng rằng chỉ cần lấy các số trong dãy nhân với nhau rồi lấy
dưtheo 10 là được. Để ý rằng 14! =87178291200, 15! = 1307674368000. Nếu để tính 15!
mà bạn chỉ lấy một chữsố cuối khác 0 của các phép tính trung gian thì sau khi tính chữ số
cuối của14! bạn sẽ nhận được 2 và cuối cùng là (2*15) mod 10 = 30 mod 10 = 3. Kết
quảnày là sai vì chữ số cuối khác 0 của 15! là 8.
Chương trình sau đây chứa thủtục find tìm chữ số cuối cùng khác 0 của n! với n trong
khoảng 1..65535.
(* Tim chu so khac khong cuoi cung cua n! *)
uses crt;
var n: word;
function find: word;
var d2,d5:word;
i,k,c:word;
begin
k := 1;
find:=k;
if n<=1then exit;
d2:=0;d5:=0;
for i:=2 ton do

begin
c:=i;
{dem cacthua so 2}
while cmod 2 = 0 do
begin
inc(d2);
c:=cdiv 2;
end;
{dem cacthua so 5}
while cmod 5 = 0 do
begin
inc(d5);
c:=cdiv 5;
end;
k:=(k*c)mod 10;
end;
{ 2^(d2-d5)mod 10 }
case(d2-d5) mod 4 of
0: c:=6;
1: c:=2;
2: c:=4;
3: c:=8;
end;

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

Tải bản đầy đủ ngay
×