Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    haihonglyk6

    haihonglyk6
    Chuyên viên
    Chuyên viên
    Đâ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.

    Marsge

    Marsge
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    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.

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Đâ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.

    https://khmt.123.st

    LeVanDat

    avatar
    Chuyên viên
    Chuyên viên
    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.

    sinhmd

    sinhmd
    Quản trị viên
    Quản trị viên
    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é.

    http://climategis.com/forum/

    trungttnd

    trungttnd
    Thành viên cao cấp
    Thành viên cao cấp
    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).

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    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).

    https://khmt.123.st

    xuandiencntt

    xuandiencntt
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Để 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.]

    hoangkim

    hoangkim
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    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

    dienht

    dienht
    Thành viên cao cấp
    Thành viên cao cấp
    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

    11[Lời giải]Bài tập Đánh giá thuật toán Thầy Tĩnh Empty Tài liệu Thầy Tĩnh gửi lớp Wed Nov 23, 2011 12:17 pm

    Cuong01111

    avatar
    Thành viên cao cấp
    Thành viên cao cấp
    Đâ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.

    hotline300

    hotline300
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    anh ơi làm ơn phích lại cho em cái link với, cảm ơn nhiều

    phạm huyền trang

    phạm huyền trang
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
     link hỏng, cảm ơn nhiều

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất