Không thể kiểm soát nhiều vòng lặp

[lytieubinh_269]

Ý tưởng: Bài toán tìm số lần lặp lại nhiều nhất trong mảng.
B1) Nhập mảng.
B2)Tạo mảng b với các pt bằng 0
ở mảng A:
lặp a1, a2... a(n-1)...
lặp a2, a3... a(n)...
nếu a[i] = a[j]
thì giá trị b[i] sẽ tăng lên 1
sau đó xóa a[j] để lần lặp tiếp theo ko bị trùng với lần lặp trước
Thực hiện xong 3 vòng lặp trên ta được mảng b gồm k phần tử với các giá trị. Sau đó tìm GTLN trong mảng b và xuất GTLN.

Đó là ý tưởng của mình và đây là bài code. Vấn đề là với 3 vòng lặp for chương trình ko thể kiểm soát mặc dù mình đã suy nghĩ rất nhiều. Mong các bạn góp ý làm nó được hoàn thiện hơn!!!

#include<stdio.h>#include<conio.h>void NhapDuLieu(int n, int a[20]);void Treamas(int n, int a[]);int main(){   int n, a[20];   printf("Nhap n = "); scanf("%d", &n);   NhapDuLieu(n, a);   Treamas(n, a);   getch();   return 0;}void NhapDuLieu(int n, int a[20]){   for(int i=1; i<=n; i++)   {      printf("Nhap a[%d] = ", i); scanf("%d", &a[i]);   }} void Treamas(int n, int a[]){   int b[20];   for(int i=1; i<=n; i++)   {      b[i]=0;   }   for(i=1; i<=n-1; i++)   for(int j=2; j<=n; j++)   {      if(a[i] == a[j])      {     b[i]++;                                    for(int k=j; k<=n; k++)     {        a[j]=a[j+1];     }      }    }   int max_b = b[1];   for(i=1; i<=n; i++)   {      if(b[i]>max_b)     max_b = b[i];   }   printf("So lan lap lai nhieu nhat la %d", max_b);}

[nguyenphuongcntv]

Ý tưởng: Bài toán tìm số lần lặp lại nhiều nhất trong mảng.
B1) Nhập mảng.
B2)Tạo mảng b với các pt bằng 0
ở mảng A:
lặp a1, a2... a(n-1)...
lặp a2, a3... a(n)...
nếu a[i] = a[j]
thì giá trị b[i] sẽ tăng lên 1
sau đó xóa a[j] để lần lặp tiếp theo ko bị trùng với lần lặp trước
Thực hiện xong 3 vòng lặp trên ta được mảng b gồm k phần tử với các giá trị. Sau đó tìm GTLN trong mảng b và xuất GTLN.

Đó là ý tưởng của mình và đây là bài code. Vấn đề là với 3 vòng lặp for chương trình ko thể kiểm soát mặc dù mình đã suy nghĩ rất nhiều. Mong các bạn góp ý làm nó được hoàn thiện hơn!!!

#include<stdio.h>#include<conio.h>void NhapDuLieu(int n, int a[20]);void Treamas(int n, int a[]);int main(){   int n, a[20];   printf("Nhap n = "); scanf("%d", &n);   NhapDuLieu(n, a);   Treamas(n, a);   getch();   return 0;}void NhapDuLieu(int n, int a[20]){   for(int i=1; i<=n; i++)   {      printf("Nhap a[%d] = ", i); scanf("%d", &a[i]);   }} void Treamas(int n, int a[]){   int b[20];   for(int i=1; i<=n; i++)   {      b[i]=0;   }   for(i=1; i<=n-1; i++)   for(int j=2; j<=n; j++)   {      if(a[i] == a[j])      {     b[i]++;                                    for(int k=j; k<=n; k++)     {        a[j]=a[j+1];     }      }    }   int max_b = b[1];   for(i=1; i<=n; i++)   {      if(b[i]>max_b)     max_b = b[i];   }   printf("So lan lap lai nhieu nhat la %d", max_b);}

Bạn ghi tiêu đề thật khó hiểu: Có phải bạn muốn tìm phần tử xuất hiện nhiều nhất trong mảng và in ra số lần phần tử này xuất hiện không????????
Lưu ý: mảng trong c bắt đầu là a[0] chứ không phải là a[1]

[clchicken]

Ui trời. Bạn làm thế này thành ra 3 vòng lặp lồng nhau mất rồi :-ss. Độ phức tạp thấp nhất sẽ luôn luôn là n^2 , và xui xẻo nhất là cái vòng lặp thứ 3 (for k chạy) luôn dc thực hiện. , độ phức tạp lớn nhất sẽ là n^3.
Sao bạn ko làm cách này :
1)Xắp xếp mảng , tăng hoặc giảm. (Độ phức tạp nlogn nếu bạn dùng các sort tiên tiến, còn ko thì cứ Bubble sort mà táng : n^2)
Nếu bạn muốn giữ nguyên hiện trạng vị trí các phần tử của Mảng Input thì có thể Clone nó ra thêm 1 mảng y chang vậy. Rồi thực hiện thuật toán này trên mảng clone.
2)Sau đó cho 1 vòng for duyệt lại: Độ phức tạp n.
Cho 1 cái flag duyệt số lần lặp hiện tại, và 1 cái Max lặp

 int flag=1;Maxlap=1;if (n==1)    return Maxlap;for (int i=0;i<n-1;i++)    if( array[i]==array[i+1])        flag++;    else    {        if (flag>Maxlap)             Maxlap=flag;        flag=1;     }

Cách này luôn cho độ phức tạp n^2 hoặc nlogn, Phụ thuộc bạn dùng thuật toán sort gì

[VoTichSu]

Ý tưởng: Bài toán tìm số lần lặp lại nhiều nhất trong mảng.
B1) Nhập mảng.
B2)Tạo mảng b với các pt bằng 0
ở mảng A:
lặp a1, a2... a(n-1)...
lặp a2, a3... a(n)...
nếu a[i] = a[j]
thì giá trị b[i] sẽ tăng lên 1
sau đó xóa a[j] để lần lặp tiếp theo ko bị trùng với lần lặp trước

Trong một bài tương tự trước đây, tôi có đưa ra một giải thuật có bao gồm phần "xóa a[j] để lần lặp tiếp theo ko bị trùng với lần lặp trước". Tuy nhiên, giải thuật ấy chỉ áp dụng cho "đếm số phần tử lặp lại".

Trong bài này, bạn chỉ cần tìm "số lần lặp lại nhiều nhất" cho nên không cần phải lưu lại số đếm và không cần phải xóa phần tử tránh trùng lặp.

vd { 1, 3, 2, 7, 5, 1, 4, 1, 2 }
Nếu ta cứ từ vị trí mà đếm về phía phải thì số lần đếm của 1 ở vị trí 0 sẽ là 3, ở vị trí 5 là 2 và ở vị trí 7 là 1. Số lần đếm của 2 ở vị trí 2 là 2 và ở vị trí 8 là 1. Tổng kết lại, ta vẫn có số phần tử lặp lại nhiều nhất là 1 và số lần lặp là 3.

// giải thuật tìm pt lặp lại nhiều nhất và không cần phải sắp xếp mảng int i, j;int lapLai, nnViTri, nnLan = 0; // số lần lặp lại, vị trí có số lặp lại nhiều nhất, sô lần lặp lại nhiều nhấtfor (i = 0; i < n; i++){  for (j = i+1, lapLai = 1; j < n; j++)  if (a[i] == a[j]) lapLai++;  if (lapLai > nnLan)  {    nnLan = lapLai;    nnViTri = i;  }}if (nnLan)  printf("Số lặp lại nhiều nhất là %d, tất cả %d lần", a[nnViTri], nnLan);

[clchicken]

@ VoTichSu : Thank bro .
À mà mình thấy giải thuật đó có chỗ hạn chế là phần tử đã dc đếm ở lượt trước thì vẫn bị đếm lại ở lượt sau . Do nó dựa trên base của Bubble sort
Ví dụ : 1 2 3 1 1 3 .
Lượt đầu tiên số 1 đã được đếm là 3 lần, đến khi i dịch lên vị trí thứ 4 thì số 1 lại dc đếm lại 2 lần nữa (tuy nhiên do lần này chỉ là 2 lần nên ko dc add vào kết quả). Tương tự với các số khác

Có cách gì để cải thiện việc này ko bro ơi