Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải

    Bài 1: Dạo chơi bằng xe buýt
    Trên một tuyến đường ở thành phố du lịch nổi tiếng X có ô tô buýt công cộng phục vụ việc đi lại của du khách. Bến xe buýt có ở từng km của tuyến đường. Mỗi lần đi qua bến xe đều đỗ lại cho khách lên xuống. Mỗi bến đều có xe xuất phát từ nó, nhưng mỗi xe chỉ chạy không quá b km kể từ bến xuất phát của nó. Hành khách khi đi xe sẽ phải trả tiền cho độ dài đoạn đường mà họ ngồi trên xe. Cước phí cần trả để đi đoạn đường có độ dài i là ci (i=1...b) Một du khách muốn đi dạo L km trên tuyến đường nói trên. Hỏi ông ta phải lên xuống xe như thế nào để tổng số tiền phải trả cho chuyến dạo chơi bằng xe buýt là nhỏ nhất ?
    Dữ liệu: Vào từ file văn bản Bus.inp
    * Dòng đầu tiên chứa hai số nguyên dương b, L (b<=20, L<=200);
    * Dòng thứ hai chứ b số nguyên dương c1, c2... cb được ghi cách nhau bởi ít nhất một kí tự trắng.
    Kêt quả: Ghi ra file văn bản Bus.out
    * Dòng đầu tiên ghi chi phí tìm được
    * Dòng thứ hai ghi số lần lên xuống xe k
    * Dòng tiếp theo ghi k số là độ đài đoạn đường của k lần ngồi xe.
    Ví dụ:
    Bus.INP
    10 15
    12 21 31 40 49 58 68 79 90 101
    Bus.OUT
    147
    3
    3 6 6

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Hướng dẫn giải thuật cho Bài 1:
    Bài này có thể giải quyết bằng phương pháp quy hoạch động.
    Gọi f(i) là số tiền ít nhất phải dùng khi cần đi quãng đường i (km)
    Rõ ràng f(0)=0;
    f(1)=chiphi(1) (Số tiền để xe đi 1 km)
    Với 2<=i<= L Thì
    f(i)= MIN(f(i-j)+chiphi(j)) với 1<=j<=b và j<=i
    Và f(L) chính là chi phí nhỏ nhất cần dùng khi cần đi đoạn đường độ dài L.

    Chắc nhiều bạn còn lạ lẫm với cách giải quy hoạch động, nên mình sẽ giải thích cụ thể hơn như sau.
    Thay vì giải quyết bài toán tìm chi phí nhỏ nhất khi cần đi L đoạn đường, ta sẽ giải quyết L bài toán nhỏ hơn: Tìm chi phí nhỏ nhất khi cần đi 1, 2, 3.... L (km)
    rồi từ đó phối hợp lại để giải bài toán ban đầu.
    Lời giải Các bài toán con trên nhận được từ các lởi giải trước đó theo công thức quy hoạch động ở trên.
    Nói theo ngôn ngữ tự nhiên, khi cần tính toán xem chi phí nhỏ nhất khi cần đi i km là bao nhiêu ta sẽ đặt ra các giả thiết, tại lúc trước đó ta đã xuất phát từ đâu, và với vị trí xuất phát đó ta sẽ có được chi phí tương ứng để có mặt ở vị trí hiện tại. Chi phí nhỏ nhất chính là MIN của các giá trị trên.
    Khi cài đặt, ta xây dựng một mảng Int f[Maxl] để lưu giữ kết quả các bài toán con
    Việc tìm lời giải các bài toán con có thể mô tả như sau:
    PHP Code:
     f[0]:= 0;
        
    f[1]:= c[1];
        For 
    i:=2 To L Do
          
    Begin
            Min
    := Maxint;
            For 
    j:=1 To b Do
             If 
    i>= j Then
              
    If f[i-j] + c[j]< Min Then
                 Begin
                   Min
    := f[i-j] + c[j];
                 
    End;
            
    f[i]:= Min;
          
    End;
      
    End
    Lời giản của bài toán khi đó sẽ là F[L]

  3. #3
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Bài 2:
    Mạng máy tính
    Tổng công ty Meka có N máy tính được đánh số từ 1 đến N. Người ta đã lắp đặt được M kênh trực tiếp truyền tin giữa một số máy tính. Hai máy tính u và v trong Tổng công ty được coi là có thể truyền tin được cho nhau nếu chúng được nối với nhau bằng một kênh nối trực tiếp hoặc tồn tại một dãy các máy tính u = m0, m1, …, mk = v sao cho giữa 2 máy tính m(i-1) và mi bất kì (i=1..k) đều có ít nhất một kênh nối trực tiếp. Nhằm triển khai thực hiện chủ trương cải cách hành chính theo tinh thần Chỉ thị 58 của Bộ Chính trị, Ban Giám đốc đã cho triển khai dự án hoàn thiện mạng máy tính để nâng cao hiệu quả hoạt động của Tổng công ty.

    Yêu cầu: Hãy giúp Ban Giám đốc xác định số lượng ít nhất kênh trực tiếp truyền tin cần lắp đặt thêm, sao cho 2 máy tính bất kì trong Tổng công ty có thể truyền tin cho nhau.

    Dữ liệu: Vào từ file văn bản COMNET.INP trong đó:
    - Dòng đầu tiên chứa hai số nguyên dương N, M (0 <= N <= 5000; M <= 200000)
    - M dòng tiếp theo chứa thông tin về M kênh truyền tin đã được lắp đặt: Mỗi dòng chứa hai số nguyên dương xác định hai máy tính được nối bởi kênh thông tin đã lắp đặt.

    Kết quả: Ghi ra file văn bản COMNET.OUT trong đó:
    - Dòng đầu tiên ghi số K là số lượng kênh cần lắp đặt thêm.
    - K dòng tiếp theo mô tả thông tin về K kênh truyền tin đã được lắp đặt: Mỗi dòng chứa hai số nguyên xác định hai máy tính cần lắp đặt thêm đường nối.

    Trong trường hợp có nhiều hơn 1 cách nối, chỉ cần đưa ra 1 cách bất kì.

    Ví dụ:COMNET.INP
    8 6
    1 2
    3 1
    3 4
    4 1
    5 6
    7 8
    COMNET.OUT
    2
    1 5
    1 7

    Nguồn đề: Kì thi học sinh giỏi quốc gia năm 2003.

    Gợi ý: Bài này nói chung không khó lắm, các bạn đưa về tìm các thành phần liên thông của đồ thị, các cung cần nối thêm chính là các cung nối các thành phần liên thông này với nhau. Vấn đề là xử lý bài toán với số cạnh lớn.

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Lâu lâu em mới lại có thời gian vào diễn đàn được. Mấy hôm vừa rồi em tìm được một trang cho phép giải đề trên mạng http://acm.timus.ru/ bài tập của nó nhiều và khá hay lại cho phép giải bằng nhiều ngôn ngữ (Pascal, C, Java) rất tiện. Hôm nay em xin post lên một đề trong đó: bài này không khó (em nói thật đấy), chỉ khó cái nó bằng tiếng Anh, đọc hiểu rồi thì nghĩ chút là ra thôi.
    (đây là đề 1409 link: http://acm.timus.ru/problem.aspx?space=1&num=1409)
    Two Gangsters
    Time Limit: 1.0 second
    Memory Limit: 16 MB

    Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can.

    Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot.

    Determine how many cans were not shot by Harry and how many cans were not shot by Larry.
    Input

    The only input line contains two integers — the number of cans shot by Harry and by Larry respectively.
    Output

    two integers — the number of cans that were not shot by Harry and the number of cans that were not shot by Larry, respectively.
    Sample Input

    4 7

    Sample Output

    6 3


    Chú ý: Trước khi làm bài nên đọc FAQ của trang đó để xem cách thức vào ra, các mở rộng về bộ nhớ...
    Để vào, ra dữ liệu ta cứ dùng scanf, printf bình thường, phần chấm sẽ tự điền dữ liệu vào cho ta.
    Sau khi viết xong chương trình để kiểm tra kết quả, vào trang đề của nó (đã đưa link trên) nhấn nút submit, mục JUIDGE_ID nhập 46907LJ (đây là id của em, các bác có thể lập ID khác).

  5. #5
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Những bài toán này rất hay, nó giúp cho mình phải suy nghĩ nhiều nhưng trên thực tế là những dạng toán này đã có các giải thuật cụ thể rồi. Mấy kỳ thi học sinh giỏi toàn lấy mấy cái bài này, sửa số lại là có ngay 1 cái đề thi mới, năm nào cũng vậy riết rồi nhàm. Mình nghĩ nên đặt ra những bài toán có yêu cầu từ thực tế và kỹ thuật cũng khó khăn phức tạp, có thể bài toán phải cần đến 1 nhóm giải quyết mới được, khi đó mình có thể phát triển tư duy logic lập trình mà cũng có thể phát triển cách làm việc nhóm nhiều hơn. Ở VN toàn học solo, đi thi cũng solo, thi học sinh giỏi cũng solo, chưa thấy có 1 cái gì gọi là làm việc theo nhóm trong khi mọi người lại bảo làm việc nhóm tốt hơn, giúp mỗi người phát triển theo chuyên ngành mình nhiều hơn. Vậy chúng ta hãy thử sức với cách làm việc nhóm để thử xem nó là thế nào.

  6. #6
    Ngày gia nhập
    03 2009
    Bài viết
    5

    Mặc định [Lý thuyết giải thuật] Một số bài tập về giải thuật và cách giải

    Hay quá các bác post tiếp lên để bọn em mở rộng tầm mắt

  7. #7
    Ngày gia nhập
    01 2010
    Bài viết
    1

    BẠn ơi, bạn post luôn giải thuật háo ăn và vét cạn để giải bài toán người giao hàng luôn nha bạn. Mình hi vọng bạn sẽ là người giúp mình

Các đề tài tương tự

  1. Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 24-02-2015, 05:21 PM
  2. Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 31
    Bài viết cuối: 30-01-2015, 10:41 PM
  3. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  4. Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 28
    Bài viết cuối: 15-05-2013, 11:10 AM
  5. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn