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

Đề tài: [C] Chèn thêm phân tử vào dãy tăng dần???

  1. #1
    No Avatar
    narxix_voldemort Khách

    Mặc định [C] Chèn thêm phân tử vào dãy tăng dần???

    Cho một dãy tăng đần.chèn thêm 1 phần tử sao cho dãy đó vẫn là dãy tăng dần
    Cám ơn các bác trước nha!

  2. #2
    No Avatar
    l1k3.no1 Khách

    Theo ý tưởng nêu dãy tăng dần rồi khi chèn vào .Thì chỉ cần sao sánh số đứng trước đứng sau nó nêu thõa
    a<x<b

    thì là ổn rùi.^^.Còn code thui tớ chịu,hic đang trên đường học hỏi.

  3. #3
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Đây là code, ý tưởng là so sánh đồng thời dời vị trí các phần tử để lấy chỗ chèn key vào
    Code:
    int i = n-1;
    while ((key <= a[i])&&(i >= 0)){
          a[i+1] = a[i];
          --i;
    }
    a[i+1] = key;
    ++n;
    Nếu thích viết C++ thì nên viết câu lệnh phức hợp:
    while ((key <= a[i])&&(i >= 0)) a[(i--)+1] = a[i];

  4. #4
    No Avatar
    Nhuan_Trang_Only_Love Khách

    Theo tôi như trên vẫn không hợp lý .bạn có thể làm như sau


    void Dao(float &a,float &b)
    {
    float temp=a;a=b;b=temp;//bien temp la bien tam hay trung gian
    }
    void Chen(float A[],int gh) //chen vao va van giu duoc tinh chat cua day tang dan
    {
    int i=0;
    while(A[i]<A[gh-1]) i++;
    Dao(A[i],A[gh-1]);
    i++;
    while(i<gh)
    {
    Dao(A[i],A[gh-1]);
    i++;
    }
    }

  5. #5
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Theo tôi như trên vẫn không hợp lý
    Xin cho biết ko hợp lý chỗ nào, bạn test thử chưa mà bảo ko hợp lý? Sao lại có người tự cho mình là đúng, cho người khác là sai ấy nhỉ, tui chẳng hiểu nổi. Bạn giải thích giúp giải thuật của bạn, tui noob lắm, ko hiểu.

  6. #6
    Ngày gia nhập
    07 2006
    Bài viết
    121

    Mặc định [C] Chèn thêm phân tử vào dãy tăng dần???

    Trích dẫn Nguyên bản được gửi bởi huynguyen
    Đây là code, ý tưởng là so sánh đồng thời dời vị trí các phần tử để lấy chỗ chèn key vào
    Code:
    int i = n-1;
    while ((key <= a[i])&&(i >= 0)){
          a[i+1] = a[i];
          --i;
    }
    a[i+1] = key;
    ++n;
    Nếu thích viết C++ thì nên viết câu lệnh phức hợp:
    while ((key <= a[i])&&(i >= 0)) a[(i--)+1] = a[i];
    Theo mình thì ok.
    để mình edit lại code của cậu.
    Code:
    void insert(int *a,int *n,int key)
    {
           int i;
           i=*n++;
          if(i==0)a[i]=key;
          while(key<a[i])
                  a[i--]=a[i-1];
          a[i]=key;
    }

  7. #7
    No Avatar
    phoenix2007 Khách

    Với dãy đã được sắp xếp sẵn, thì tội jì mà không dùng phương pháp binary search để tối ưu hóa chương trình. Thuật toán như sau :
    - Giả sử ta có khóa muốn chèn vào là x
    - Chia 2 dãy ra ( ((max + min)/2) ), và lấy x so sánh với khóa ở giữa dãy, nếu x lớn hơn thì lấy tiếp nửa phần nhỏ hơn x
    - Cứ thế, cho đến khi x tìm được vị trí thích hợp để chèn. Rồi viết code ! Ok !
    Nếu bạn cần, mình có thể cung cấp code cho bạn !
    Mình nghĩ thuật toán này là tối ưu nhất đối với dạng toán này ! Phải ko các bác ?
    Chúc vui !

  8. #8
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Trích dẫn Nguyên bản được gửi bởi shinichi_haha
    Theo mình thì ok.
    để mình edit lại code của cậu.
    Code:
    void insert(int *a,int *n,int key)
    {
           int i;
           i=*n++;
          if(i==0)a[i]=key;
          while(key<a[i])
                  a[i--]=a[i-1];
          a[i]=key;
    }
    Để tôi viết lại code nhé:
    Code:
    void insert(int a,int& n,int key){
         int i;
         i = n++;
         while(key < a[i-1]) a[i--] = a[i-1];
         a[i] = key;
    }
    hình như ông bạn định dùng mảng động nên tui thấy hơi rắc rối, làm mảng tĩnh cho chắc ăn. Lần trước cho i = n-1 thấy ko hiệu quả lắm, cho i = n thấy tiện lợi hơn.
    Đã được chỉnh sửa lần cuối bởi huynguyen : 12-01-2007 lúc 04:07 PM.

  9. #9
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Với dãy đã được sắp xếp sẵn, thì tội jì mà không dùng phương pháp binary search để tối ưu hóa chương trình. Thuật toán như sau :
    - Giả sử ta có khóa muốn chèn vào là x
    - Chia 2 dãy ra ( ((max + min)/2) ), và lấy x so sánh với khóa ở giữa dãy, nếu x lớn hơn thì lấy tiếp nửa phần nhỏ hơn x
    - Cứ thế, cho đến khi x tìm được vị trí thích hợp để chèn. Rồi viết code ! Ok !
    Nếu bạn cần, mình có thể cung cấp code cho bạn !
    Mình nghĩ thuật toán này là tối ưu nhất đối với dạng toán này ! Phải ko các bác ?
    Đúng là tối ưu nhất rồi, tìm kiếm thì tối ưu nhưng đến lúc chèn vào thì lại phải chạy 1 vòng for từ điểm cần chèn đến cuối dãy để lùi dần số -> cái này mới là ko tối ưu vì độ phức tạp là O(2n)
    Thay vì vậy, tui nghĩ cứ cho nó chạy từ cuối về đầu, trong lúc chạy thì vừa lùi vừa so sánh, nếu cần thì gán, ko cần lại chạy tiếp -> độ phức tạp: O(n)

  10. #10
    No Avatar
    phoenix2007 Khách

    ặc....ặc....Bác ơi, theo mình thì khi chèn, không cần cho chạy từ đầu đâu !
    Nếu bài này dùng mảng, thì khi dùng binary search, ta đã có được chỉ số của mảng tại điểm phân chia, cứ tiếp tục như thế, ta sẽ có được chỉ số của điểm cần chèn vào ! Việc còn lại là chỉ cần chèn vào thui ! hihi ! Không biết đúng kô nữa ?

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

  1. Thêm mã nhân viên tăng dần và theo đơn vị
    Gửi bởi mrlonely0390 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 12-10-2013, 02:03 PM
  2. ADO.NET Thêm ID tự tăng vào SQL từ ADO.NET
    Gửi bởi phucnguyen0818 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 23-12-2012, 10:30 PM
  3. Thêm Nhân viên với Mã tăng tự động trong C# bằng cách nào?
    Gửi bởi ltdt trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 8
    Bài viết cuối: 16-10-2012, 02:01 PM
  4. Kỹ thuật C thêm một số vào dãy tăng?
    Gửi bởi cautrucdulieu 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: 18-07-2011, 11:13 PM
  5. Thêm 1 phần tử vào mảng không làm mất tính tăng của mảng
    Gửi bởi chiensy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 04-07-2009, 10:57 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