Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
Nhóm sinh viên thực hiện: Nhóm 32
Thành Viên Nhóm:
Trần Anh Đức
Trần Xuân Tới
Vũ Duy Anh
Đỗ Văn Tuyên
Nguyễn Duy Tuấn
Đề Tài: Thao tác với ADT Mảng
•
Sơ Đồ Thực Hiện:
0. Phân công công việc
1. Mô tả yêu cầu bài toán
2. Biểu đồ IPO
3. Thiết Kế Chương Trình
4. Thiết kế dữ liệu
5. Thiết kế giải thuật
6. Các kỹ thuật lập trình áp dụng
7. Demo Chương trình
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
1. Mô tả yêu cầu bài toán

Tạo một ADT có tên là Array và lưu trữ trong file Array.h

ADT này bao gồm 2 thành phần thông tin:

Max: mảng các giá trị số thực

Count: số lượng các giá trị lưu trữ trong mảng Max

Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
1. Mô tả yêu cầu bài toán

ADT này cho phép thực hiện một số thao tác trên mảng số
thực:

Khởi tạo một phiên bản mới của chính nó

Gán giá trị cho các thành phần thông tin của một đối
tương Array

Sắp xếp các phần tử của mảng theo giải thuật bubble sort

Sắp xếp các phần tử của mảng theo giải thuật insertion
sort
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
1. Mô tả yêu cầu bài toán

Sắp xếp các phần tử của mảng theo giải thuật selection
sort

Tìm giá trị lớn nhất được lưu trữ trong mảng và vị trí của
các phần tử có giá trị lớn nhất trong mảng

Tìm giá trị nhỏ nhất được lưu trữ trong mảng và vị trí của
các phần tử có giá trị nhỏ nhất trong mảng

Tìm giá trị trung bình của các phần tử trong mảng

Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
1. Mô tả yêu cầu bài toán

Tìm độ lệch về giá trị giữa 2 phần tử có vị trí biết trước
trong mảng

Tìm độ lệch trung bình về giá trị của các phần tử trong
mảng

Tìm kiếm (theo giải thuật sequential search

Tìm kiếm (theo giải thuật binary search)

Biểu diễn độ phức tạp tính toán theo ký pháp big-O và
hiện thị thời gian tính toán thực tế bằng micro-second.
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
•
Viết chương trình để kiểm tra các chức năng trên
Cho phép người dùng chọn cách nhập dữ liệu và cách hiển
thị kết quả.
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
Thành Viên Công việc <Tất cả thành viên tham
gia fix lỗi>
Trạng thái
Trần Anh Đức Viết menu, thiết kế cấu trúc chương
trình và dữ liệu cho bài toán, tính độ
lệch trung bình, Viết báo cáo và đặc

biệt chuyên đi tối ưu hóa các bài
toán con của các thành viên.
Chưa tốt
Trần Xuân Tới Viết các giải thuật sắp xếp. Tìm kiếm
phần tử nhỏ nhất, lớn nhất, độ lẹch
2 phần tử
Tốt
Vũ Duy Anh Tính toán thời gian thực hiện các giải
thuật sắp xếp.
Tốt
Đỗ Văn Tuyên Viết các giải thuật sắp xếp. Chưa tốt
Nguyễn Duy Tuấn Tính toán và tìm kiếm trên mảng.
Viết tài liệu present.
Chưa tốt
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
0. Phân công công việc
2. Biểu đồ IPO
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
INPUT PROCESS OUTPUT
Array Sắp xếp theo ba thuật toán bubble
sort, selection sort, insertion sort
Array được sắp xếp
Array Tính giá trị trung bình Giá trị trung bình
Array Tính độ lệch 2 phần tử Giá trị độ lệch hai phần tử
Array Tính độ lệch trung bình Giá trị độ lệch trung bình
Array, và giá trị cần tìm Tìm kiếm theo thuật toán nhị phân
hoặc tuần tự
In ra vị trí tìm thấy, nếu ko thấy thì in ra thông

báo ko tìm được
Array Tìm các vị trí min và max In ra một mảng các ví trị ở đó có giá trị là min
hoặc max
Array Tính thời gian thi hành các giải thuật
sắp xếp cho các phần tử
Thời gian thi hành các thuật toán sắp xêp
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
3. Thiết kế chương trình
Main menu
Enter array
Print the array
Make a copy
A = B
Find maxs
Find mins
Average
Difference
Average
Difference two
element
Sorting
Searching
Calc time
From stdin
From a file
Bubble sort
Selection sort
Insertion sort
Bubble sort

Selection sort
Insertion sort
Binary search
Sequential search
4. Thiết kế dữ liệu
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
Array
Properites
Method
Properites
Max Count
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
4. Thiết kế dữ liệu
Method
Độ lệch trung bình
Tìm kiếm
Sắp xếp
Độ lệch giữa 2 phần tử
Tạo một bản copy
Tính toán thời gian
Đa toán tử =
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
4. Thiết kế dữ liệu
5. Thiết kế giải thuật
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
Các giải thuật tìm kiếm và sắp xếp

không có gì phức tạp
6. Các kỹ thuật lập trình áp dụng
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
STT Kỹ thuật / quy tắc Đối tượng áp dụng và phạm vi áp dụng
I.Các kỹ
thuật
làm việc
với biến
1 Đặt tên biến dễ nhớ hướng tới
mục đích biến sử dụng
Toàn bộ chương trình
2 Sử dụng các kiểu dữ liệu hợp lý Toàn bộ chương trình
3 Khai báo hạn chế giá trị Sử dụng cho việc nhập tên chuỗi để mở
file
4 Khởi tạo 1 lần dùng nhiều lần Sử dụng hầu hết trong mọi hàm
5 Giá trị khởi tạo Sử dụng cho mảng ban đầu để kiểm tra
người dùng đã nhập mảng hay chưa
6 Khai báo biến tĩnh Dùng HANDLE stdout để điều khiển giao
diện chương trình
7 Thêm biến trung gian Sử dụng trong các hàm tính thời gian,
tính giá trị trung bình, tạo bản copy…
II.Các kỹ
thuật viết
mã
chương
trình hiệu
quả
1 Định dạng cấu trúc code rõ ràng Toàn bộ chương trình
2 Cấu trúc lặp hợp lý Trong các giải thuật tìm kiếm, sắp xếp,

tính thời gian, hay trong hàm điều
khiển menu
3 Break khi dùng switch Hầu hết sử dụng trong menu
II.Các kỹ
thuật
thiết kế
chương
trình
1 Top-Down design Toàn bộ chương trình
Module hóa chương trình Chia bài toán thành các modulo riêng,
phân chia cho các thành viên trong
nhóm
3 Dữ liệu được thiết kế theo
chuẩn ISO =))
:D
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
6. Các kỹ thuật lập trình áp dụng
IV.Các kỹ
thuật xây
dựng
hàm/thủ
tục
1 Đặt tên hàm dễ nhớ theo
đúng chức năng
Toàn bộ chương trình
2 Trừu tượng hóa hàm <
3 Loại bỏ các phần dư thừa
trong các thủ tục con


4 Che giấu thông tin Khai báo các hàm trong header và sử
dụng trong checkarray.cpp
5 Sử dụng macro Sử dụng trong nhập một array(sử dụng
define rút ngắn code)
6 Đa năng hóa toán tử Sử dụng toán tử = cho array
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
6. Các kỹ thuật lập trình áp dụng
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
6. Các kỹ thuật lập trình áp dụng
V.Các
kỹ
thuật
bẫy lỗi
và lập
trình
phòng
ngừa
1 Bẫy lỗi bằng cách dòng printf ở
đoạn nghi ngờ có lỗi
Toàn bộ chương trình
2 Phòng ngừa những âm mưu đen
tối của người dùng
Nhập sự lựa chọn, file ko đúng quy
định…
3 Nhất quán các hàm tương tự
nhau
Dùng trong các thuật toán sắp xếp
<

VI.Phon
g cách
lập
trình
Vì tất cả các mã nguồn thành viên được nhóm trưởng kết hợp lại, toàn bộ
chương trình đều mang style của nhóm trưởng
Nhóm trưởng: tên hàm, tên biến, comment tất cả đều bằng tiếng anh, viết
mã theo cấu trúc răng cưa, các dòng lệnh rõ ràng
7. Demo Chương Trình
Kỹ Thuật Lập Trình
Hà Nội, Tháng 5 - 2012
Giao diện được thiết kế đơn giản sử dụng các
hàm API console của Windows
Trân trọng cảm ơn sự hướng dẫn của cô Giang
và sự giúp đỡ của các bạn trong quá trình học
tập.