Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: thuật toán sắp xếp dữ liệu trên mảng sử dụng iterative và recursive function?

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    3

    Wink thuật toán sắp xếp dữ liệu trên mảng sử dụng iterative và recursive function?

    nhờ các cao thủ giải hộ em bài này với:

    Cho 1 mảng gồm 10 elements ( rand() mảng trong rang 0-100);

    Yêu cầu:

    + Di chuyển các phần từ trong mảng sang bên trái của mảng nếu chúng <=50
    + Di chuyển các phần từ trong mảng sang bên phải của mảng nếu chúng >50

    Sử dụng con trỏ để trỏ tới các phần tử trong mảng.

    Xuất ra kết quả sử dụng iterative và recursize function ( 2 version).

    E vẫn chửa nghĩ ra thuật toán cho bài này, ai giúp với.
    Thanks

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    C++ Code:
    1. Cho i bắt đầu từ từ đầu mảng, j bắt đầu từ cuối mảng
    2. Trong khi i và j chưa đụng nhau thì làm công việc sau:
    3.    if ( ai >50 )
    4.       if (aj <=50)  
    5.          swap (ai , aj)
    6.       else
    7.          giảm j
    8.    else
    9.       tăng i
    Giải thuật này nó rõ ràng dễ hiểu nhưng mà chưa tối ưu, bạn xài tạm

    C++ Code:
    1. i=0 ; j= cuối;
    2. while(i và j chưa đụng nhau,i chưa về cuối, j chưa về đầu)
    3. {
    4.   while(ai >50)
    5.       tăng i;
    6.   while(aj <=50)
    7.       giảm j;
    8.   swap(ai,aj);
    9. }
    Bạn thử nốt đoạn này xem có đúng đắn ko . Mình ko có compiler ở đây nên ko build đc
    C++ Code:
    1. i=0;j=cuối
    2. for (i;i!=j;i++)
    3.   if(ai >50)
    4.      for(j;j!=i;j--)
    5.         if (aj<=50)
    6.         {
    7.            swap(ai,aj)
    8.            j--;
    9.            break;
    10.          }
    Thử nốt đoạn này luôn nhé

    Có dc giải thuật rồi thì bạn dùng Recursion khỏe thôi
    Đã được chỉnh sửa lần cuối bởi clchicken : 31-10-2011 lúc 06:53 PM.

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    3

    bạn ơi thanks nha, đây là đoạn code của mình :

    Code:
    void swap2Elements (int* no1, int* no2)
    {
    	int temp;
    	temp = *no1;
    	*no1 =*no2;
    	*no2=temp;
    }
    	
    void swapIterative (int *a, int size)
    {
    	
    	
    	
    	int *left  = &a[0];
    	int *right = &a[size-1];
    	
    	while (left <right)
    	{
    		
    		while (*left <=50)
    		{
    			++left;
    		}
    		
    		while (*right >50)
    		{
    			--right;
    		}
    		
    	
    	swap2Elements(left,right);
    			
    		
    	
    	}
    }
    thì nó hiện thế này:

    http://imageshack.us/f/845/18784735.jpg/

    Vậy sao số 45 lại xuất hiện bên phải vậy?

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mình thấy là nếu đúng như thuật toán thì số 61 phải dc đổi chỗ với 45 .
    Mà đây hình như là sau khi đổi 83 cho 10 (đúng rồi) thì trỏ right nó bỏ qua mất số 45 để chạy tút về thấu 80 gần 61 (dừng vòng while của right) . Và làm đổi chỗ 61 và 80
    Tiếp đó left tăng 1 , lại trúng vào 61 . Và ko hiểu vì sao lần này nó lại tráo với 45

    Hoặc cũng có thể là . 61 tráo với 45 đúng rồi . Nhưng sau đó 45 lại bị tráo với 80 . Đây là sai sót cuối cùng của thuật toán . (Nghĩ cách fix dễ thôi)
    Mình nghĩ khả năng nhất là sai ở chỗ này đây

    Để chi tiết thì bạn debug step by step đi nhé . Debug step sẽ lòi ra cái chỗ sai cho bạn sửa

    Thế này nhé :
    C++ Code:
    1. while (left <right)
    2.     {
    3.        
    4.         while (*left <=50)
    5.         {
    6.             ++left;
    7.         }
    8.        
    9.         while (*right >50)
    10.         {
    11.             --right;
    12.         }
    13.        
    14.    
    15.             swap2Elements(left,right);
    16.             // thêm vào left++ ;
    17.             // right--;    
    18.             //Debug lại xem có điều gì khác biệt 
    19.     }
    Đã được chỉnh sửa lần cuối bởi clchicken : 31-10-2011 lúc 11:30 PM.

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    3

    Sau khi mình add ++left, và --right thì nó ntn:

    http://imageshack.us/photo/my-images/411/97654324.jpg/

    sao 13 vẫn chưa swap cho nhau ?

    + Thuật giải recursive này thì mình ko rõ ý nghĩa của việc thêm *no3.

    Code:
    void swap_2(int *no1, int *no2, int *no3)
    {
    	if (*no2==*no3)
    	{
    		return;
    	}
    	else
    	{
    	*no3=*no1;
    	*no1=*no2;
    	*no2=*no3;
    	
    	swap_2(no1,no2,no3);
    	}
    }

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

  1. Call to undefined function "nhandoi" in function main()
    Gửi bởi webboyk trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 19-06-2012, 10:09 PM
  2. Viết function để test một function khác như thế nào?
    Gửi bởi c_is_master 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: 05-05-2012, 02:55 AM
  3. Lập trình C Kỹ thuật lính canh | kỹ thuật đặt cờ hiệu | trên C là gì?
    Gửi bởi shinichi1290 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: 14-03-2010, 12:28 PM
  4. Thuật toán in ra tam giác trên C?
    Gửi bởi lebronjamesuit 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: 12-01-2010, 12:18 AM
  5. Kỹ thuật cài đặt thuật toán heapsort và quicksort trên C?
    Gửi bởi Taylaptrinh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 06-04-2008, 06:50 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