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

Đề tài: Thuật toán tìm kiếm nhị phân trên mảng, lỗi không tìm kiếm được?

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    2

    Mặc định Thuật toán tìm kiếm nhị phân trên mảng, lỗi không tìm kiếm được?

    Bài này là nhập một mảng một chiều , tìm kiếm phần tử x theo nhị phân . Em viết code , phần sắp xếp tăng thì ok , còn phần tìm kiếm ko biết lỗi gì . mấy bro giúp giùm em nhé

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3.  
    4. void Nhap_mang(int a[] , int &n)
    5. {
    6.     printf(" Nhap so phan tu mang : ");
    7.     scanf("%d" , &n);
    8.     for(int i = 0 ; i<n ; i++)
    9.     {
    10.         printf("a[%d] = " , i);
    11.         scanf("%d" , &a[i]);
    12.     }
    13. }
    14.  
    15. void Xuat_mang(int a[] , int n)
    16. {
    17.     for(int i = 0 ; i<n ; i++)
    18.     printf("%d   " , a[i]);
    19. }
    20.  
    21. void Swap (int &a,int &b)
    22. {
    23.     int t = a;
    24.     a=b;
    25.     b=t;
    26. }
    27.  
    28.  
    29. void Sap_xep_tang (int a[] , int n)
    30. {
    31.     int i,j;
    32.     for(i = 0;i<n-1 ; i++)
    33.        for(j = n-1 ; j>i ; j--)
    34.           if(a[j] < a[j-1])
    35.          Swap(a[j] , a[j-1]);
    36. }
    37.  
    38. int Tim_nhi_phan (int a[] , int n , int x)
    39. {
    40.     int l = 0 , r = n - 1 , k;
    41.     while (l<=r)
    42.     {
    43.         k = (l+r)/2;
    44.         if(a[k] == x)
    45.         return k;
    46.         if(a[k]<x)
    47.         k = l+1;
    48.         else
    49.         k = r-1;
    50.     }
    51.     return -1;
    52. }
    53.  
    54. void main()
    55. {
    56.     clrscr();
    57.     int a[20],n,x;
    58.     Nhap_mang (a,n);
    59.     printf(" Mang vua nhap : ");
    60.     Xuat_mang (a,n);
    61.     printf("\nMang duoc sap xep tang: ");
    62.     Sap_xep_tang (a,n);
    63.         Xuat_mang(a,n);
    64.     printf("\n Nhap phan tu x can tim : ");
    65.     scanf("%d" , &x);
    66.     int c = Tim_nhi_phan (a,n,x);
    67.     if (c == -1)
    68.     printf("Ko tim thay phan tu %d", x);
    69.     else
    70.         printf("Tim duoc phan tu %d tai vi tri %d" , x , c);
    71.     getch();
    72. }

  2. #2
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3.  
    4. void Nhap_mang(int a[] , int &n)
    5. {
    6.     printf(" Nhap so phan tu mang : ");
    7.     scanf("%d" , &n);
    8.     for(int i = 0 ; i<n ; i++)
    9.     {
    10.         printf("a[%d] = " , i);
    11.         scanf("%d" , &a[i]);
    12.     }
    13. }
    14.  
    15. void Xuat_mang(int a[] , int n)
    16. {
    17.     for(int i = 0 ; i<n ; i++)
    18.     printf("%d   " , a[i]);
    19. }
    20.  
    21. void Swap (int &a,int &b)
    22. {
    23.     int t = a;
    24.     a=b;
    25.     b=t;
    26. }
    27.  
    28.  
    29. void Sap_xep_tang (int a[] , int n)
    30. {
    31.     int i,j;
    32.     for(i = 0;i<n-1 ; i++)
    33.        for(j = n-1 ; j>i ; j--)
    34.           if(a[j] < a[j-1])
    35.          Swap(a[j] , a[j-1]);
    36. }
    37.  
    38. int Tim_nhi_phan (int a[] , int n , int x)
    39. {
    40.     int l = 0 , r = n - 1 , k;
    41.     while (l<=r)
    42.     {
    43.         k = (l+r)/2;
    44.         if(a[k] == x)
    45.             return k;
    46.         else if(a[k]<x)
    47.             r = k-1;
    48.         else
    49.             l = k+1;
    50.     }
    51.     return -1;
    52. }
    53.  
    54. void main()
    55. {
    56.     int a[20],n,x;
    57.     Nhap_mang (a,n);
    58.     printf(" Mang vua nhap : ");
    59.     Xuat_mang (a,n);
    60.     printf("\nMang duoc sap xep tang: ");
    61.     Sap_xep_tang (a,n);
    62.         Xuat_mang(a,n);
    63.     printf("\n Nhap phan tu x can tim : ");
    64.     scanf("%d" , &x);
    65.     int c = Tim_nhi_phan (a,n,x);
    66.     if (c == -1)
    67.     printf("Ko tim thay phan tu %d", x);
    68.     else
    69.         printf("Tim duoc phan tu %d tai vi tri %d" , x , c);
    70.     getch();
    71. }

    bài của bạn triển khai thuật toán bị nhầm ,mình sửa lại rồi
    Đã được chỉnh sửa lần cuối bởi AlexF : 25-02-2009 lúc 11:14 AM.

  3. #3
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Tạm sửa như này, bạn test thử xem
    Chú ý là trước khi tìm kiếm phải sắp xếp đã.
    C Code:
    1. int Tim_nhi_phan (int a[] , int n , int x)
    2. {
    3.     int l = 0 , r = n - 1 , k;
    4.     while (l<=r)
    5.     {
    6.         k = (l+r)/2;
    7.         if(a[k] == x)
    8.              return k;
    9.         if(x<a[k])
    10.                  r = k-1;
    11.         else
    12.              l = k+1;
    13.     }
    14.     return -1;
    15. }

    @Edit: Chậm hơn coder_gate 1 bước

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    2

    bài sửa của coder_gate sai oi
    vẫn ko tìm được x
    bạn hoàng code chính xác
    thanks các bro nhiều

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

    giúp giùm mình với.mình cũng vik code giải thuật tìm kiếm nhị phân nhưng bị lỗi.chạy ra kết quả không đúng.
    C Code:
    1. #include<iostream.h>
    2. void nhapmang(int a[], int &n)
    3. {
    4.   cout<<"Nhap vao so n: ";cin>>n;
    5.   for (int i=0;i<n;i++)
    6.   {
    7.     cout<<"a["<<i<<"]: ";
    8.     cin>>a[i];
    9.   }
    10. }
    11.  
    12. void xuatmang(int a[], int n)
    13. {
    14.      cout<<endl;
    15.      for (int i=0;i<n;i++)
    16.       cout<<a[i]<<" ";
    17. }
    18. int tknp(int a[],int s)
    19. {
    20.     int n;
    21.     int i,start=0,end=n,found=0;
    22.     do
    23.     {
    24.         i=(end+start)/2;
    25.         if(a[i]==s)
    26.         found=1;
    27.         else if (a[i]<s)
    28.         start=i+1;
    29.         else if (a[i]>s)
    30.         end=i-1;
    31.     }
    32.     while(!found&&end>=start);
    33.     if(found==1)
    34.     return i+1;
    35.     else
    36.     return 0;
    37. }
    38. void main()
    39. {
    40.     int a;
    41.     int b;
    42.     int x[100];
    43.     int n;
    44.     int s;
    45.     nhapmang(x,n);
    46.     cout<<"mang vua nhap:\n";
    47.     xuatmang(x,n);
    48.     cout<<"nhap vao so can tim";
    49.     cin>>s;
    50.     b=tknp(x,s);
    51.     if(b==0)
    52.     cout<<"khong co";
    53.     else
    54.     cout<<"vi tri "<<b;
    55.    
    56. }

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

    Mặc định gợi ý cho bạn

    Bạn xem lại thuật toán tìm kiếm của Quanghoang và các phần còn lại của magician1611 nha.Bài của bạn còn thiếu phần sắp xếp.Ak mình không hiểu 1 vấn đề nữa là tại sao khi khai bao tham số cho phần Nhapmang có int &n ???(Bạn nên code đẹp hơn để mọi người dễ nhìn và dễ sửa bài cho bạn)

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

    Có int &n để bạn ấy muốn nhập n ở trong hàm.
    Khi ra khỏi hàm thì n mang giá trị đã bị thay đổi lần cuối cùng ở trong hàm.
    Um Mani Padme Hum...!!

  8. #8
    Ngày gia nhập
    07 2010
    Bài viết
    16

    mình có cái code tìm kiếm nhị phân nè (binary search) bạn thữ xem sao :
    C++ Code:
    1. giả sữ ta có mảng A có n phần tử, tăng dần cần tìm x trong A
    2.  
    3. int biSearch (int *_a,int x,int n)
    4. {
    5.     int i = 0;
    6.    
    7.    while (i < n)
    8.    {
    9.        int mid = (i + n) / 2 // Lấy phần tử ở giữa;
    10.  
    11.        if(_a[mid] <x) n = mid; // nếu x > a[mid] thì tìm trong nữa đầu
    12.        else
    13.             if(_a[mid] > x) i=mid + 1;   // ngược lại tìm trong nữa sau
    14.             else
    15.                  if (_a[mid] == x) return mid; // nếu a[mid]== x trả về vị trí tìm thấy
    16.    }
    17.    
    18.    return -1;  // không tìm thấy trả về -1
    19. }
    Đã được chỉnh sửa lần cuối bởi coolkg1412 : 16-01-2012 lúc 01:07 PM.

  9. #9
    Ngày gia nhập
    01 2011
    Bài viết
    27

    rất bổ ích, thanks các bro

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

  1. Các Thuật Toán Sắp Xếp & Tìm Kiếm Trên Mảng
    Gửi bởi cò lã trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 15-11-2011, 10:29 AM
  2. Thuật toán tìm kiếm BFS trên VC++?
    Gửi bởi anhhung90 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 0
    Bài viết cuối: 10-10-2010, 09:52 PM
  3. Lập trình C++ Thuật toán tìm kiếm mù(theo độ sâu hoặc rộng) và tìm kiếm leo đồi
    Gửi bởi chickentruong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 08-04-2010, 08:09 PM
  4. Tìm kiếm trên C++ | Tìm kiếm sinh viên trên C++ | Cách xây dựng hàm tìm kiếm?
    Gửi bởi yentinh 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: 24-05-2009, 05:11 PM
  5. Tìm kiếm trên file! Tìm kiếm xâu mẫu dùng giải thuật Naive | Giúp mình code sai ở đâu
    Gửi bởi totoise trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 19-04-2009, 08:22 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