Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: mọi người ơi code giúp em bài này với ạ

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

    Mặc định mọi người ơi code giúp em bài này với ạ

    Xâu ký tự S gọi là xâu con của xâu ký tự T nếu có thể xoá bớt một số ký tự trong xâu T để
    được xâu S. Lập chương trình nhập vào hai xâu ký tự X, Y. Tìm xâu Z có độ dài lớn nhất là
    xâu con của cả X và Y. Ví dụ: X = 'abcdefghi123'; Y = 'abc1def2ghi3' thì Z là 'abcdefghi3'.
    có thể sử dụng các hàm đơn giản được không ạ
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    02 2016
    Bài viết
    306

    Giải thuật:
    duyệt từng ký tự của X
    duyệt Y kể từ ký tự đã tìm được lần trước đó
    nếu gặp đúng ký tự thì cóp vào Z

    // string X, Y, Z
    char *pX = X-1, *pY = Y-1, *pZ = Z;
    char *lastMatch = pY;
    while (*++pX) // not the end of X
    {
    pY = lastMatch;
    while (*++pY) // not the end of Y
    if (*pX == *pY)
    {
    *pZ++ = *pX; // match found, copy to Z
    lastMatch = pY;
    break;
    }
    }
    *pZ = '\0'; // mark the end of Z

  3. #3
    Ngày gia nhập
    08 2017
    Bài viết
    3,549

    longest common subsequence
    + interface
    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

    + implementation

  4. #4
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    483

    Trích dẫn Nguyên bản được gửi bởi NguNhuheo Xem bài viết
    Giải thuật:
    duyệt từng ký tự của X
    duyệt Y kể từ ký tự đã tìm được lần trước đó
    nếu gặp đúng ký tự thì cóp vào Z

    // string X, Y, Z
    char *pX = X-1, *pY = Y-1, *pZ = Z;
    char *lastMatch = pY;
    while (*++pX) // not the end of X
    {
    pY = lastMatch;
    while (*++pY) // not the end of Y
    if (*pX == *pY)
    {
    *pZ++ = *pX; // match found, copy to Z
    lastMatch = pY;
    break;
    }
    }
    *pZ = '\0'; // mark the end of Z
    Mình sửa code bạn để có thể chạy được như sau
    C++ Code:
    1. #include <iostream>
    2. //#include <string>
    3. //#include <cstdio>
    4. using namespace std;
    5.  
    6. void lcs(char *X, char* Y, char* Z)
    7. {
    8.     char *pX, *pY;
    9.     char *pZ;
    10.     pX = X - 1;
    11.     pY = Y - 1;
    12.     pZ = Z;
    13.     char *lastMatch = pY;
    14.     while (*++pX) {// not the end of X
    15.         pY = lastMatch;
    16.         while (*++pY) {// not the end of Y
    17.             if (*pX == *pY) {
    18.                 *pZ++ = *pX; // match found, copy to Z
    19.                 lastMatch = pY;
    20.                 break;
    21.             }
    22.         }
    23.     }
    24.     *pZ = '\0'; // mark the end of Z
    25. }
    26. int main(int argc, char *argv[])
    27. {
    28.     char X[] = "apple";
    29.     char Y[] = "peach";
    30.     string x, y;
    31.     char Z[100];
    32.     lcs(X, Y, Z);
    33.     cout << X << " " << Y << " " << Z <<"\n";
    34.     lcs(Y, X, Z);
    35.     cout << Y << " " << X << " " << Z <<"\n";
    36. }
    37. /* Kết quả là
    38. apple peach a
    39. peach apple pe
    40.  
    41. [Program finished]
    42. */
    Kết quả là nếu thay đổi thứ tự đầu vào thì xâu con chung "dài nhất" cũng khác nhau
    Như vậy ta phải gọi lcs 2 lần rồi so sánh kết quả rồi lấy kết quả dài hơn
    Đã được chỉnh sửa lần cuối bởi khoaph : 22-05-2020 lúc 03:41 PM. Lý do: Thêm kết quả khi chạy

  5. #5
    Ngày gia nhập
    08 2017
    Bài viết
    3,549

    Đổi chỗ mà đúng, như chó ngáp phải ruồi, chỉ là may mắn.
    Chương trình sai vì dựa trên thuật toán sai.

    Thích thì thử với dữ liệu sau
    Code:
        char X[] = "ZBCDEFGHIJKLMNOPQRSTUVWXYA";
        char Y[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  6. #6
    Ngày gia nhập
    02 2016
    Bài viết
    306

    Mặc định mọi người ơi code giúp em bài này với ạ

    Phải rồi.
    Ở bài #2 chỉ tìm được 1 xâu con chứ không bảo đảm tìm được xâu dài nhất. Vì vậy có thể coi như sai.

  7. #7
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    483

    Trích dẫn Nguyên bản được gửi bởi Monre Xem bài viết
    Đổi chỗ mà đúng, như chó ngáp phải ruồi, chỉ là may mắn.
    Chương trình sai vì dựa trên thuật toán sai.

    Thích thì thử với dữ liệu sau
    Code:
        char X[] = "ZBCDEFGHIJKLMNOPQRSTUVWXYA";
        char Y[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    Đúng rồi.........
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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