Từ 1 tới 5 trên tổng số 5 kết quả

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

  1. #1
    Ngày gia nhập
    09 2011
    Bài viết
    1

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

    Ý 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!!!
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. void NhapDuLieu(int n, int a[20]);
    4. void Treamas(int n, int a[]);
    5. int main()
    6. {
    7.    int n, a[20];
    8.    printf("Nhap n = "); scanf("%d", &n);
    9.    NhapDuLieu(n, a);
    10.    Treamas(n, a);
    11.    getch();
    12.    return 0;
    13. }
    14. void NhapDuLieu(int n, int a[20])
    15. {
    16.    for(int i=1; i<=n; i++)
    17.    {
    18.       printf("Nhap a[%d] = ", i); scanf("%d", &a[i]);
    19.    }
    20. }
    21.  
    22. void Treamas(int n, int a[])
    23. {
    24.    int b[20];
    25.    for(int i=1; i<=n; i++)
    26.    {
    27.       b[i]=0;
    28.    }
    29.    for(i=1; i<=n-1; i++)
    30.    for(int j=2; j<=n; j++)
    31.    {
    32.       if(a[i] == a[j])
    33.       {
    34.      b[i]++;                              
    35.      for(int k=j; k<=n; k++)
    36.      {
    37.         a[j]=a[j+1];
    38.      }
    39.       }
    40.  
    41.    }
    42.    int max_b = b[1];
    43.    for(i=1; i<=n; i++)
    44.    {
    45.       if(b[i]>max_b)
    46.      max_b = b[i];
    47.    }
    48.    printf("So lan lap lai nhieu nhat la %d", max_b);
    49. }

  2. #2
    Ngày gia nhập
    08 2011
    Nơi ở
    Trà Vinh
    Bài viết
    20

    Trích dẫn Nguyên bản được gửi bởi lytieubinh_269 Xem bài viết
    Ý 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!!!
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. void NhapDuLieu(int n, int a[20]);
    4. void Treamas(int n, int a[]);
    5. int main()
    6. {
    7.    int n, a[20];
    8.    printf("Nhap n = "); scanf("%d", &n);
    9.    NhapDuLieu(n, a);
    10.    Treamas(n, a);
    11.    getch();
    12.    return 0;
    13. }
    14. void NhapDuLieu(int n, int a[20])
    15. {
    16.    for(int i=1; i<=n; i++)
    17.    {
    18.       printf("Nhap a[%d] = ", i); scanf("%d", &a[i]);
    19.    }
    20. }
    21.  
    22. void Treamas(int n, int a[])
    23. {
    24.    int b[20];
    25.    for(int i=1; i<=n; i++)
    26.    {
    27.       b[i]=0;
    28.    }
    29.    for(i=1; i<=n-1; i++)
    30.    for(int j=2; j<=n; j++)
    31.    {
    32.       if(a[i] == a[j])
    33.       {
    34.      b[i]++;                              
    35.      for(int k=j; k<=n; k++)
    36.      {
    37.         a[j]=a[j+1];
    38.      }
    39.       }
    40.  
    41.    }
    42.    int max_b = b[1];
    43.    for(i=1; i<=n; i++)
    44.    {
    45.       if(b[i]>max_b)
    46.      max_b = b[i];
    47.    }
    48.    printf("So lan lap lai nhieu nhat la %d", max_b);
    49. }
    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]
    Nó là con của thằng nào ? Con của thằng nào ? Nói mau!!!!!!!!!!!!!!!

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    552

    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
    C++ Code:
    1.  
    2. int flag=1;Maxlap=1;
    3. if (n==1)
    4.     return Maxlap;
    5. for (int i=0;i<n-1;i++)
    6.     if( array[i]==array[i+1])
    7.         flag++;
    8.     else
    9.     {
    10.         if (flag>Maxlap)
    11.              Maxlap=flag;
    12.         flag=1;
    13.      }
    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ì
    Đã được chỉnh sửa lần cuối bởi clchicken : 17-10-2011 lúc 12:04 AM.

  4. #4
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Trích dẫn Nguyên bản được gửi bởi lytieubinh_269 Xem bài viết
    Ý 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.

    C Code:
    1. // 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
    2.  
    3. int i, j;
    4. 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ất
    5. for (i = 0; i < n; i++)
    6. {
    7.   for (j = i+1, lapLai = 1; j < n; j++)  if (a[i] == a[j]) lapLai++;
    8.   if (lapLai > nnLan)
    9.   {
    10.     nnLan = lapLai;
    11.     nnViTri = i;
    12.   }
    13. }
    14. if (nnLan)
    15.   printf("Số lặp lại nhiều nhất là %d, tất cả %d lần", a[nnViTri], nnLan);

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    552

    @ 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

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

  1. Dùng vòng lặp để thay thế nhiều mệnh đề IF?
    Gửi bởi kittynguyen89 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 10
    Bài viết cuối: 31-12-2012, 08:31 AM
  2. Giúp e 1 xử lý vòng lặp for để giải nhiều phương trình 1 lúc
    Gửi bởi fly_or_die trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 27-10-2011, 05:52 PM
  3. Bài tập C lỗi sử dụng vòng lặp làm bài toán ra nhiều kêt quả khác nhau
    Gửi bởi kid_191 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 07-09-2011, 11:44 PM
  4. soft bị treo do vòng for xử lý quá nhiều, có nên dùng kĩ thuật đa luồng
    Gửi bởi chitvivo trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 13
    Bài viết cuối: 30-08-2011, 05:31 PM
  5. Lập trình C++ giá trị của xâu trong vòng lặp và ngoài vòng lặp khác nhau
    Gửi bởi virus93ttll trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 17
    Bài viết cuối: 14-05-2011, 02:43 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