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

Đề tài: Bài tập lập trình "siêu mã"

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

    Mặc định Bài tập lập trình "siêu mã"

    Mình mới học C++ có một bài tập mình muốn nhờ các bạn cho mình ý tưởng để giải. Bài tập như sau :

    Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
    Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
    Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
    • Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
    • Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
    Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
    • Nếu X là siêu mã thì ghi số 1;
    • Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
    Ví dụ:
    HCODE.INP
    5
    1111
    100101
    01011
    000
    0001000
    HCODE.OUT
    0
    2

    HCODE.INP
    3
    010
    1000
    11
    HCODE.OUT
    1
    Đã được chỉnh sửa lần cuối bởi nnvn : 07-10-2007 lúc 06:45 PM. Lý do: viết sai vài chỗ trong ví dụ

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

    ka ka. Lại một bài luyện gà nữa nè.

    Tớ có ý kiến thế này cậu coi thử nhé. Mấu chốt là cậu so sánh 2 chuối xi bất kì thôi đúng không .

    Về chuyện này tớ có nhiều ý để có thể loại bỏ đi 1 cách sớm nhất tuy nhiên tớ thấy ko ổn lắm để về lại nghĩ tiếp. Cách cơ bản (và cũng là rất chuối) là cách này.

    Giả sử 2 dãy đưa vào lần lượt là x1[n] và x2[m] phần tử .

    Xét trường hợp n=m:
    + Không thỏa .
    Trường hợp n<m
    + Duyệt lần lượt các phần tử của n.
    + Tại phần tử thứ i, ta kiểm tra phần tử tiếp theo của x2 sao cho x2[j] =x1[i]
    + Nếu ta tìm được tất cả các phần tử thuộc x1 đều có thể tìm được phần tử tương ứng ( trái sang phải ) bên x2 thì đây là thằng cần tìm.

    Về cơ bản là như thế đã.

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    13

    Up lại cho một bài toán hay!
    Đầy là 1 bài toán trong đề thi OLYMPIC TIN HỌC SINH VIÊN LẦN 15, 2006.
    Em cũng đang định thi O-09, nên đang xem luyện lại, pác này cùng hướng đi thì pm làm quen, trao đổi học hỏi thêm nhé. Y!M: nhimsonic_89
    Muốn có thắng lợi, phải có hy sinh

  4. #4
    Ngày gia nhập
    09 2009
    Bài viết
    1

    Bài này hay quá Giờ em mới bít!
    Cứ ăn chơi cho hết thời trai trẻ
    Rồi âm thầm lặng lẽ đạp xích lô

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

    Trích dẫn Nguyên bản được gửi bởi nnvn Xem bài viết
    Mình mới học C++ có một bài tập mình muốn nhờ các bạn cho mình ý tưởng để giải. Bài tập như sau :

    Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
    Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
    Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
    • Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
    • Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
    Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
    • Nếu X là siêu mã thì ghi số 1;
    • Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
    Ví dụ:
    HCODE.INP
    5
    1111
    100101
    01011
    000
    0001000
    HCODE.OUT
    0
    2

    HCODE.INP
    3
    010
    1000
    11
    HCODE.OUT
    1
    Mình đọc tập tin trên vào biến FILE f, vào một mảng A kiểu char[15] gồm N phần tử. Đọc dữ liệu thì có thể dùng hàm fscanf hoặc fgets.
    Nhưng chỉ đọc được vào 1 biến kiểu char, chưa đọc vào mảng được, báo lỗi ko thể chuyển kiểu char sang char* gì đó, bạn nào test giúp mình với.
    Muốn có thắng lợi, phải có hy sinh

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

  1. nghĩa của 3 từ "principals", "artifacts", "securables" là như thế nào?
    Gửi bởi ntbao trong diễn đàn English for IT | Tiếng anh cho dân CNTT
    Trả lời: 2
    Bài viết cuối: 02-09-2017, 06:36 PM
  2. Lỗi"error C2275: 'T' : illegal use of this type as an expression" khi dùng "list<T>::iterator it"
    Gửi bởi doicanhden trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 6
    Bài viết cuối: 19-01-2012, 01:59 AM
  3. Trả lời: 1
    Bài viết cuối: 01-12-2011, 07:32 PM
  4. Problems : " recover tree " with input as " preorder" and "inorder"
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 10:19 PM
  5. Portable Cyberlink PowerCinema 6.0.3316 - Trình media "siêu khủng"
    Gửi bởi digiman87 trong diễn đàn Software (Phần mềm) | Ebooks
    Trả lời: 0
    Bài viết cuối: 09-02-2011, 08:50 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