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ố 19 kết quả

Đề tài: Tìm và hiện ra dãy con các số giống nhau liên tục dài nhất, làm thế nào?

  1. #1
    Ngày gia nhập
    05 2008
    Bài viết
    1

    Angry Tìm và hiện ra dãy con các số giống nhau liên tục dài nhất, làm thế nào?

    gợi ý giúp mình với, ngồi cả ngày rùi mà ko được.
    Đề bài : nhập mảng n số nguyên. Tìm và hiện ra dãy con các số giống nhau liên tục dài nhất, nếu có nhiều dãy côn như vậy thì chỉ cần hiện 1 dãy trong số đó.
    thanks các bạn trước nha!

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Mình giúp bạn 1 í. Chương trình này nhập một xâu và xuất 1 xâu con các kí tự giống nhau dài nhất. Công việc này lặp đi lặp lại đến khi nhập được xâu "." thì dừng.

    Code:
    #include<stdio.h>
    
    int len(const char c, const char*s) // how many first chars in s are same as c?
    {
        if( *s==0 ) return 0;
        if( *s!=c ) return 0;
        return 1+len(c,s+1);
    }
    
    int len(const char *s)  // how many first chars in s are the same?
    {
        if (*s==0) return 0;
        return 1+len(*s,s+1);
    }
    
    int len(const char *s, const char *& r) // length of the longest substring r of same chars in s
    {
        if( *s==0 )
        {
            r = s;
            return 0;
        }
        int k = len(s);
        int n = len(s+k, r);
        if (k > n)
        {
            r = s;
            return k;
        }
        else
        {
            return n;
        }
    }
    
    int main()
    {
        char s[200], format[100];
        const char *r;
        int m;
        for(;;)
        {
            printf("Nhap xau:");
            gets(s);
            if(*s == '.') break;
            m = len(s,r);
            sprintf(format,"Xau con dai nhat:%%%d.%ds\n\n",m,m);
            printf(format,r);
        }
        return 0;
    }
    Ví dụ

    Code:
    Nhap xau:1
    Xau con dai nhat:1
    
    Nhap xau:122
    Xau con dai nhat:22
    
    Nhap xau:122333
    Xau con dai nhat:333
    
    Nhap xau:1223331
    Xau con dai nhat:333
    
    Nhap xau:1564084006846468464898793
    Xau con dai nhat:00
    
    Nhap xau:aaa-bbb-ccc
    Xau con dai nhat:ccc
    
    Nhap xau:.

  3. #3
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Bài này mình có ý tưởng thế này: Đầu tiên bạn viết một hàm copy 1 phần mảng a[] từ vị trí k đến l. Tương tự như thế này:
    Code:
    void copymg(int a[], int m[], int k, int l);
    Với mảng m[] là phần mảng copy từ mảng a[], số phần tử của m[] là l - k + 1.

    Bây giờ duyệt mảng a[]. Nếu gặp một dãy các số giống nhau liên tiếp thì ghi nhớ vị trí bắt đầu k và kết thúc l của nó. Nếu độ dài của dãy là l - k + 1 > MAX (MAX là kích thước của dãy các số giống nhau liên tiếp trước đó, nếu chưa có dãy nào thì giá trị đầu của MAX = 1) thì copy phần mảng từ k đến l vào mảng m[]. Cuối cùng mảng m[] là mảng bạn cần phải in ra.

    Để duyệt mảng và xác định vị trí đầu cuối [k, l] của dãy các số giống nhau liên tiếp có thể làm như sau: Cho i chạy từ 1 đến N, nếu a[i] == a[i - 1]; thì gán l = i, k = l - max + 1 (max "nhỏ" là kích thước của dãy CSGN liên tiếp này, sau mổi lần thỏa dk a[i] == a[i - 1] thì max++, giá trị đầu của max = 1). Ngược lại nếu dk trên ko thỏa và nếu max > MAX thì copy nó vô mảng m[]. lúc này gán MAX = max; Xong rồi gán lại giá trị đầu cho max = 1. Lặp lại quá trình đến hết mảng a[].

    Code thử xem chạy có được không. Tui cũng mới chập chững học C, ai pro vô góp ý cái.
    Đã được chỉnh sửa lần cuối bởi Chautieu47 : 01-06-2008 lúc 08:53 PM.
    /* The thing that I think is the thing that I do. */

  4. #4
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Trích dẫn Nguyên bản được gửi bởi duclong Xem bài viết
    gợi ý giúp mình với, ngồi cả ngày rùi mà ko được.
    Đề bài : nhập mảng n số nguyên. Tìm và hiện ra dãy con các số giống nhau liên tục dài nhất, nếu có nhiều dãy côn như vậy thì chỉ cần hiện 1 dãy trong số đó.
    thanks các bạn trước nha!
    1. Bài viết của bạn vi phạm nội quy : tiêu đề ko hợp nội quy

    2. Châm trước trả lời bạn lần này. Lần sau đừng vi phạm nội quy nha:
    Có nhiều các làm khác nhau. Có thể tham khảo ý tưởng này :

    + Nhập mảng ......

    + tìm chiều dài của lớn nhất của các dãy con gán vào maxkt. // max kí tự

    PHP Code:
    maxkt=0// lúc đầu
    for (i=0;i<n;i++) 
     if  ( 
    mang[i]==mang[i+1] ) // nếu xuất hiện sự trùng lặp
         
    {
            
    k=i;
            while (
    mang[k]==mang[i]) k++;
            
    ddt=k-i;   // ddt độ dài temp ( độ dài của các đoạn con nhất thời )
            
    if (maxkt<ddtmaxkt=ddt;
         } 
    qua đoạn code này bạn có biết được doạn dài nhất của mảng nhập có "maxkt" kí tự

    + Duyệt lại mảng 1 lần nữa nếu đoạn con nào có độ dài == maxkt và in ra. (Nếu chỉ lấy 1 trường hợp thì break luôn sau khi in trường hợp 1)
    PHP Code:
    for (i=0;i<n;i++) 
     if  ( 
    mang[i]==mang[i+1] ) // nếu xuất hiện sự trùng lặp
         
    {
            
    k=i;
            while (
    mang[k]==mang[i]) k++;
            
    ddt=k-i;   // ddt độ dài temp ( độ dài của các đoạn con nhất thời )
            
    if (maxkt==ddt
                   {
                          
    // .... code để in dãy con này ra màn hình ....
                         // in mảng tại đoạn từ i đến k 
                        // ko code hộ đoạn này

                       // break;   //break nếu chỉ muốn in 1 dãy con
                   
    }
         } 
    3. @ada :
    PHP Code:
    Mình giúp bạn 1 íChương trình này nhập một xâu và xuất 1 xâu con các kí tự giống nhau dài nhấtCông việc này lặp đi lặp lại đến khi nhập được xâu "." thì dừng
    Về bản chất thì ko khác nhau đều tìm dãy con trong mảng có độ dài max.
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

  5. #5
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Hì! thử luyện cho lên tay nghề, bài của bạn mình đã code hoàn chỉnh, phần in đậm là những gì phía trên mình nói:
    Code:
    #include <stdio.h>
    #include <conio.h>
    void copymg(int a[], int m[], int k, int l)
    {
    	int j, i = k;
    	for(j = 0; j < l - k + 1; j++, i++)
    		m[j] = a[i];
    }
    void nhapm1d(int a[], int N)
    {
    	int i;
    	for(i = 0; i < N; i++)	{
    		printf("a[%d] = ", i); scanf("%d", &a[i]);
    	}
    }
    void xuatm1d(int a[], int N)
    {
    	int i;
    	for(i = 0; i < N; i++)	{
    		printf("%4d", a[i]);
    	}
    }
    void main()
    {
    	int N;
    	int a[50], m[50];
    	int i, MAX, max, k, l; 
    
    	printf("Nhap N: "); scanf("%d", &N);
    	nhapm1d(a, N);
    	for(i = 1, MAX = max = 1; i < N + 1; i++)	{
    		if(a[i - 1] == a[i])	{
    			max++; l = i; k = l - max + 1;
    		}
    		else	{
    			if(max > MAX)	{
    				MAX = max;
    				copymg(a, m, k, l);
    			}
    			max = 1;
    		}
    	}
    	if(MAX == 1)
    		printf("Khong co day thoa yeu cau");
    	else	{
    		printf("\nDay CSGN lien tiep dai nhat la:");
    		xuatm1d(m, MAX);
    	}
    	getch();
    }
    Đã được chỉnh sửa lần cuối bởi Chautieu47 : 01-06-2008 lúc 08:54 PM.
    /* The thing that I think is the thing that I do. */

  6. #6
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Wink Tìm và hiện ra dãy con các số giống nhau liên tục dài nhất, làm thế nào?

    Trích dẫn Nguyên bản được gửi bởi Chautieu47 Xem bài viết
    Hì! thử luyện cho lên tay nghề, bài của bạn mình đã code hoàn chỉnh, phần in đậm là những gì phía trên mình nói:
    Code:
    #include <stdio.h>
    #include <conio.h>
    void copymg(int a[], int m[], int k, int l)
    {
    	int j, i = k;
    	for(j = 0; j < l - k + 1; j++, i++)
    		m[j] = a[i];
    }
    void nhapm1d(int a[], int N)
    {
    	int i;
    	for(i = 0; i < N; i++)	{
    		printf("a[%d] = ", i); scanf("%d", &a[i]);
    	}
    }
    void xuatm1d(int a[], int N)
    {
    	int i;
    	for(i = 0; i < N; i++)	{
    		printf("%4d", a[i]);
    	}
    }
    void main()
    {
    	int N;
    	int a[50], m[50];
    	int i, MAX, max, k, l; 
    
    	printf("Nhap N: "); scanf("%d", &N);
    	nhapm1d(a, N);
    	for(i = 1, MAX = max = 1; i < N + 1; i++)	{
    		if(a[i - 1] == a[i])	{
    			max++; l = i; k = l - max + 1;
    		}
    		else	{
    			if(max > MAX)	{
    				MAX = max;
    				copymg(a, m, k, l);
    			}
    			max = 1;
    		}
    	}
    	if(MAX == 1)
    		printf("Khong co day thoa yeu cau");
    	else	{
    		printf("\nDay CSGN lien tiep dai nhat la:");
    		xuatm1d(m, MAX);
    	}
    	getch();
    }
    @ Chautieu47 : Bản chất bài này rất ngắn gọn chỉ trong vài dòng lệnh như mình trình bày. Làm như bạn mình chưa check nhưng sẽ vắc phải vài nhược điểm nhỏ sau :
    a. tốn bộ nhớ.
    Máy tính sẽ phải cấp pháp bộ nhớ ko cần thiết:
    + biến thừa :
    PHP Code:
    int a[50], m[50];
    int iMAXmaxkl
    với bài này ta ko cần đến 2 mảng ....

    có thể ngắn gọn với các biến như sau

    PHP Code:
    int mang[50],i,j,k,maxdt,ddt
    + vùng nhớ ko cần thiết cho các hàm :
    Bài bạn khai báo rất nhiều hàm, điều đó cô giáo luôn khuyến khích học sinh. ok!
    Tuy nhiên mình ngó hàm ko có tính "chuẩn mực" cao.
    Hàm nên là 1 module riêng biệt, có tác dụng hữu ích cụ thể, có tính đơn lẻ ( ko gắn liền với 1 bài cụ thể nào cả ).
    hàm của bạn đều ko sai với ý trên nhưng tác dụng thì chưa sâu sắc lắm.

    b. Không linh động
    Bạn đã mất đi tính linh động trong code. Đây là 1 bài đơn giản. Bạn đừng quá bài bản với vấn đề,bài này yêu cầu hoàn toàn rõ ràng, ngắn gọn.
    cách trình bày tốt nhất với bài này ta trình bày 1 cách mạch lạc từ trên xuống dưới có phân cách đoạn và trích dẫn. Như thế các bạn mới đọc có thể hiểu dễ dàng hơn.
    Dùng hàm , module hóa công việc là tốt, nhưng những vấn đề bạn đang tách ra thành các module nhỏ lại rất đơn giản, ko sâu sắc đặc biệt , trong bài này nó ko được xài nhiều lần... cũng ko phải 1 module có thể ứng dụng mạnh mẽ.


    ......


    @ góp ý nhỏ với bạn về coding conventions:




    PHP Code:
    void xuatm1d(int a[], int N)
    {
        
    int i;
        for(
    0Ni++)    {
            
    printf("%4d"a[i]);
        }  
    // mở ngoặc của cái này đâu

    cái } kia nó ko hề song song với { của nó.

    bạn nên nghiên cứu kĩ hơn về coding conventions tuy nhiên đừng đánh mất đi tính linh hoạt trong code nha. C là ngôn ngữ chuẩn mực và mềm dẻo.

    bạn có thể tham khảo cách trình bài của đoạn code sau: (cũng khá mạch lạc)
    PHP Code:
    long giaithua(unsigned n)
        {
            if (
    n==0) return 1;
                else return 
    n*giaithua(n-1);
        }
    long haicham(unsigned n)
        {
            if (
    n*(n-1)==0) return 1;
                else return 
    n*haicham(n-2);
        }
    int UCLN(int a,int b)
        {
            if (
    b==0) return a;
                else return 
    UCLN(ba%b);
        }
    int BCNN(int a,int b)
        {
            return 
    a*b/UCLN(a,b);
        } 
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

  7. #7
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Hì! Thank langman, xin tiếp thu ý kiến. Mình mới học C cơ bản ở học kỳ này thôi. Còn mấy cái hàm bạn đưa ra dùng đệ qui phải không? cái này mình chưa học. Đang muốn ngâm cứu mà thi cử tới nơi rồi. Có gì xin chỉ giáo thêm ^_^.
    /* The thing that I think is the thing that I do. */

  8. #8
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Trích dẫn Nguyên bản được gửi bởi Chautieu47 Xem bài viết
    Hì! Thank langman, xin tiếp thu ý kiến. Mình mới học C cơ bản ở học kỳ này thôi. Còn mấy cái hàm bạn đưa ra dùng đệ qui phải không? cái này mình chưa học. Đang muốn ngâm cứu mà thi cử tới nơi rồi. Có gì xin chỉ giáo thêm ^_^.
    Thật ra cái mình muốn bạn ngó ko phải là mấy cái đệ quy. Mình muốn bạn ngó về cách trình bày thôi. Coding conventions là 1 vấn đề quan trọng.

    Còn về đệ quy là vấn đề ko khó. Chỉ hơi trừu tượng. Và ko tối ưu lắm.

    Code:
    Việc sử dụng đệ quy cần sử dụng bộ nhớ chồng kiểu LIFO ( Last in , Fist out stack) để chứa các kết quả trung gian do đó phải chú ý kỹ đến trường hợp neo.
    
    .......
    Trên phương diện thí dụ thì đệ quy rất đơn giản và dễ hiểu. Song về phương diện kỹ thuật thì lại là 1 thí dụ ko đẹp lắm.
    
    Trích Ngôn ngữ lập trình C - Quách Tuấn Ngọc



    càng học càng thấy thích các cách đơn giản

    hi hi . Tất nhiên nên biết nhiều cách giải quyết vấn đề, nhưng khi thực sự giải quyết 1 vấn đề nào đó, càng đơn giản càng hay hi hi


    Chúc bạn thành công trong cuộc sống
    langman
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

  9. #9
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Nói về coding conventions, mình quen cách trình bày như vậy tại vì mình đọc một số tài liệu, đặc biệt là các ebook tiếng Anh đều trình bày như vậy. Ví dụ như cuốn C chuẩn: "The C programming language" (Cuốn này do chính Kernighan và Ritchie là người sáng tác ra ngôn ngữ C viết). Trong đó mình thấy các dấu đóng mở ngoặc của if, for, while, do... while... đều trình bày như vậy. Dấu đóng ngoặc } của các toán tử điều khiển đều thẳng hàng với tên của nó, còn dấu mở ngoặc { được đặt cùng hàng với toán tử ở phía sau điều kiện. Tương tự trong cuốn "Theory and Problems of Programming with C" đều trình bày như vậy. Mình tin là 2 cuốn sách này bạn có. Và mình search trên google về coding conventions thì thấy cái này: http://www.cs.rice.edu/~dwallach/CPlusPlusStyle.html

    Không biết bạn tìm hiểu về coding conventions trong tài liệu nào, cách trình bày code ra sao. Bạn có thể cho mình xem tài liệu đó được không? Coding conventions đúng là vấn đề quan trọng, mình cũng muốn trình bày sao cho rõ ràng, khoa học. Nếu cần có thể tạo 1 topic để cùng thảo luận về vấn đề này.
    /* The thing that I think is the thing that I do. */

  10. #10
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Trích dẫn Nguyên bản được gửi bởi Chautieu47 Xem bài viết
    Nói về coding conventions, mình quen cách trình bày như vậy tại vì mình đọc một số tài liệu, đặc biệt là các ebook tiếng Anh đều trình bày như vậy. Ví dụ như cuốn C chuẩn: "The C programming language" (Cuốn này do chính Kernighan và Ritchie là người sáng tác ra ngôn ngữ C viết). Trong đó mình thấy các dấu đóng mở ngoặc của if, for, while, do... while... đều trình bày như vậy. Dấu đóng ngoặc } của các toán tử điều khiển đều thẳng hàng với tên của nó, còn dấu mở ngoặc { được đặt cùng hàng với toán tử ở phía sau điều kiện. Tương tự trong cuốn "Theory and Problems of Programming with C" đều trình bày như vậy. Mình tin là 2 cuốn sách này bạn có. Và mình search trên google về coding conventions thì thấy cái này: http://www.cs.rice.edu/~dwallach/CPlusPlusStyle.html

    Không biết bạn tìm hiểu về coding conventions trong tài liệu nào, cách trình bày code ra sao. Bạn có thể cho mình xem tài liệu đó được không? Coding conventions đúng là vấn đề quan trọng, mình cũng muốn trình bày sao cho rõ ràng, khoa học. Nếu cần có thể tạo 1 topic để cùng thảo luận về vấn đề này.
    Ko cần đâu. Thật lạ là mình ko hề tìm hiểu trong quyển nào cả, theo bất kì ai cả. Mình code nhiều, thành quen và đề ra cho mình 1 cái chuẩn riêng, ko giống ai cả ( và mình tin tưởng vào bản thân ) . Code là tâm huyết của mỗi người, nên bạn đừng để nó ko mang bóng giảng của ai cả.

    Còn về {} . Bạn đừng nên nghĩ mình theo người nọ, người kia. Hãy nhìn và cảm nhận. Bạn thấy thế nào là đúng, bạn cho là đúng , nó hợp với bạn ok! là được. Thực sự bạn cũng thấy đó.
    Nếu (mình để { và } cùng 1 cặp với nhau thì // với nhau ) Nó rất dễ nhìn, tiện theo dõi.

    Khi tôi trình bày quan điểm của tôi với 1 đứa bạn trong lớp về bài tập, nó châm biếm tôi (trêu đểu) rằng :"... thế mày hơn cả cô giáo à...".
    Tôi nói rằng :
    "Cô giáo là lớp người đi trước. Cô đúc kết những kinh nghiệm và truyền cho tôi. Tôi là lớp người đi sau, tôi kế thừa và phát huy. Tôi phải sửa những chỗ sai và đi xa hơn. Nếu toàn bộ học sinh mà thua hết thầy cô giáo thì đất nước việt nam chúng ta làm sao tiến bộ và phát triển được?"

    Cái nào thấy hợp lí thì là đúng. Chuẩn của tôi đó.



    Những quyển sách đó tuy là hay nhưng ko phải là chân lý.
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

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

  1. Kỹ thuật C++ Sử dụng 1 Danh Sách Liên Kết với 2 Struct khác nhau như thế nào?
    Gửi bởi 5fox trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 23-04-2012, 04:45 PM
  2. Tìm chuỗi con gồm các số giống nhau liên tiếp dài nhất của một chuỗi cho trước
    Gửi bởi dailammoc trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 07-02-2012, 09:03 PM
  3. Tìm ba số liền nhau có tổng nhỏ nhất như thế nào?
    Gửi bởi nguyenthanhhai90vp trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 02-08-2010, 10:06 AM
  4. Bài tập C++ Nối 2 danh sách liên kết chẵn, lẻ lại với nhau như thế nào?
    Gửi bởi phatngoit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 16-06-2010, 05:16 PM
  5. [C++] In hình chữ nhật liên nhau
    Gửi bởi trieuanhl 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: 03-12-2006, 03:51 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