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ú ý:
- 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)
- Để 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ả.