Trang 1 trên tổng số 4 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 34 kết quả

Đề tài: Tối ưu thuật toán sắp xếp cơ bản

  1. #1
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Red face Tối ưu thuật toán sắp xếp cơ bản

    Cho mảng số nguyên A có n phần tử. Với thuật toán sắp xếp sau, hãy tìm cách tối ưu nó:
    C++ Code:
    1. void Swap(int *a,int *b)
    2. {
    3.  int tmp=*a;
    4.  *a=*b;
    5.  *b=tmp;
    6. }
    7.  
    8. void Sort(int A[],int n)
    9. {
    10.  for (int i=0;i<n-1;i++)
    11.    for (int j=i+1;j<n;j++)
    12.      if (A[i]>A[j]) Swap(&A[i],&A[j])
    13. }

    Dành cho các thành viên ham học toán và muốn thích tìm cách tối ưu.
    Xin ko gợi ý. Vì nếu gợi ý sẽ ra luôn kết quả mất rồi
    (PS: Đây là bài tớ thấy khá hay khi nhận được 1 cái project nhỏ, trên www.freelancer.com)
    Đã được chỉnh sửa lần cuối bởi Tadius : 21-04-2010 lúc 02:25 AM.

  2. #2
    Ngày gia nhập
    12 2009
    Bài viết
    190

    Có phải tối ưu hàm swap không bạn ?

  3. #3
    Ngày gia nhập
    03 2010
    Nơi ở
    My Home
    Bài viết
    772

    Trích dẫn Nguyên bản được gửi bởi Tadius Xem bài viết
    Cho mảng số nguyên A có n phần tử. Với thuật toán sắp xếp sau, hãy tìm cách tối ưu nó:
    C++ Code:
    1. void Swap(int *a,int *b)
    2. {
    3.  int tmp=*a;
    4.  *a=*b;
    5.  *b=tmp;
    6. }
    7.  
    8. void Sort(int A[],int n)
    9. {
    10.  for (int i=0;i<n-1;i++)
    11.    for (int j=i+1;j<n;j++)
    12.      if (A[i]>A[j]) Swap(&A[i],&A[i]
    13. }

    Dành cho các thành viên ham học toán và muốn thích tìm cách tối ưu.
    Xin ko gợi ý. Vì nếu gợi ý sẽ ra luôn kết quả mất rồi
    (PS: Đây là bài tớ thấy khá hay khi nhận được 1 cái project nhỏ, trên www.freelancer.com)
    C Code:
    1. Swap(&A[i],&A[i]);
    Nghe chừng không ổn

  4. #4
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi namdq2k Xem bài viết
    C Code:
    1. Swap(&A[i],&A[i]);
    Nghe chừng không ổn
    Không đâu vì tớ khai trong hàm hàm là con trỏ mà. Nêu phải truyền vào là địa chỉ 2 biến cần thay đổi.
    Còn nếu cậu truyên A+i là nó tính ra địa chỉ đó. Vì A là địa chị đầu của mảng ,cộng với i sẽ tính ra địa chỉ của A[i] tức là (A+i == &A[i])

  5. #5
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Không phải đâu tối ưu là làm sao giảm số lần lặp trung bình xuống ấy.
    Gợi ý:
    Nếu trong dãy các xuất hiện nhiều dãy đã con tăng thỏa thêm 1 tính chất nữa thì có thể rút ngắn được các lần lặp. Còn Swap thì ko thể tối ưu hơn được rồi.

  6. #6
    Ngày gia nhập
    03 2010
    Nơi ở
    My Home
    Bài viết
    772

    Mặc định Tối ưu thuật toán sắp xếp cơ bản

    Trích dẫn Nguyên bản được gửi bởi Tadius Xem bài viết
    Không đâu vì tớ khai trong hàm hàm là con trỏ mà. Nêu phải truyền vào là địa chỉ 2 biến cần thay đổi.
    Còn nếu cậu truyên A+i là nó tính ra địa chỉ đó. Vì A là địa chị đầu của mảng ,cộng với i sẽ tính ra địa chỉ của A[i] tức là (A+i == &A[i])
    Tớ bít cái đó rùi vấn đề tớ hỏi là:
    Swap(a, a) thì không có gì thay đổi cả

  7. #7
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi namdq2k Xem bài viết
    Tớ bít cái đó rùi vấn đề tớ hỏi là:
    Swap(a, a) thì không có gì thay đổi cả
    Ơ nhỉ. Chết lại nhầm đề rồi. Bà con thông cảm để tớ sửa lại.

  8. #8
    Ngày gia nhập
    12 2009
    Bài viết
    190

    Hàm swap có thể viết lại :
    PHP Code:
    void swapint *aint *)
    {
        *
    -= *= ( *+= *) - *b;

    Còn số vòng lặp thì có thể là sử dụng ý tưởng Sharker Sort thực hiện hai lượt đi và về cùng lúc lượt đi đẩy các phần từ nhỏ về đầu dãy lượt về đẩy các phần tử lớn về cuối dãy ( Chỉ biết vậy chứ cũng phải xem lại cái đã ) Có đúng không nhỉ ???

  9. #9
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Trích dẫn Nguyên bản được gửi bởi pannaruto Xem bài viết
    Hàm swap có thể viết lại :
    PHP Code:
    void swapint *aint *)
    {
        *
    -= *= ( *+= *) - *b;

    Còn số vòng lặp thì có thể là sử dụng ý tưởng Sharker Sort thực hiện hai lượt đi và về cùng lúc lượt đi đẩy các phần từ nhỏ về đầu dãy lượt về đẩy các phần tử lớn về cuối dãy ( Chỉ biết vậy chứ cũng phải xem lại cái đã ) Có đúng không nhỉ ???
    Swap bạn viết lại như vậy thì độ phức tạp vẫn như vậy thôi.
    Còn Sharker Sort thì ko phải.

  10. #10
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    trích đoạn code 2 năm trước
    PHP Code:
    void xapxepngd(int mang[], int n// xap xep nguyen giam dan 
        
    {
            
    int i,j;
            for (
    i=0;i<n-1;i++)
                for (
    j=i+1;j<n;j++)
                    if (
    mang[i]<mang[j]) mang[i]^=mang[j]^=mang[i]^=mang[j];
        } 
    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

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

  1. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  2. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  3. Bài tập C++ Viết chương trình nhập số lượng hàng hóa, giá cả, thuế, xuất ra tổng giá, thuế, tổng cộng
    Gửi bởi seit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 04-03-2011, 09:04 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 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