Trả lời về bài toán "Dãy con khác nhau (nhiều nhất)"


Câu hỏi do Phạm Phương Tú đặt trong comment của [Vài nét về website]

Câu hỏi

Phạm Phương Tú gabeo90@...

                            
                    Mong thầy giúp em bài tập này

                Nhập mảng n số nguyên 

Hiện ra dãy con các số khác nhau nhiều nhất trong mảng trên.

Em không hiểu ý nghĩa của "dãy con" và "khác nhau nhiều nhất" ở đề trên.

Em xin cảm ơn thầy.

Chào Tú, có vẻ như các em chịu khó tham khảo nhiều "đề" nhỉ.
Bài toán này cũng hay nhưng "hơi khó" phải không?!
Ta cùng giải quyết từng vấn đề một nhé.

Thứ nhất là phải hiểu khái niệm "Dãy con"

Giả sử ta có mảng a như sau:

int a[13]={2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 0, 1, 2, 2};

Dãy con của 1 dãy (hay 1 mảng) có thể hiểu là các phần tử liên tiếp thuộc dãy (mảng) đó
Ví dụ trên ta có các dãy con:
{2, 3, 4}, {4, 5, 5, 5}, {6}, ......
Đấy là các dãy với tiêu chí bất kì.

Giờ ta xét đến tiêu chí "dãy con khác nhau"

Theo tôi, dãy con khác nhau là dãy con trong đó chỉ có các phần tử không giống nhau
Tôi sẽ tô màu các dãy con khác nhau trong mảng a để tiện phân biệt
{2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 0, 1, 2, 2}
trong đó nếu lấy dãy {2, 3, 4, 5, 5} thì sẽ không thỏa mãn điều kiện vì có 2 phần tử cùng có giá trị = 5.
Tương tự như vậy với 2 phần tử có giá trị =2 ở cuối mảng.

Giờ ta sẽ mô phỏng từng bước tìm 1 dãy con khác nhau.

Bắt đầu từ vị trí i=0

i
j
dãy đang xét
a[j]
Khác nhau không?
0
1
2
3
yes, tiếp nhận a[j] vào dãy, xét phần tử tiếp theo

2
2, 3
4
yes, tiếp nhận a[j] vào dãy, xét phần tử tiếp theo

3
2, 3, 4
5
yes, tiếp nhận a[j] vào dãy, xét phần tử tiếp theo

4
2, 3, 4, 5
5
no, thu được dãy từ i đến j-1 = {2, 3, 4, 5}
4
...
...
...
....

Lập trình:

/* Tim va hien cac day con khac nhau cua mang www.huudungle.net */ #include <conio.h> #include <stdio.h> //Tim xem gia tri tai m[c] //co xuat hien trong khoang [i]->[j] cua m ko? unsigned char found(int d, int c, int *m){     int i;     for (i=d; i<c; i++)         if (m[i]==m[c])             return 1;     return 0; } //hien cac phan tu mang m tu [d] den [c] void hien(int d, int c, int *m){     int i;     printf("\n");     for (i=d; i<=c; i++)         printf("%5d", m[i]); } void main(){     //gia su co mang a nhu sau     int a[20]={2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 0, 1, 2, 2};     int i=0,j, n=13;     clrscr();     while(i<=n){         j=i+1;         while(j<n && found(i,j, a)==0)             j++;         hien(i, j-1, a);         i=j;//xet tu diem ket thuc day hien tai         //neu thay bang i++;         //thi se hien tat ca cac day con         //ke ca cac day nam trong day da xet     }//        getch(); }

Chú ý:

  1. Có nhiều thuật toán để giải quyết bài toán này, tôi lựa chọn cách mà tôi cho là sẽ dễ nắm bắt với mức độ kiến thức của SV năm thứ 1 (mới học Ngôn ngữ lập trình)
  2. Để tìm dãy con dài nhất thì đương nhiên ta phải tổ chức lưu trữ được chỉ số đầu, chỉ số cuối của từng dãy con. Sau đó tính toán ra độ dài rồi hiển thị kết quả.

( đã được xem 2258 lần từ 14/05/2009 )

Phản hồi bài viết

   
Họ tên  
Email*
Mã xác thực email
Tiêu đề*  
Nội dung*  
Đính kèm 
 
 
nguyễn hồng phương phong_winter_love@...
thấy thương chúng em với !
Thầy ơi thầy cho đề thi lại dễ dễ thôi nhé, thầy thương chúng em thầy nhé !
Trang 1
Tôi là Lê Hữu Dũng
Giảng viên CNTT
Khoa Công nghệ Tin học
Viện Đại học Mở Hà Nội