cobebupbe138
New Member
Download miễn phí Tìm hiểu Thuật giải trong Turbo Pascal
Turbo Pascal là một phần mềm có nhiệm vụ giúp người thảo chương soạn thảo và thực hiện
các chương trình viết bằng ngôn ngữPascal. Các chức năng chính của Turbo Pascal là :
Cung cấp một hệ soạn thảo văn bản cho phép người thảo chương soạn và sửa chương trình dễ
dàng, tiện lợi.
Giúp người thảo chương tìm các lỗi về văn phạm trong chương trình.
Dịch (compiler) chương trình viết bằøng ngôn ngữ Pascal thành một chương trình viết dưới
dạng mã máy.
Thực hiện hay chạy ( Run ) chương trình viết bằng ngôn ngữ Pascal.
Cung cấp các thư viện có sẵn nhiều hàm (function) và thủ tục (procedure) chuẩn mang lại cho
người thảo chương nhiều công cụ hữu ích, làm giảm bớt khối lượng phải lập trình.
Là sản phẩm của hãng Borland nổi tiếng, Turbo Pascal (viết tắt là TP) không ngừng được cải
tiến, đến nay đã ra đời phiên bản 7.0. Tuy nhiên, ở mức độ thảo chương căn bản, người ta vẫn thích
dùng phiên bản 5.5 hay 6.0 vì nó đơn giản mà đủ dùng, tốc độ nhanh hơn, thích hợp với các máy
có cấu hình chưa mạnh.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ối ưu.Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra và To là
thời gian tối ưu thì người ta đã chứng minh được rằng
Với kết quả này, ta có thể xác lập được sai số mà chúng ta phải gánh chịu nếu dùng Heuristic thay
vì tìm một lời giải tối ưu. Chẳng hạn với số máy = 2 (n=2) ta có
, và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này, số máy
càng lớn thì sai số càng lớn.
Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, sai số tối đa mà ta phải chịu là T* ?
4/3To, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số
đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật giải Heuristic trong trường hợp
này rõ ràng đã cho chúng ta những lời giải tương đối tốt.
Bài toán Ta-canh - ứng dụng của hàm Heuristic
Bài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây là bài toán 9-
puzzle. Trò chơi bao gồm một hình vuông kích thước 3x3 ô. Có 8 ô có số, mỗi ô có một số từ 1
đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di chuyển một ô nằm cạnh ô trống về phía ô
trống. Vấn đề là từ một trạng thái ban đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng
thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái sang phải, từ trên xuống dưới, ô cuối
dùng là ô trống.
Cho đến nay, người ta vẫn chưa tìm được một thuật toán chính xác, tối ưu để giải bài toán này.
Tuy nhiên, cách giải theo kiểu Heuristic lại khá đơn giản. Nhận xét rằng : tại mỗi thời điểm ta chỉ
có tối đa 4 ô có thể di chuyển. Vấn đề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng
hạn ở hình trên, ta nên di chuyển (1), (2), (6) hay (7)?
Gọi T0 là trạng thái đích của bài toán và TK là trạng thái hiện tại. Ta gọi V(i,j) là con số nằm ở ô
(i,j), với ô trống V(i,j)=0.
Ta đặt d(i,j) là số ô cần di chuyển để đưa con số ở ô (i,j) về đúng vị trí của nó ở trạng thái TO .
Hàm FK tại trạng thái TK bằng tổng của các d(i,j) sao cho vị trí (i,j) không phải là ô trống.
Như vậy đối với trạng thái ở hình ban đầu, hàm FK sẽ có giá trị là
FK = 2+1+3+1+0+1+2+2=12.
Một cách tổng quát, giá trị hàm FK tại trạng thái TK sẽ là
Từ trạng thái TK , ta có tối đa 4 cách di chuyển.Ta ký hiệu các trạng thái mới này lần lượt là TKT
,TKD , TKTr ,TKP ứng với con số ở trên, dưới, trái, phải ô trống hiện tại bị di chuyển. Chẳng
hạn, ứng với hình ban đầu, ta có thể có 4 trạng thái mới như hình bên.
Ứng với các trạng thái mới, ta cũng sẽ có các hàm FK tương ứng là FKT ,FKD ,FKTr ,FKP.
Dựa vào 4 con số này, ta sẽ chọn hướng đi có hàm FK tương ứng là nhỏ nhất, trong trường hợp
bằng nhau ta chọn ngẫu nhiên một trong số các đường đó. Với ví dụ, ta sẽ chọn di chuyển ô mang
số (2) vì FKD là nhỏ nhất. Sau khi đã di chuyển một ô, bài toán chuyển về một trạng thái TK mới.
Ta lại thực hiện quá trình trên cho đến lúc đạt được trạng thái đích.
Hàm FK trong ví dụ của chúng ta là một dạng hàm Heuristic. Tất nhiên, để giải được bài toán này
trong những tình huống khó, hàm FK cần có nhiều sửa đổi.
I.GIỚI THIỆU NGÔN NGỮ PASCAL
PASCAL là ngôn ngữ lập trình cấp cao được giáo sư Niklaus Wirth ở trường đại học Kỹ
thuật Zurich (Thụy sĩ) thiết kế và công bố vào năm 1971. Ông đặt tên cho ngôn ngữ của mình là
Pascal để tưởng nhớ nhà toán học nổi tiếng người Pháp ở thế kỷ 17: Blaise Pascal, người đã sáng
chế ra chiếc máy tính cơ khí đầu tiên của nhân loại. Qua thời gian sử dụng, Pascal ngày càng
được đông đảo người dùng đánh gía cao, và trở thành một trong các ngôn ngữ thảo chương phổ
biến nhất hiện nay.
Thành công của ngôn ngữ Pascal là ở chỗ: nó là ngôn ngữ đầu tiên đưa ra và thể hiện được
khái niệm lập trình có cấu trúc. Ý tưởng về một chương trình có cấu trúc xuất phát từ suy nghĩ
cho rằng có thể chia một bài toán lớn, phức tạp thành nhiều bài toán nhỏ, đơn giản hơn. Nếu mỗi
bài toán nhỏ được giải quyết bằng một chương trình con, thì khi liên kết các chương trình con này
lại sẽ tạo nên một chương trình lớn giải quyết được bài toán ban đầu?.
Bằng cách chia một chương trình thành các chương trình con như vậy, người thảo chương
có thể lập trình để giải quyết riêng lẻ từng phần một, từng khối một, hay có thể tổ chức để nhiều
người cùng tham gia, mỗi người phụ trách một vài khối. Ðặc biệt khi phải thay đổi hay sửa chữa
trong một khối thì điều đó sẽ ít ảnh hưởng đến các khối khác.
Tính cấu trúc của ngôn ngữ Pascal còn thể hiện trong việc tổ chức các câu lệnh và tổ chức
dữ liệu. Từ các lệnh đã có, người thảo chương có thể nhóm chúng lại với nhau và đặt giữa hai từ
khóa Begin và End tạo thành một câu lệnh mới phức tạp hơn gọi là câu lệnh ghép. Ðến lượt mình,
hai hay nhiều lệnh ghép lại có thể được nhóm lại để tạo thành một câu lệnh ghép phức tạp hơn
nữa,.v.v. Tương tự như thế, ngôn ngữ Pascal cũng cho phép xây dựng các kiểu dữ liệu phức tạp
hơn từ các kiểu dữ liệu đã có.
Pascal là một ngôn ngữ không chỉ chặt chẽ về mặt cú pháp mà còn chặt chẽ về mặt dữ
liệu. Mỗi biến, mỗi hằng tham gia trong chương trình luôn có một kiểu dữ liệu xác định và chỉ
nhận những gía trị có cùng kiểu dữ liệu với nó. Ðiều này buộc người lập trình phải nắm chắc cú
pháp và luôn chú ý đến tính tương thích của các biểu thức về mặt kiểu dữ liệu. Chính vì thế, thảo
chương bằng ngôn ngữ Pascal là một cơ hội tốt không chỉ rèn luyện tư duy mà còn rèn luyện tính
cẩn thận và chính xác.
Ngày nay, Ngôn ngữ Pascal được dùng để viết các chương trình ứng dụng trong nhiều
lĩnh vực. Với văn phạm sáng sủa, dễ hiểu, với khả năng đủ mạnh, Pascal được xem là ngôn ngữ
thích hợp nhất để giảng dạy ở các trường phổ thông và đại học.
II.CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL
1.Tập ký tự cơ bản
Mỗi ngôn ngữ đều được xây dựng từ một tập ký tự nào đó. Nhiều ký tự nhóm lại với nhau
tạo nên các từ. Nhiều từ liên kết với nhau theo một qui tắc ngữ pháp nhất định (gọi là văn phạm)
thì tạo nên các mệnh đề. Trong các ngôn ngữ thảo chương, mệnh đề?còn được gọi là câu lệnh.
Một tập hợp các câu lệnh được sắp xếp theo một trật tự nhất định nhằm chỉ thị cho máy các thao
tác phải thực hiện tạo thành một chương trình. Các chương trình được soạn thảo bởi người thảo
chương và được lưu trữ trên đĩa dưới dạng các tập tin.
Ngôn ngữ Pascal được xây dựng trên bộ ký tự cơ bản, gồm:
các chữ cái la tinh: A, B, C,...,Z, a, b, c,..., z
các chữ số :0, 1, 2, 3, 4, 5, 6, 7, 8, 9
các ký hiệu đặc biệt: +, -, *, /, =, <, {, }, [, ], %, $, &, #, ...
ký tự gạch nối ‘_’ và ký tự trắng ‘ ‘ ( space)
Các chữ Ả rập: , , , ... không thuộc bộ ký tự của Pascal.
2. Từ khóa ( key word ):
Có một số từ được Pascal dành riêng cho việc xây dựng các câu lệnh, các khai báo, các phép
tính,... gọi là từ khóa. Việc sử dụng các từ ...