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ố 17 kết quả

Đề tài: [BorlandC]Hỏi về giải thuật Insertion

  1. #1
    Ngày gia nhập
    04 2007
    Bài viết
    27

    Mặc định [BorlandC]Hỏi về giải thuật Insertion

    Cho mình hỏi trong giải thuật insertion :
    Code:
     for(i=0;i<length;i++)
        {
         j=i;
    
         while(j>0&&a[j]<a[j-1])
         {
          t=a[j-1];
          a[j-1]=a[j];
          a[j]=t;
          j--;
         }
        }
    Mình thắc mắc ở chỗ là tại sao trong vòng lặp while lại có điều kiện j>0 vậy , ở đây mình hiểu là cứ mỗi khi bốc một "lá bài" thì lại đem so sánh lá bài ấy với các lá bài đã có sẵn trên tay theo thứ tự từ phải sang trái , nếu lá bài này bé hơn các lá bài có trên tay thì ta đổi chỗ . Có điều nếu như lá bài này đã đến bét nhất rùi ( ô a[0] ) thì nó còn lá bài nào nữa đâu mà so sánh , chẳng lẽ trong mảng có tồn tại ô a[-1] và giá trị của ô này là giá trị rác ư ?

    <Xài thẻ CODE plz>
    Đã được chỉnh sửa lần cuối bởi Xcross87 : 21-05-2007 lúc 07:16 PM. Lý do: <Xài thẻ CODE plz>

  2. #2
    Ngày gia nhập
    04 2007
    Bài viết
    128

    trong khi j còn lớn hơn 0 mà tức là gặp j=0 thì stop!! khỏi cần làm mấy cái trong while nữa

  3. #3
    Ngày gia nhập
    04 2007
    Bài viết
    27

    à mình muốn hỏi là bây giờ nếu như ta bỏ điều kiện j>0 luôn thì có được không ? nếu ko thì tại sao mong giải thích giùm với .

  4. #4
    Ngày gia nhập
    11 2006
    Nơi ở
    Tiền Giang
    Bài viết
    28

    Tôi viết lại giải thuật InsertionSort như sau cho dễ hiểu để giải thích :

    Code:
    void InsertionSort (int * a , int n)
    {
    int  save; // Biến trung gian lưu lại giá trị phần tử cần chèn
    for (int i = 0 ; i < n ; i + +)
    	{
    	save = a [i]; //Lưu lại phần tử cần chèn thứ i
            //Dịch chuyển cách phần tử trong phần đã sắp xếp sang phải
    	for (int j = i ; j  > 0 && save < a [j-1] ; j --)
    		a [j] = a [j -1];
    		a [j] = save;//Chèn phần tử vào đúng vị trí
    	 }
    }
    Cách tiếp cận thuât toán Insert như sau :

    Chia mảng cần sắp xếp thành 2 phần :

    - Phần đã được sắp xếp và phần chưa được sắp xếp
    - Phần đã sắp xếp ban đầu chỉ 1 phần tử (và chính là phần tử đầu tiên của mảng). Lưu ý phần tử này hông nhất thiết phải là phần tử nhỏ nhất
    - Sau đó ta mở rộng phần được sắp xếp bằng cách chọn phần tử nhỏ nhất trong phần chưa được sắp xếp (biến j xuất hiện từ đây)
    - Sau đó so sánh phần tử nhỏ nhất vừa lấy trong phần chưa được sắp xếp với phần tử trong phần đã được sắp xếp để sắp thứ tự 2 phần tử này (vì phần được sắp xếp bây giờ đã là 2 phần tử)
    ....
    - Cứ như thế tiếp tục

    Thực ra mà nói, ta có thể đặt điều kiện cho biến j>=0 nhưng nếu nó bằng 0 vì ban đầu xét i = 0 (tức mảng được sắp xếp roài) nếu j = 0 nữa hóa ra ta so sánh nó với chính nó. Vậy nghĩa là ít ra phải lấy phần tử kế sau nó (tức phần tử trong phần chưa được sắp xếp) tức j = 1 > 0.

    Và thêm 1 điều nữa, nếu j = 0 thì ta phải so sánh với phần tử kế trước nó tức ptử [j-1]. Mà lúc này j = 0 vậy [j - 1] sẽ là phần tử nào. Vì chỉ số mảng trong C++ bắt đầu từ 0 hoặc 1

    Từ đó về sau không ai viết là j>=0 nữa mà viết là j>0

    Chạy tay :

    Giả sử bạn có mảng gồm 3 phần tử sau :

    a= 7 1 2
    a[0] a[1] a[2]

    - Xét i = 0 :

    Lưu biến saved = a[0] = 7
    xét j = i = 0 nhưng không thỏa điều kiện j >0 nên thoát khỏi vòng lặp for (j ...) ngay.

    - Cứ như thế tiếp tục ...

    Thân !

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

    Trích dẫn Nguyên bản được gửi bởi nanosi Xem bài viết
    Cho mình hỏi trong giải thuật insertion :

    for(i=0;i<length;i++)
    {
    j=i;

    while(j>0&&a[j]<a[j-1])
    {
    t=a[j-1];
    a[j-1]=a[j];
    a[j]=t;
    j--;
    }
    }

    Mình thắc mắc ở chỗ là tại sao trong vòng lặp while lại có điều kiện j>0 vậy , ở đây mình hiểu là cứ mỗi khi bốc một "lá bài" thì lại đem so sánh lá bài ấy với các lá bài đã có sẵn trên tay theo thứ tự từ phải sang trái , nếu lá bài này bé hơn các lá bài có trên tay thì ta đổi chỗ . Có điều nếu như lá bài này đã đến bét nhất rùi ( ô a[0] ) thì nó còn lá bài nào nữa đâu mà so sánh , chẳng lẽ trong mảng có tồn tại ô a[-1] và giá trị của ô này là giá trị rác ư ?
    về thuật toán mình thấy huyfeng nói quá rõ rồi chuyện giá trị rác mình nghĩ chắc chắn là có đó bạn về nguyên lí mình không rõ lắm nhưng có lẽ khi bạn cấp phát n phần tử (n vùng nhớ sát nhau+ liên tiếp)cho mảng thì phần tử như ban nói a[-1] nó nằm ngay sau a[0] và đó là một giá trị mà chúng ta chưa xác định được trước các huynh xem đúng ko ạh

  6. #6
    Ngày gia nhập
    04 2007
    Bài viết
    27

    Mặc định [BorlandC]Hỏi về giải thuật Insertion

    về giải thuật thì mình hiểu rồi , cái thắc mắc chính của mình ở chỗ là có tồn tại phần tử a[-1] ,a[-2],... hay không mà thôi .

  7. #7
    Ngày gia nhập
    11 2006
    Nơi ở
    Tiền Giang
    Bài viết
    28

    Theo mình nghĩ thì không tồn tại phần tử a[-1], a[-2]

    Thân !

  8. #8
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    # Không có ..và không tồn tại :|
    # Trừ khi dùng trong số ảo có tồn tại được phần tử tại vị trí âm nhưng mà xét theo vecto ảo
    None!

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

    Trích dẫn Nguyên bản được gửi bởi nanosi Xem bài viết
    về giải thuật thì mình hiểu rồi , cái thắc mắc chính của mình ở chỗ là có tồn tại phần tử a[-1] ,a[-2],... hay không mà thôi .
    Vẫn tồn tại nếu thỏa điều kiện giả sử i<0 là phần tử a[i] của một mảng, phần tử a[i] này vẫn tồn tại nếu (a-i) trỏ tới địa chỉ >NULL. (Chú ý mảng vẫn là một contro) tuy nhiên với i<0 phần tử a[i] là một nơi nào đó (có thể là nhân hệ điều hành) do đó việc thay đổi nó sẽ bị ngăn chặn nhưng ta có thể xem nội dung của nó được.

    Câu hỏi của cậu rất hay!
    Đã được chỉnh sửa lần cuối bởi shinichi_haha : 21-05-2007 lúc 07:04 PM.

    OoShinHaoO

  10. #10
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Có tồn tại, giải thuật sắp xếp chèn trực tiếp lính canh dùng phần tử a[-1] để làm lính canh đó thôi!!
    Code:
    void chenTrucTiepLC( long a[], long n)
    {
    	long j;
    	long x;
    	for(long i=1;i<n;i++)
    	{
    		x=a[i];
    		j=i-1;
    		while(a[j]>x )
    		{
    			a[-1]=x;
    			a[j+1]=a[j];
    			j--;
    		}
    		a[j+1]=x;
    	}
    }
    tiết kiệm 1 phép so sánh trong while(j>0&&a[j]<a[j-1]) bù lại vẫn phải tốn thêm phép gán a[-1]=x, mình nghĩ ý đồ của bạn là gợi mở ra cái này ah?
    Đã được chỉnh sửa lần cuối bởi soda_chanhmuoi : 21-05-2007 lúc 10:09 PM.

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

  1. Bài tập C Giải thuật Bubble Sort , Insertion Sort
    Gửi bởi cts2x trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 28-12-2013, 11:31 PM
  2. Mã nguồn C Lỗi Giúp về Insertion Sort
    Gửi bởi alethinh trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 19-03-2012, 03:52 PM
  3. Không thể sử dụng BORLANDC để biên dịch chương trình
    Gửi bởi hauhoc 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: 26-02-2011, 09:53 AM
  4. Insertion sort - Sắp xếp chèn
    Gửi bởi dungdragon88 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: 20-01-2010, 11:58 PM
  5. Các thuật toán sắp xếp mảng | Bubble sort, Shak sort, Insertion sort, Selection, ...
    Gửi bởi kids 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: 11-04-2009, 10:05 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