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

Đề tài: Dãy con chung dài nhất

  1. #1
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    705

    Mặc định Dãy con chung dài nhất

    Chào các bạn mình có 1 vấn đề mong mọi người giải đáp giúp:
    "Cho 2 xâu X=<X1X2....Xm> và xâu Y=<Y1Y2....Yn> .1 dãy con chung của X và Y là xâu có được bằng cách xoá bớt 1 số phần tử của X và của Y,
    Yêu cầu liệt kê ra tất cả các dãy con chung dài nhất.
    Vấn đề tìm độ dài xâu con chung dài nhất thì mình đã giải quyết xong bằng thuật toán quy hoạch động(cái này có nhiều trong các sách về thuật toán) ,nhưng mình gặp khúc mắc ở chỗ in ra mọi dãy con chung lớn nhất của bài toán có nhiều đáp án

    vd :X=”a45y7i9”
    Y=”y475f90A!” thì dáp án là 459 và y79

    Cho mình hỏi thêm các bạn có địa chỉ nào có thể giúp mình down những bộ file test(bao gồm cả input và output) cho những bài toán phổ biến trong tin học như “đường đi ngắn nhất trong đồ thị",”knapsack”,”bài toán người du lịch” ,”bài toán cây khung”,”dãy con tăng dài nhất”,”giao và hợp của n đoạn cho trước”...
    ý mình là cần những test rất lớn để kiểm tra tính đúng đắn của những thuật toán mình đã cài.

    Rất mong nhận được hồi âm của các bạn.

  2. #2
    Ngày gia nhập
    10 2007
    Bài viết
    32

    Trích dẫn Nguyên bản được gửi bởi tanglung117 Xem bài viết
    Chào các bạn mình có 1 vấn đề mong mọi người giải đáp giúp:
    "Cho 2 xâu X=<X1X2....Xm> và xâu Y=<Y1Y2....Yn> .1 dãy con chung của X và Y là xâu có được bằng cách xoá bớt 1 số phần tử của X và của Y,
    vd :X=”a45y7i9”
    Y=”y475f90A!” thì dáp án là 459 và y79
    Chào bạn, mình chưa hiểu tại sao đáp án là 459 và y79 được không(hic, mình hơi chuối). Bạn có thể nói rõ thêm về dãy con chung được không. Định nghĩa và ví dụ của bạn hơi khó hiểu. Sao đáp án lại không là 45y79 nhỉ.
    Ý quên mới search lại trên forum có một topic nói về cái này nè
    http://forums.congdongcviet.com/arch...hp/t-4277.html
    Have fun!
    Đã được chỉnh sửa lần cuối bởi fedo : 13-04-2008 lúc 06:51 PM.

  3. #3
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    705

    Dãy con của 1 dãy thì yêu cầu thứ tự các phần tử phải giữ nguyên ,trong ví dụ của mình do kí tự "y" đứng trước kí tự "5" nên đáp án của bạn không được.
    cái định nghĩa của mình đưa ra là khá chuẩn do mình theo các sách rồi đấy.
    nhưng trong sách họ chưa giải quyết được vấn đề là "liệt kê mọi dãy con chung dài nhất".cái topic của bạn "rox_rook" đã đưa ra giải thuật đúng nhưng vẫn chưa giải quyết được vấn đề trên,vả lại mình cũng chưa ngâm cứu về C++ cho nên code của rox_rook mình không hiểu cho lắm nhưng về tư tưởng là đúng rồi.

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

  1. Mã nguồn C Lỗi Ước chung lớn nhất, bội chung nhỏ nhất chạy với dữ liệu lớn bị sai kết quả là do đâu?
    Gửi bởi vanquocktcn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 27-11-2012, 04:19 PM
  2. Chung Cư Ngô Thì Nhậm, bán CT2 tầng10,DT:128.58m2 Chung Cư Ngô Thì Nhậm
    Gửi bởi datphat191 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 27-12-2011, 01:09 PM
  3. Chung cư Ngô Thì Nhậm, bán chỉ 20tr Chung cư Ngô Thì Nhậm 128m
    Gửi bởi datphat191 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 14-12-2011, 01:49 PM
  4. Chung cư ngô thị nhậm CT2,căn hộ ngô thị nhậm ,chung cu ngo thi nham
    Gửi bởi ephat_tt86 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 30-11-2011, 11:08 AM
  5. @Chung cư ngô thị nhậm CT2,căn hộ ngô thị nhậm ,chung cu ngo thi nham
    Gửi bởi ephat_tt86 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 17-11-2011, 04:35 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