Đây là 3 bài tập Thầy ra:
Bài 1: Có 1000 phiếu thu tiền điện thoại và 999 biên lai thu tiền (trong đó có ghi sđt của thuê bao). Hãy xác định thuê bao nào chưa trả tiền.
Bài 2: Cho 1 ds gồm tên sách, tác giả, số đt, nhà sản xuất tất cả các sách trong thư viện và 1 ds khoảng 30 nhà sản xuất. Tính số sách trong thư viện của mỗi nhà sản xuất.
Bài 3: Cho ma trận A mxn, trong đó có các phần tử trên từng cột - hàng đã được sắp xếp không giảm. Cho giá trị x, xác định có hay không 1 phần tử của A bằng x. Đánh giá số phép so sánh phải thực hiện.

Hi, làm ơn cho em xin cái đề chính xác của thầy cái!

Admin:Hi. Em gặp Thầy Tĩnh nha.

Đây là 3 bài tập Thầy ra:

Đề thầy ra đã viết:
Bài 1: Có 1000 phiếu thu tiền điện thoại và 999 biên lai thu tiền (trong đó có ghi sđt của thuê bao). Hãy xác định thuê bao nào chưa trả tiền.

Theo tôi hướng giải quyết bài toán dạng này là đưa biên lai thu tiền vào cấu trúc cây tìm kiếm lấy index là trường số điện thoại. Việc dò tìm từ phiếu thu sẽ chỉ thực hiện dò tìm theo cây, nên công việc cũng giảm đáng kể. Vấn đề là ở chỗ, nên chọn cấu trúc cây tìm kiếm sao cho tối ưu. Ví dụ cây nhị phân tìm kiếm và cây thập phân tìm kiếm, hoặc cây gia phả, hoặc một cây nào đó bất kỳ... cây nào tối ưu hơn thì phải đánh giá.

Đề thầy ra đã viết:Bài 2: Cho 1 ds gồm tên sách, tác giả, số đt, nhà sản xuất tất cả các sách trong thư viện và 1 ds khoảng 30 nhà sản xuất. Tính số sách trong thư viện của mỗi nhà sản xuất.

Hướng giải quyết bài này cũng tương tự trên, đưa vào cấu trúc cây thực hiện.

Đề thầy ra đã viết:Bài 3: Cho ma trận A mxn, trong đó có các phần tử trên từng cột - hàng đã được sắp xếp không giảm. Cho giá trị x, xác định có hay không 1 phần tử của A bằng x. Đánh giá số phép so sánh phải thực hiện.

Bài này hình như tương tự trong [You must be registered and logged in to see this link.]

code đại khái như vầy:

Phần xem xét tiếp đề nghị các nhóm thảo luận tại đây và cho phương án để đưa ra giải pháp tối ưu.

2 bài đầu dùng cấu trúc cây đúng rồi.

theo tôi dùng cấu trúc cây NPTK.

Bài 1:

- Gọi DS1 là tập hoá đơn, DS2 là tập biên lai thu tiền. DS1 có 1000 phần tử, mỗi phần tử mang thông số so dien thoai, DS2 co 999 phan tu, moi phan tu mang thong so so dien thoai. Giua 2 danh sach nay con co moi lien he do la cu 1 phan tu trong DS2 co cung so seri voi mot phan tu trong DS1.

- Ta dua thong so seri cua DS1 vao mot cau truc cay nhi phan tim kiem.Moi nut tren cay co cac tham so ve seri, so dien thoai. Ve cay nay len giay.

- Sau do ung voi moi phan tu cua DS2 duyet theo cay nhi phan tim kiem theo thong so seri. Voi moi nut duyet duoc ta danh dau vao. Cuoi cung nut nao chua duoc danh dau tren cay NPTK thi so dien thoai tuong ung la thue bao chua tra tien.

- Nhan xet: theo           nay ta co the tim duoc nhieu so thue bao chua tra tien cung mot luc.

Bai 2:

Đánh số danh sách nhà xuat ban tu 1 den 30.

Theo danh sach nay, dua vao cay nhi phan tim kiem theo           danh so. Moi nut co du lieu la chi so = 0, so, nha xuat ban.

Duyet tat ca sach cua thu vien theo cay NPTK. su trung giua sach va nut tren cay theo thong so nha xuat ban thi tang chi so nut len 1.

Cuoi cung la cac chi so tuong ung so sach nha xuat ban co trong thu vien.

Bài 1: Theo tôi dùng cây thập phân tìm kiếm để làm:
- Nút gốc: Số 0, các nút là 0,1,...,9
- Nút lá cấp 1: chỉ đi theo đường số 1,9 (số điện thoại như thế)
- Các mức tiếp theo sẽ là các số từ 0, 1,2 ->9
Như thế thì sau mỗi lần rẽ nhánh ta đã vô tình loại được khá nhiều số điện thoại khác rồi.
Bước 1: Để tạo cây ta duyệt lần lượt các số điện thoại và đưa vào cây thập phân
Bước 2: Lần lượt với từng hóa đơn dùng cây thập phân để tìm kiếm số điện thoại tương ứng, khi tìm được ta đánh dấu hoặc xóa khỏi cây. Còn lại số nào trên cây hoặc số nào không được đánh dấu tức là số đó chưa thanh toán tiền.
Chú ý: Ở nút lá cấp 1 ta chỉ đi theo 2 nhánh là 1 hoặc 9, 8 nhánh còn lại sẽ được bỏ qua, tôi thêm vào cho đúng đây là 1 cây thập phân.

Bài 2: Theo tôi dùng cây nhị phần tìm kiếm là hợp lý.

Bài 3: Theo tôi ta dùng thuật toán sắp xếp hòa nhập các mảng không giảm từ các hàng của ma trận tạo thành mảng không giảm, sau đó dùng kỹ thuật phân đoạn để tìm kiếm phần tử x.

Admin: Mọi người nêu các quan điểm của mình để trao đổi nhé.

sinhmd đã viết:Bài 1: Theo tôi dùng cây thập phân tìm kiếm để làm:
- Nút gốc: Số 0, các nút là 0,1,...,9
- Nút lá cấp 1: chỉ đi theo đường số 1,9 (số điện thoại như thế)
- Các mức tiếp theo sẽ là các số từ 0, 1,2 ->9
Như thế thì sau mỗi lần rẽ nhánh ta đã vô tình loại được khá nhiều số điện thoại khác rồi.
Bước 1: Để tạo cây ta duyệt lần lượt các số điện thoại và đưa vào cây thập phân
Bước 2: Lần lượt với từng hóa đơn dùng cây thập phân để tìm kiếm số điện thoại tương ứng, khi tìm được ta đánh dấu hoặc xóa khỏi cây. Còn lại số nào trên cây hoặc số nào không được đánh dấu tức là số đó chưa thanh toán tiền.
Chú ý: Ở nút lá cấp 1 ta chỉ đi theo 2 nhánh là 1 hoặc 9, 8 nhánh còn lại sẽ được bỏ qua, tôi thêm vào cho đúng đây là 1 cây thập phân.

Theo bác là nút gốc là "0", tiếp theo nút lá cấp 1 là "9" và "1", nút lá cấp 2 gồm 10 số "0">>"9". Vậy đến nút lá cấp 9 nó có biết bao nhiêu lá trên cây (tăng theo hàm mũ).
Em nghĩ nên lưu trữ dạng cây nhị phân tìm kiếm (danh sách liên kết). Mỗi nút ngoài Left, Right thì có 2 trường là Số tiền và Số thuê bao. Sắp xếp theo Số tiền (khi tìm được trùng tiền sẽ so sánh số thuê bao).

trungttnd đã viết:
Theo bác là nút gốc là "0", tiếp theo nút lá cấp 1 là "9" và "1", nút lá cấp 2 gồm 10 số "0">>"9". Vậy đến nút lá cấp 9 nó có biết bao nhiêu lá trên cây (tăng theo hàm mũ).
Em nghĩ nên lưu trữ dạng cây nhị phân tìm kiếm (danh sách liên kết). Mỗi nút ngoài Left, Right thì có 2 trường là Số tiền và Số thuê bao. Sắp xếp theo Số tiền (khi tìm được trùng tiền sẽ so sánh số thuê bao).

Ở đây tạo cây bằng cách chèn từng số điện thoại vào cây. Mỗi con số điện thoại sẽ quyết định rẽ nhánh đi theo hướng nào. Vậy có 999 số điện thoại của phiếu thu tức là có 999 chiếc lá.
Khi kiểm tra bằng cách kiểm tra từng số điện thoại ở hoá đơn đều đi theo từng nhánh, nếu chiếc lá nào không có tức là không tìm thấy phiếu (dừng luôn và thông báo). Còn nếu tìm thấy thì xoá bỏ chiếc lá đó để vòng lặp sau không phải tìm vào đó nữa (giảm dần việc tìm).

Để thầy ra khó thật nghĩ mãi mà chưa có cách giải quyết! Bác nào có cách gì hay thì share cho anh em đi [You must be registered and logged in to see this image.]

Các bác hiểu sai ý của thầy rồi, đây là 1 bài toán ngoài thực tế, không ai nhập vào máy rồi mới kiểm tra cả, vì vậy ý của thầy ở đây là giải quyết thủ công bằng tay như thế nào

Cả nhà cho nhận xét bài 1 của tôi nhé
Bài 1: Có 1000 phiếu thu tiền điện thoại và 999 biên lai thu tiền (trong đó có ghi số điện thoại của thuê bao). Hãy xác định thuê bao nào chưa trả tiền.

Bài làm:
Input:
- Tập phiếu thu tiền điện thoại (1000 phiếu thu)
- Tập biên lai thu tiền (999 biên lai)
Xử lý:
Ta quy ước số điện thoại là x1x2x3x4x5x6x7x8x9x10x11
với x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11 = 0,9
nếu số điện thoại có 10 chữ số thì ta thêm số 0 vào đầu
Bước 0:
- i = 12 // vị trí của chữ số trong điện thoại
- j = 0 // giá trị của chữ số trong điện thoại; j = 0, 9
Bước 1:
- i = i -1;
- Chia phiếu thu tiền thành các tập phiếu sao cho mỗi phiếu có xi cùng giá trị j (j = 0, 9)
- Chia biên lai thu tiền thành các tập biên lai sao cho mỗi biên lai có xi cùng giá trị j (j = 0, 9)
Bước 2:
- Đếm số phiếu thu tiền và số biên lai thu tiền của từng tập với giá trị j tương ứng
- Khi gặp tập phiếu thu tiền có số lượng khác với số lượng tập biên lai thu tiền thì kết thúc việc đếm và:
o Nếu số lượng biên lai thu tiền bằng 1, số lượng phiếu thu bằng 0: chuyển sang bước 4
o Nếu i =1: chuyển sang bước 3
o Còn lại: quay lại bước 1 với biên lai và phiếu thu tiền có xi = j
Bước 3: Loại bỏ những biên lai và phiếu thu tiền có số điện thoại trùng nhau
Bước 4: Kết thúc
Output: Thuê bao chưa trả tiền

Đây là tài liệu của thầy gửi cho lớp.
Bạn nào chưa có có thể download tại:
[You must be registered and logged in to see this link.]

Mọi người nghiên cứu tài liệu và làm bài tập thầy giao (23/11/2011)trong ebook: AlgorithmsAndComplexity.PDF, phần chương 3.

anh ơi làm ơn phích lại cho em cái link với, cảm ơn nhiều