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.
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!
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.
Đâ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
Nếu thích viết C++ thì nên viết câu lệnh phức hợp:Code:int i = n-1; while ((key <= a[i])&&(i >= 0)){ a[i+1] = a[i]; --i; } a[i+1] = key; ++n;
while ((key <= a[i])&&(i >= 0)) a[(i--)+1] = a[i];
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++;
}
}
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.Theo tôi như trên vẫn không hợp lý
Theo mình thì ok.Nguyên bản được gửi bởi huynguyen
để 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; }
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 !
Để tôi viết lại code nhé:Nguyên bản được gửi bởi shinichi_haha
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.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; }
Đã được chỉnh sửa lần cuối bởi huynguyen : 12-01-2007 lúc 04:07 PM.
Đú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)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 ?
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)
ặ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 ?