Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Chỉ mình về cách dồn mảng ^^

  1. #1
    Ngày gia nhập
    05 2008
    Nơi ở
    TP.HCM
    Bài viết
    7

    Red face Chỉ mình về cách dồn mảng ^^

    Các bạn gợi ý dùm mình thuật toán nha

    Giả sử có một mảng int gồm n số, hãy viết hàm làm nhiệm vụ dồn các số lẻ lên đầu mảng, các số chẵn xuống cuối mảng.

    Thank nhiều lắm ^^

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Có cần dồn theo thứ tự không nhỉ?
    Nếu không thì bạn có thể hình dung như sau:
    1. Tạo hai biến lưu trữ chỉ số đầu và cuối
    2. Dùng vòng lặp while( đầu != cuối )
    3. Trong vòng lặp xác định phần tử thứ đầu :
    a. Nếu lẻ thì đầu ++ để nó chạy đến phần tử là chẵn nếu có
    b. Ngược lại là chẵn rùi thì tiến hành while( đầu != cuối)
    b1. Nếu phần tử thứ cuối mà chẵn thì cuối-- để nó chạy đến phần tử là lẻ nếu có
    b2. Ngược lại thì hoán đổi hai phần tử thứ đầu và cuối.
    Nếu dồn mà vẫn giữ thứ tự thì bạn duyệt từ cuối về đầu, nếu gặp lẻ thì lưu trữ vị trí của nó. Sau đó băng qua các số lẻ phía trước nó đến khi gặp phần tử là chẵn hoặc về đầu. Nếu có phần tử là chẵn thì tiến hành hoán đổi từ đó đến vị trí lưu trữ và cập nhật lại các vị trí lưu trữ.
    Nói chung bạn viết một cái ma trận ra giấy rồi nghĩ xem nó như thế nào.
    Còn đây là một code mà trường hợp trên mình nói tới, bạn tham khảo chút.
    Còn trường hợp 2 bạn suy nghĩ xem sao nha:
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3.  
    4. void Swap(int &_iParam1, int &_iParam2)
    5. {
    6.     int _iTemp;
    7.     _iTemp=_iParam1;
    8.     _iParam1=_iParam2;
    9.     _iParam2=_iTemp;
    10. }
    11.  
    12. void Printer(int Matrix[],int _iLeng)
    13. {
    14.     for(int _iIndex=0; _iIndex<_iLeng; _iIndex++)
    15.         cout<<"  "<<Matrix[_iIndex];
    16.     cout<<endl;
    17. }
    18.  
    19. int main()
    20. {
    21.     int Matrix[10];
    22.     for(int _iIndex=0;_iIndex<10;_iIndex++)
    23.     {
    24.         cout<<endl
    25.             <<"Matrix["<<_iIndex<<"]=";
    26.             cin>>Matrix[_iIndex];
    27.     }
    28.  
    29.     system("cls");
    30.     cout<<"Truoc khi hoan doi"<<endl;
    31.  
    32.     Printer(Matrix,10);
    33.  
    34.     int _iTop=0;
    35.     int _iTail=9;
    36.  
    37.     while(_iTop != _iTail)
    38.     {
    39.         if(Matrix[_iTop] % 2 != 0 ) // le
    40.             _iTop++;
    41.         else
    42.         {
    43.             while(_iTop != _iTail)
    44.                 if(Matrix[_iTail] % 2 ==0 )// chan
    45.                     _iTail--;
    46.                 else
    47.                 {
    48.                     Swap(Matrix[_iTop],Matrix[_iTail]);
    49.                     break;
    50.                 }
    51.         }
    52.     }
    53.  
    54.     cout<<"Sau khi hoan doi:"<<endl;
    55.     Printer(Matrix,10);
    56.     cout<<endl;
    57.     system("Pause");
    58. }
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  3. #3
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Cách của tui là thế này: bạn duyệt các phần tử trong mảng từ trái sang phải bằng cách dùng vòng for cho i chạy từ 0 đến N - 2. Nếu phần tử a[i] chẵn thì dùng vòng for thứ 2 cho j chạy từ i + 1 đến N - 1 (Nghĩa là xét các phần từ đứng sau a[i]) nếu gặp a[j] lẻ thì đổi chổ a[j] với a[i], lúc này số lẻ lên trên, số chẵn xuống dưới. Cứ thế làm tiếp tục đến hết mảng.
    C Code:
    1. void donchle(int a[], int N)
    2. {
    3.     int i, j, t;
    4.  
    5.     for(i = 0; i < N - 1; i++)
    6.         if(!(a[i] % 2)) {
    7.             for(j = i + 1; j < N; j++)
    8.                 if(a[j] % 2)    {
    9.                     t = a[i]; a[i] = a[j]; a[j] = t;
    10.                     break;
    11.                 }
    12.         }
    13. }
    Đã được chỉnh sửa lần cuối bởi Chautieu47 : 04-06-2008 lúc 06:16 PM.

  4. #4
    Ngày gia nhập
    05 2008
    Nơi ở
    TP.HCM
    Bài viết
    7

    Trích dẫn Nguyên bản được gửi bởi Chautieu47 Xem bài viết
    Cách của tui là thế này: bạn duyệt các phần tử trong mảng từ trái sang phải bằng cách dùng vòng for cho i chạy từ 0 đến N - 2. Nếu phần tử a[i] chẵn thì dùng vòng for thứ 2 cho j chạy từ i + 1 đến N - 1 (Nghĩa là xét các phần từ đứng sau a[i]) nếu gặp a[j] lẻ thì đổi chổ a[j] với a[i], lúc này số lẻ lên trên, số chẵn xuống dưới. Cứ thế làm tiếp tục đến hết mảng.
    Code:
    void donchle(int a[], int N)
    {
    	int i, j, t;
    
    	for(i = 0; i < N - 1; i++)
    		if(!(a[i] % 2))
    		{
    			for(j = i + 1; j < N; j++)
    				if(a[j] % 2)	{
    					t = a[i]; a[i] = a[j]; a[j] = t; break;
    				}
    		}
    }
    Cách của bạn hay lắm, cám ơn nhiều nhá.
    Mà nếu mình muốn sắp xếp theo thứ tự tăng dần nữa thì phải thêm đoạn code nào nữa?

    ^^

  5. #5
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Thử thay
    i=j+1;
    vào trước break xem sao nha.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Mặc định Chỉ mình về cách dồn mảng ^^

    Muốn sắp nó tăng dần nữa thì có cách là sắp tăng những số lẻ, xong rồi sắp tăng những số chẵn. Như vậy thì mình cần biết là tới vị trí nào thì kết thúc các số lẻ và qua số chẵn. Có thể làm như sau:
    Code:
    for(k = 0; a[k] % 2 != 0; k++);
    /* Lam xong dong tren thi k la vi tri 
    phan tu chan dau tien trong mang */
    Sau đó mình viết một hàm sắp tăng như sau
    Code:
    void saptang(int a[], int d, int c)
    {
    	int i, j, t;
    
    	for(i = d; i < c - 1; i++)	{
    		for(j = i + 1; j < c; j++)
    			if(a[j] < a[i])	{
    				t = a[i]; a[i] = a[j]; a[j] = t;
    			}
    	}
    }
    Hàm saptang này dùng để sắp tăng 1 phần mảng từ vị trí d đến c - 1.
    Vậy là xong bây giờ chỉ việc gọi các hàm để nó sắp tăng dần theo như sau:
    Code:
    donchle(a, N);   // don le len dau, chan xuong duoi
    for(k = 0; a[k] % 2 != 0; k++); // lay vtri k la vtri ket thuc so le va qua so chan
    saptang(a, 0, k);   // sap tang so le
    saptang(a, k, N);   // sap tang so chan
    Cách này thì đơn giản, dễ hiểu, nhưng mà hơi bị dài. Không biết còn cách nào hay hơn không.

  7. #7
    Ngày gia nhập
    05 2008
    Nơi ở
    TP.HCM
    Bài viết
    7

    Mình vừa hỏi ông thầy, ông thầy chỉ mình cách làm như sau nè bạn:

    Sau khi thực hiện công việc dồn số lẻ lên đầu mảng và số chẵn xuống cuối mảng, mình thực hiện hàm sắp xếp như sau

    C Code:
    1. for(int i=0;i<n-1;i++)
    2.     for(int j=i+1;j<n;j++)
    3.         if(((a[i]%2==0) && (a[j]%2==0) ) || ((a[i]%2==1) && (a[j]%2==1) ) && a[i]>a[j])
    4.         {
    5.             int tam=a[i]; a[i]=a[j]; a[j]=tam;
    6.         }

  8. #8
    Ngày gia nhập
    10 2007
    Nơi ở
    TP. HCM
    Bài viết
    52

    Hì! thay vì chia ra sắp tăng số lẻ, số chẵn thì cái điều kiện trên đã làm việc này luôn rồi. ^_^
    Thank for your sharing.
    /* The thing that I think is the thing that I do. */

  9. #9
    Ngày gia nhập
    05 2008
    Nơi ở
    TP.HCM
    Bài viết
    7

    Trích dẫn Nguyên bản được gửi bởi NT_OnlyLove Xem bài viết
    Thử thay

    vào trước break xem sao nha.
    Thêm đoạn đó vào có tác dụng gì thế bạn?

  10. #10
    Ngày gia nhập
    04 2008
    Nơi ở
    Phu yen
    Bài viết
    10

    Trích dẫn Nguyên bản được gửi bởi yoyo89312 Xem bài viết
    Mình vừa hỏi ông thầy, ông thầy chỉ mình cách làm như sau nè bạn:

    Sau khi thực hiện công việc dồn số lẻ lên đầu mảng và số chẵn xuống cuối mảng, mình thực hiện hàm sắp xếp như sau

    C Code:
    1. for(int i=0;i<n-1;i++)
    2.     for(int j=i+1;j<n;j++)
    3.         if(((a[i]%2==0) && (a[j]%2==0) ) || ((a[i]%2==1) && (a[j]%2==1) ) && a[i]>a[j])
    4.         {
    5.             int tam=a[i]; a[i]=a[j]; a[j]=tam;
    6.         }
    làm thế cũng tốt nhưng nếu chia ra (đổi trước sắp sau) thì thêm có mấy dòng mà dễ hiểu,dễ nhớ.
    ----------------------------------------------------
    he he

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