Lời nói đầu 0
Phần 1:Yêu cầu của đề: 1
Phần 2: Giới thiệu chi tiết đề tài 1
Chương 1: Tổng Quan: 1
I. Công việc đã làm 1
1. Tiến trình công việc: 1
2. Công việc cụ thể: 1
II. Công việc chưa làm 2
Chương 2 Tóm tắt các menu chính: 2
Chương 3 Chi tiết các modul : 4
1. n!: 4
2. Fibonacci: 5
3. ThapHaNoi 6
5. Insert_Sort: 8
8. Sequen_Search: 11
9. Sequen_Search: 12
11. DoiCoSo: 14
Chương 4: Hướng dẫn sử dụng qua giao diện chương trình 15
Tài liệu tham khảo: 22
24 trang |
Chia sẻ: huong.duong | Lượt xem: 1537 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Viết unit các thuật toán trong sách cấu trúc dữ liệu và giải thuật bằng ngôn ngữ Pascal, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Lời nói đầu
Với tốc phát triển hiện nay thì môn tin học trở thành một môn học không thể thiếu trong các trường phổ thông và các trường đại học. Cuốn sách Cấu Trúc Dữ Liệu và Giải Thuật của PGS. Đỗ Xuân Lôi đã trở thành tài liệu học tập và tham khảo của sinh viên ngành công nghệ thông tin ở nhiều cơ sở đào tạo Cao Đẳng, Đại Học và sau Đại Học.
Để việc học môn này trở nên dễ dàng hơn em đã viết lại một số thuật toán trong sách dưới dạng các Unit.
Phần 1:Yêu cầu của đề:
Viết unit các thuật toán trong sách cấu trúc dữ liệu và giải thuật bằng ngôn ngữ Pascal
Phần 2: Giới thiệu chi tiết đề tài
Chương 1: Tổng Quan:
Công việc đã làm
Tiến trình công việc:
Trong thời gian 2 tuần đầu của thực tập em đã nghiên cứu một số vấn đề quan trọng và căn bản có ý nghĩa trong việc thực hiện yêu cầu đã đặt ra của đề tài.
Các unit và menu chương trình được viết trong tuần thứ 3 và hoàn thành trong tuần 4.
Tuần 5 viết báo cáo và chỉnh sửa giao diện chương trình
Công việc cụ thể:
Dưới sự hướng dẫn tận tình của thầy Phạm Đức Khánh, sau 5 tuần : từ ngày 12-4-2005 đến ngày 16-5-2005 em đã làm được các công việc như sau:
Đệ quy: Viết Unit dequy gồm các thủ tục
N!
Fibonacci
Bài Toán Tháp Hà Nội
Bài Toán Xếp 8 Hậu
Sắp xếp: Viết Unint sapxep gồm các phương pháp
lựa chọn
Thêm dần
Nổi bọt
Sắp xếp nhanh
Vun đống
Hoà nhập
Tìm kiếm Unit timkiem gồm các thủ tục
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Ngăn xếp Unit nganxep có úng dung
Đổi cơ số từ một số hệ 10 sang hệ bất kỳ <10
Công việc chưa làm
Do thời gian có hạn nên còn nhiều thuật toán hay trong sách em chưa có điều kiên hoàn thành. Menu chương trình chính chưa được đẹp vì chương trình em viết hoàn toàn bằng ngôn ngữ Pascal – một ngôn ngữ có nhiều hạn chế về giao diện.
Chương 2 Tóm tắt các menu chính:
Chương trình chính có tên menu.pas gồm các modul sau:
KeO: kẻ khung chương trình
HienThi: hiển thị các lựa chọn của chương trình
Call_n: Gọi thủ tục giaithua trong Unit dequy.tpu để tính n!
Call_Fibonacci: Gọi thủ tục Fibonacci trong Unit dequy.tpu để tính dãy Fibonacci của một số nhập vào từ bàn phím
Call_ThapHN: Gọi thủ tục ThapHaNoi trong Unit dequy.tpu để thực hiện bài toán chuyển n đĩa từ cọc 1 sang cọc 2
Call_XepHau: Gọi thủ tục XepHau trong Unit Dequy.tpu để đưa ra các phương án xếp 8 con hậu không ăn nhau trên bàn cờ vua
Call_Select: Gọi thủ tục Select_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp lựa chọn
Call_Insert: Gọi thủ tục Insert_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp thêm dần
Call_Bubble: Gọi thủ tục Bubble_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp nổi bọt
Call_Quick: Gọi thủ tục Quick_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp sắp xếp nhanh
Call_Heap: Gọi thủ tục Head_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp vun đống
Call_Mergring: Gọi thủ tục Mergring_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp hoà nhập
Call_TimTuanTu: Gọi thủ tục Sequen_Search trong Unit SX_va_TK.tpu để tìm vị trí của một số trong dãy đã cho theo phương pháp tìm kiếm tuần tự.
Call_TimNhiPhan: Gọi thủ tục Binary_Search trong Unit SX_va_TK.tpu để tìm vị trí của một số trong dãy đã cho theo phương phán tìm vị trí của một số trong dãy đã cho theo phương phán tìm kiếm Nhị Phân
Call_DoiCoSo: Gọi thủ tục DoiCoSo trong Unint Stack.tpu để đổi một số từ số hệ 10 sang hệ bất kỳ < 10.
Chương 3 Chi tiết các modul :
n!:Begin
Nhập N
K= 1
I = 2
K: = k*i
I: =i+1
I > N
GiaiThua: = k
END
True
False
Fibonacci:
ta có : if n< = 2 then F(n) = 1
F(n) = F(n-2) + F(n-1)
Begin
Fibo = x+y
X = Y
Y = Fibo
END
i< = n
True
False
I = i+ 1
Nhập N
i = 2
x = 1
y = 1
Fibo = 0
ThapHaNoi Begin
Chuyển n -1 đĩa từ a sang b
Out a b
Chuyển n -1 đĩa từ c sang b
END
True
False
N0
N
4. Select_Sort:
Begin
True
False
N
I = 1
m = i
j = i+1
a[j] < a[m]
m = j
j = j+1
I > N
m i
True
True
M i
Đổi Chỗ a[j] , a[m]
I = i + 1
i > n - 1
False
False
False
END
5. Insert_Sort:
Begin
False
True
N
a [0] = -32767
i = 2
X = a [i]
j = j - 1
x < a[j]
a [j+1] = x
I = i + 1
False
END
I < = N
True
a[j+1] = a[j]
j = j - 1
6. Bubble_Sort:
Begin
False
True
N
i = 1
j = n
a[j] < a[j-1]
J = J - 1
False
END
J< I + 1
True
Đổi chỗ
a[j] , a[j-1]
I = i+1
I > n-1
False
True
7. Quick_Sort:
Begin
False
True
N
i = l
j = r
x= a[(i+j) div 2]
a[i] < x
i = i + 1
END
x< a[j]
Đổi chỗ a[j] , a[j]
i = i + 1
j = j - 1
True
True
j = j - 1
False
i< = j
True
i< = j
False
False
L < i
True
R = j
I < R
False
True
R = j
False
8. Sequen_Search:
Begin
END
False
N0
K
I = 1
a[n+1] = k
a[i] k
I = I+1
Sequen = i
True
9. Sequen_Search:
Begin
END
False
N0
K
I = 1
a[n+1] = k
a[i] k
I = I+1
Sequen = i
True
\
10. Binary_Search:
Begin
END
False
N0
K
I = 1;
a[n+1] = k
Binary = 0
L< = r
M = (r+l) div 2
True
K < a[m]
R = m - 1
True
K > a[m]
L = m + 1
True
False
False
Binary = m
11. DoiCoSo:
Begin
END
False
X, Y
T = 0
x 0
r = x mod y
True
push(c,t,r)
x = x div y
T > 0
pop(c,t,r)
R
True
False
Chương 4: Hướng dẫn sử dụng qua giao diện chương trình
Chương trình có thể chạy trên môi trường Windows 9x, 2000, xp hoặc Dos. Dung lượng chương trình nhỏ, gọn, không phài cài đặt.
Menu chương trình chính:
Tính n!:
Fibonacci:
ThapHaNoi:
XepHau:
Select_Sort:
Insert_Sort:
bubble_Sort:
Quick_Sort:
Heap_Sort:
Mergring:
Sequen_Search:
Binary_Search:
DoiCoSo:
Tài liệu tham khảo:
Giáo trình: Ngôn ngũ lập trình Pascal – Quách Tuấn Ngọc
Giáo trình: Bài tập ngôn ngũ lập trình Pascal – Quách Tuấn Ngọc
Giáo trình: Ngôn Ngữ lập trình Pascal nâng cao - Quách Tuấn Ngọc
Giáo trình: Bài tập ngôn Ngữ lập trình Pascal nâng cao - Quách Tuấn Ngọc
Sách :Turbo Pascal, cẩm nang tra cứu - Quách Tuấn Ngọc
Giao trình: Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi
Các file đính kèm theo tài liệu này:
- P0128.doc