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

[narxix_voldemort]

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!

[l1k3.no1]

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.

[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

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];

[Nhuan_Trang_Only_Love]

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++;
}
}

[huynguyen]

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.

[shinichi_haha]

Đâ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

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.

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;
}

[phoenix2007]

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 !

[huynguyen]

Theo mình thì ok.
để mình edit lại code của cậu.

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é:

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.

[huynguyen]

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)

[phoenix2007]

ặ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 ?