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ý.
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: chuỗi con lớn nhất

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

    Mặc định chuỗi con lớn nhất

    mình đã dò thử nhưng không biết sai chỗ nào strncpy or for. các bạn xem giúp
    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    
    char * nhap(char * &s){
    	printf("nhap chuoi: ");
    	gets(s);
    	return s;
    }
    
    void main(){
    	clrscr();
    	printf("xet chuoi con lon I of s1 va s2,leng s1>leng s2");
    	char *s1,*s2,*s3,*s4,*s5;
    	nhap(s1);
    	nhap(s2);
    	s4="";
    	for(int i=0;i<strlen(s2)-1;i++)
    	{
    		strcpy(s3,s2+i);
    		int j=strlen(s3);
    		while (j>0)
    		{	strncpy(s4,s3,j);
    			j--;
    			if (strstr(s1,s4)!=NULL)
    				if (strlen(s5)<strlen(s4))
    					s5=s4;
    		}
    	}
    	printf("chuoi con lon nhat la %s",s5);
    	getch();
    }
    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
    09 2006
    Bài viết
    7

    bạn có thể nói rõ ý bạn muốn được không
    cho một vài ví dụ nữa chứ mình chưa hiểu ý của chương trình lắm

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bạn có thể giải thích chuỗi con lớn nhất là chuỗi con thế nào trong 2 chuỗi không? Bạn có thể cho 1 ví dụ không? Mình đọc code mà chẳng hiểu bạn đang làm gì nữa thì làm sao giúp bạn được :(?

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

    Xin lỗi nhé, mình quên
    Chương trình yêu cầu nhập 2 chuỗi s1 và s2, s1>s2
    tìm chuỗi con nhỏ nhất
    Ví dụ nhé:
    s1= abcdefg
    s2=kbcdl
    => chuỗi con lớn nhất là bcd
    Các bạn check lại giùm mình nhé. Không biết sai chỗ nào. Thanks

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Xin lỗi nhé, mình quên
    Chương trình yêu cầu nhập 2 chuỗi s1 và s2, s1>s2
    tìm chuỗi con nhỏ nhất
    Ví dụ nhé:
    s1= abcdefg
    s2=kbcdl
    => chuỗi con lớn nhất là bcd
    Hic, mình sợ bạn luôn !!!
    Mà chuỗi con được định nghĩa thế nào là lớn nhất ? ( hoặc nhỏ nhất )
    Là chuỗi con lớn hơn cả 2 chuỗi trên hay....?
    Hay là chuỗi con chung ?
    s1>s2
    DK này có là sao nhỉ ? Trong khi trong code bạn lại ghi :
    printf("xet chuoi con lon I of s1 va s2,leng s1>leng s2");
    !!!!!!
    Nếu ví dụ như trên thì mình nói vậy được không ?
    abc > bcd ?
    Sorry mình hơi chậm hiểu, nhưng bạn ghi ra rõ 1 tí được không ?

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

    Mặc định chuỗi con lớn nhất

    chuỗi con là chuỗi chung của cả 2 chuổi s1 và s2, mình viết tắt s2<s1 thực ra chiều dài chuỗi s2< chiều dài chuỗi s1. Còn dòng đó chỉ là nhắc lại đề thôi không liên quan đến bài toán.
    bạn không thể nói abc>bcd vì abc không là chuỗi con của s1 và s2. Nếu nói chuỗi con thì còn nhiều chuỗi con khác trong ví dụ trên như bc, cd, b, c. nhưng chuỗi con lớn nhất là bcd/

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

    xin nói thêm. Mình đã dùng watch để dò lỗi thử và thấy là hàm
    Code:
    strncpy(s4,s3,j);
    thực hiện không đúng dù j vẫn lặp chính xác. Cũng có thể là do lỗi vùng nhớ mà mình không xác định được.
    Mình cho chạy bộ thử
    s1=abcdef
    s2=mbcdk
    thì kết quả ra dk hoặc kí tự đặc biệt.

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Ý tưởng của bạn thì mình có đọc sơ qua nhưng hình như thấy vẫn chưa đủ ! Bài này nếu đúng phải là tìm chuỗi con chung dài nhất của 2 chuỗi thì có lẽ đúng hơn . Và ý tưởng của nó sẽ là dùng Quy Hoạch Đông. Và nếu tìm được dãy con chung rồi thì việc tìm dãy con lớn nhất trong dãy đó là mình nghĩ có thể thực hiện được ! Bạn suy nghĩ về ý tưởng nào thử xem. Mình sẽ làm thử xem sao ! Thân !

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

    ờ đây mình dùng vét cạn. Đúng như bạn nói chính xác đây là chương trình tìm chuỗi con dài nhất. Mình đã thử thay đổi một số chi tiết trong chương trình nhưng vẫn chưa đạt được mục đích. Mong câu trả lời. Thanks

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này nếu giải bằng Quy Hoạch Động thì như sau :
    Gọi Grid[i][j] là dãy độ dài dãy con chung dài nhất của 2 dãy X[] và Y[], công thức truy hồi đơn giản như sau :
    if ( X[i] == Y[j] )
    {
    Grid[i][j] = Grid[i-1][j-1] + 1;
    }
    else
    {
    Grid[i][j] = GetMax(Grid[i][j-1], Grid[i-1][j]);
    }
    PHP Code:
    #include <iostream>
    #include <string>
    #include <algorithm> //swap function

    using namespace std;

    const 
    int size 100;

    char X_string[size], 
         
    Y_string[size],
         
    Y[size],
         
    X[size],
         
    subString[size];
         
    int Grid[size][size]; // Matrix Solution
    int xLyL// X length and Y length

    int GetMax(int aint b)
    {
        
    int tmp;
        if ( 
    tmp a;
        else         
    tmp b;
          
        return 
    tmp;
    }

    void Initialization()
    {
        for ( 
    int i 0<= xLi++)
        {
            
    Grid[i][0] = 0;
        }
        for ( 
    int j 0<= yLj++)
        {
            
    Grid[0][j] = 0;
        }
        
    X[0] = ' ';
        
    Y[0] = ' ';
        for ( 
    int i 1<= xLi++)
        {
            
    X[i] = X_string[i-1];
        }
        for ( 
    int i 1<= yLi++)
        {
            
    Y[i] = Y_string[i-1];
        }
    }

    void DynamicProgramming()
    {
        for (
    int i 1<= xLi++)
        {
            for (
    int j 1<= yLj++)
            {
                if ( 
    X[i] == Y[j] )
                {
                    
    Grid[i][j] = Grid[i-1][j-1] + 1;
                }
                else
                {
                    
    Grid[i][j] = GetMax(Grid[i][j-1], Grid[i-1][j]);
                }
            }
        }
    }

    void TraceString()
    {
        
    int xO xL,
            
    yO yL;
        
        
    int position 0;
            
        do
        {
            if ( 
    X[xO] == Y[yO] )
            {
                
    position++;
                
    subString[position] = X[xO];
                
    xO--; 
                
    yO--;
            }
            else
            {      
                if ( 
    Grid[xO][yO] == Grid[xO][yO-1] ) yO--;
                else                                  
    xO--;
            }
        }
        while ( 
    xO && yO );
        
        for (
    int i 1<= position/2i++)
        {
            
    swap(subString[i], subString[position-i+1]);
        }
    }
    void PrintString()
    {
        
    cout << "\n------------------------\n";
        
    cout << "\nThe maximum length is : \n" << Grid[xL][yL];
        
    cout << "\n\n";
        
    cout << "Longest common substring is : " << endl;
        for ( 
    int i 0<= Grid[xL][yL]; i++)
        {
            
    cout << subString[i];
        }
        
    }    
    int main()
    {
        
    cout << "Enter 1-st String : " << endl;
        
    cin >> X_string;
        
    cout << "Enter 2-nd String : " << endl;
        
    cin >> Y_string;
        
        
    xL strlen(X_string);
        
    yL strlen(Y_string);

       
        
    Initialization();
        
    DynamicProgramming();
        
    TraceString();
        
    PrintString();
        
        return 
    0;

    Nếu bạn có chỗ nào không hiểu thì mình sẽ giải thích ! Thân !
    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ý.

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

  1. Lập trình C++ Lệnh cin.getline() không thể nhập chuỗi kế tiếp khi trước đó đã nhập 1 chuỗi vượt quá số kí tự tối đa khi khai báo
    Gửi bởi alonesnail025 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-06-2013, 11:34 AM
  2. Bài tập C++ Cách để so sánh 2 chuỗi kí tự giữa chuỗi nhập từ phím và chuỗi từ file xem có giống nhau không?
    Gửi bởi davilson18 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 09-06-2012, 09:47 AM
  3. Trả lời: 0
    Bài viết cuối: 13-05-2012, 10:51 AM
  4. Trả lời: 1
    Bài viết cuối: 29-06-2011, 12:02 AM
  5. Kỹ thuật C++ Các quy tắc nhập chuỗi trong C++, làm thế nào để nhập chuỗi có khoảng trắng?
    Gửi bởi quyen1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 20-11-2010, 03:36 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