Trang 1 / 3 123 LastLast
Hiển thị kết quả từ 1 đến 10 / 22
  1. #1
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts

    Buồn quá đi ! viết chương trình tìm số lớn thứ hai trong mảng X trên C

    Cho mảng X có n số nguyên. Hãy xây dựng thuật toán tìm số lớn thứ hai trong mảng X. Đánh giá độ phức tạp của nó trong trường hợp xấu nhất.
    Được sửa bởi bebo90 lúc 22:25 ngày 16-12-2012
    Quote Quote

  2. #2
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts
    ai giúp mình phân tích độ phức tạp của thuật toán này với

    #include <stdio.h>

    void nhapmang(int a[], int *n);

    void main()
    {
    int a[100];
    int n, i, j, z;
    nhapmang(a, &n);
    for(i = 0; i < n; i++)
    {
    for(j = i+1; j < n; j++)
    {
    if(a[i] > a[j])
    {
    z = a[i];
    a[i] = a[j];
    a[j] = z;
    }
    }
    }
    for(i = n-1; i >= 0; i--)
    {
    if(a[i] > a[i-1])
    {
    printf("Gia tri lon thu nhi trong mang la: %d\n", a[i-1]);
    break;
    }
    }
    }
    void nhapmang(int a[], int *n)
    {
    int i;
    do
    {
    printf("Nhap gia tri n nguyen duong n = ");
    scanf("%d", n);
    if((*n <= 0)||(*n > 100))
    printf("Xin nhap lai gia tri n nguuyen duong va nho hon 100!\n");
    }
    while((*n <= 0)||(*n > 100));
    for(i = 0; i < *n; i++)
    {
    printf("Nhap phan tu thu %d la: ", i);
    scanf("%d", &a[i]);
    }
    }

  3. #3
    Tham gia
    10-03-2012
    Location
    Nha Trang
    Bài viết
    192
    Like
    3
    Thanked 33 Times in 31 Posts
    Như trên trong trường hợp xấu nhất nó sẽ là O(2n)
    Ví dụ cho n=5 và a[0] -> a[4] đều = 1

  4. Thành viên Like bài viết này:


  5. #4
    Tham gia
    15-03-2010
    Bài viết
    1,562
    Like
    84
    Thanked 1,571 Times in 860 Posts
    Trong tất cả các cách giải thì cách trên là dở nhất. Chẳng những dài dòng mà còn làm xáo trộn mảng.

  6. #5
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts
    Quote Được gửi bởi chet7h45 View Post
    Như trên trong trường hợp xấu nhất nó sẽ là O(2n)
    Ví dụ cho n=5 và a[0] -> a[4] đều = 1
    có thể giải thích cho mình hiểu được không.
    tại sao lại ra được O(2n)

  7. #6
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts
    Quote Được gửi bởi megaownage View Post
    Trong tất cả các cách giải thì cách trên là dở nhất. Chẳng những dài dòng mà còn làm xáo trộn mảng.
    Vậy cậu giải theo cách nào thì tốt hơn. nói vậy ai chẳng nói được

  8. #7
    Tham gia
    15-03-2010
    Bài viết
    1,562
    Like
    84
    Thanked 1,571 Times in 860 Posts
    Quote Được gửi bởi bebo90 View Post
    Vậy cậu giải theo cách nào thì tốt hơn. nói vậy ai chẳng nói được
    Kẻ biết nói khác mới kẻ chỉ tầm xàm. Người đang học hỏi thì ăn nói lễ độ một chút mới được người ta chỉ dẫn cho.

    2 cách giải:

    1. Giải in hệt như tìm số nhỏ nhất. Chỉ khác là lấy 2 số thay vì 1. Nếu giỏi về còn trỏ thì càng nhanh

    2. Dùng đệ quy, lượt đi tìm số nhỏ nhất, lượt về tìm số nhỏ nhất và khác số đó.

  9. Thành viên Like bài viết này:


  10. #8
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts
    vậy mình làm theo cách này đã tối ưu nhất chưa.
    cậu biết phân tích độ phức tạp của thuật toán không ?
    chỉ giúp mình làm sao để đánh giá được độ phức tạp của thuật toán. Cứ một vòng lặp for là O(n^1) ak ?
    mình sắp xếp dãy giảm dần rồi lấy giá trị thứ hai là giá trị max 2

    #include<conio.h>
    #include<stdio.h>
    void nhapmang(int a[], int *n);
    void main()

    {
    int a[100],i,j,n,tg;
    clrscr();
    printf("\n moi ban nhap so phan tu cua mang n=");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    printf("\n a[%d]",i);
    scanf("%3d",&a[i]);
    }
    for(i=0;i<n;i++)
    printf("%3d",a[i]);
    printf("\n");
    for(i=0;i<n-1;i++)
    for(j=i;j<n;j++)
    if(a[i]<a[j])
    {
    tg=a[i];
    a[i]=a[j];
    a[j]=tg;
    }
    printf("%3d",a[i]);
    printf(" so lon thu 2 la %d",a[1]);
    getch();
    }

  11. #9
    Tham gia
    10-03-2012
    Location
    Nha Trang
    Bài viết
    192
    Like
    3
    Thanked 33 Times in 31 Posts
    Quote Được gửi bởi bebo90 View Post
    vậy mình làm theo cách này đã tối ưu nhất chưa.
    cậu biết phân tích độ phức tạp của thuật toán không ?
    chỉ giúp mình làm sao để đánh giá được độ phức tạp của thuật toán. Cứ một vòng lặp for là O(n^1) ak ?
    mình sắp xếp dãy giảm dần rồi lấy giá trị thứ hai là giá trị max 2

    #include<conio.h>
    #include<stdio.h>
    void nhapmang(int a[], int *n);
    void main()

    {
    int a[100],i,j,n,tg;
    clrscr();
    printf("\n moi ban nhap so phan tu cua mang n=");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    printf("\n a[%d]",i);
    scanf("%3d",&a[i]);
    }
    for(i=0;i<n;i++)
    printf("%3d",a[i]);
    printf("\n");
    for(i=0;i<n-1;i++)
    for(j=i;j<n;j++)
    if(a[i]<a[j])
    {
    tg=a[i];
    a[i]=a[j];
    a[j]=tg;
    }
    printf("%3d",a[i]);
    printf(" so lon thu 2 la %d",a[1]);
    getch();
    }
    Cách này thì cũng chẳng khác cách trên là mấy. Bởi nó vẫn sử dụng 2 vòng lặp. Bạn cứ làm theo cách của megaownage đó. Thay vì bạn lấy 1 số, bạn sẽ lấy 2 số lớn nhất nhưng khác nhau. Thì chỉ tốn 1 vòng lặp để tìm thôi.

    Mình cũng không nhớ lắm về cái tìm độ phức tạp truy nhiên trong trường hợp xấu nhất, thì thuật toán lúc đầu bạn đưa ra sẽ chạy 2 vòng lặp từ 0->n. Trường hợp nào xấu nhất thì mình ghi trong ví dụ rồi.

    Còn thuật toán này thì có lẽ là O((n-2)(n-1)). Hehe không biết nữa, đoán đại thôi. Nói chung bạn cứ làm theo cách của megaownage.

    À bổ sung thêm là mình hay tự làm gián đoạn vòng lặp bằng continue; và break; .Ví dụ khi bạn đã chắc chắn số nào là lớn nhất nhì rồi thì break ra khỏi vòng lặp, đỡ hao phí các vòng lặp phía sau.
    Được sửa bởi chet7h45 lúc 10:09 ngày 17-12-2012 Reason: Bổ sung thêm

  12. Thành viên Like bài viết này:


  13. #10
    Tham gia
    21-07-2009
    Bài viết
    21
    Like
    12
    Thanked 0 Times in 0 Posts
    Mình đánh giá độ phức tạp như thế này có đúng không. Nếu sai thì sai ở đâu?
    Trường hợp xấu nhất là khi tập tin được sắp sếp theo thứ tự tăng dần.
    Khi vòng lặp for của I chạy n lần thì vòng lặp for của j sẽ chạy
    n + (n-1) + … + 2 + 1 = n(n+1)/2 = (n^2 + n)/2 = O(n^2).
    Vòng lặp for của I là O(n)
    Vậy độ phức tạp trường hợp xấu nhất của thuật toán là O(n^3).
    Mình đang thử làm theo cách của megaownage. thank you!

Trang 1 / 3 123 LastLast

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •