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

Đề tài: Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C

    B- Tìm kiếm
    Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như sau:
    Cho một bảng gồm n bản ghi R1,R2,…, Rn. Với mỗi bản ghi Ri được tương ứng với 1 khoá ki (trường thứ I trong record). Hãy tìm bản ghi có giá trị bằng khoá X cho trước.”
    Nếu quá trình chúng ta tìm được bản ghi có giá trị khoá là X thì phép tìm kiếm được thoả (successful). Nếu không có giá trị nào thoả thì quá trình tím kiếm không thành công, sau quá trình này có thể xuất hiện thêm yêu cầu bổ sung thêm bản ghi mới có giá trị khoá là X vào thì giải thuật được gọi là tìm kiếm bổ sung.
    Các thuật toán tìm kiếm cơ bản là:

    I- Tìm kiếm tuần tự
    Đây là kĩ thuật tìm kiếm cổ điển nhất trên 1 danh sách chưa được sắp xếp. Nội dung cơ bản của phương pháp này là duyệt từ bản ghi thứ nhất cho tới bản ghi cuối cùng, và so sánh lần lượt với khoá X cần tìm, trong quá trình duyệt nếu có bản ghi trùng với giá trị của X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu duyệt tới cuối cùng mà không có bản ghi nào trùng giá trị thì quá trình tìm kiếm không thành công.

    Chương trình cài đặt thuật toán hoàn toàn đơn giản.
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. int Sequential(int *, int, int);
    7. void Init(int *, int);
    8. void Init(int *A, int n){
    9.     int i;
    10.     printf("\n Tao lap day so:");
    11.     for (i=0; i<n;i++){
    12.         A[i]=random(1000);
    13.         printf("%5d",A[i]);
    14.     }
    15.     delay(1000);
    16. }
    17. int Sequential(int *A, int x, int n){
    18.     register i,temp;
    19.     for (i=0; i<n ; i ++){
    20.         if (A[i] == X)
    21.             return(i);
    22.     }
    23.     return(-1);
    24. }
    25. void main(void){
    26.     int *A,n, x, k;clrscr();
    27.     printf("\n Nhap n="); scanf("%d",&n);
    28.     printf(“\n Sè x cÇn t×m:”); scanf(“%, &x);
    29.     A=(int *) malloc(n*sizeof(int));
    30.     k= Sequential(A,x,n);
    31.     if ( k>=0)
    32.         printf(“\n %d ë vÞ trÝ %, x,k);
    33.     else
    34.         printf(“\n %d kh«ng thuéc d•y”);
    35.     free(A); getch();
    36. }

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mặc định Tìm kiếm nhị phân

    Tìm kiếm nhị phân:

    Là phương pháp tìm kiếm phổ biến, dựa trên dãy đã sắp xếp thứ tự. Nội dung của giải thuật này là : lấy khoá X cần tìm so sánh với phần tử ở giữa dãy , với vị trí phần tử ở giữa được xác định là mid = (hight+low)/2, trong đó cận dưới low=0, cận trên hight= n-1. Vì dãy đã sắp xếp nên có các trường hợp sau xảy ra:
    nếu X= A[mid] thì cho ra kết quả (cần tìm X trong dãy A[i])
    nếu X < A[mid] => X thuộc khoảng [A[low];A[mid-1] ] lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[low]-> A[mid -1]
    Nếu X> A[mid]=> X thuộc khoảng [A[mid+1], A[hight]], lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[mid + 1], A[hight]
    Quá trình tìm cho tới khi tìm ra X hoặc không tìm được X trong dãy

    Có thể viết thuật toán tìm kiếm nhị phân theo vòng lặp hoặc theo đệ quy đều được.
    Ta sẽ viết luôn thủ tục hàm tìm kiếm nhị phân theo hai cách:
    Hàm tìm kiếm nhị phân mà chúng ta viết là :
    Binary_Search(Usertype *A, Usertype X, int n);
    Trong đó: Usertype là cấu trúc dữ liệu mà ta cần tìm kiếm, có thể là các kiểu đơn giản có sẵn: int, long , float, doublle., char… hoặc các kiểu do người dùng định nghĩa, có thể là một cấu trúc nào đó (ví dụ như Struct SinhVien, SoPhuc….)
    Mảng A có n phần tử đã được sắp xếp. Do đó trước khi thực hiện thao tác tìm kiếm thì chúng ta phải thực hiện thao tác sắp xếp dãy đã.

    Viết dưới dạng vòng lặp :
    C Code:
    1. int Binary_Search(Usertype *A, Usertype X, int n)  // hàm trả về là vị trí của X trong dãy
    2. {
    3.     int mid,low=o,hight=n-1;
    4.     while(low<=hight) // lap neu can duoi van nho hon can tren
    5.        {
    6.     mid=(low+hight)/2;  //xác định vị trí phần tử ở giữa
    7.     if(X>A[mid]) low=mid+1;      // X thuộc [mid+1,hight]
    8.             else        if(X<A[mid]) hight=mid-1;   // X thuộc đoạn [low,mid-1]
    9.     else   return(mid); //trả về vị trí của X trong dãy
    10.    }
    11.         return(-1); // nếu X không thuộc dãy thì trả về giá trị của hàm là -1
    12. }

    Viết dưới dạng hàm đệ quy:
    C Code:
    1. int Binary_Search(Usertype *A, Usertype X, int i,int j)  // hàm trả về là vị trí của X trong dãy
    2. {
    3.     int mid=(i+j)/2;
    4.     if(X>A[mid]&&i<mid)
    5.         return(Binary_Search(A,X,mid+1,j));
    6.     else if(X<A[mid]&&j>mid)
    7.         return(Binary_Search(A,X,i,mid-1));
    8.     else if(X==A[mid])
    9.         return(mid);
    10.     return(-1); // tra lai gia tri la -1 nếu không tìm thấy X
    11. }

    Chương trình cài đặt thuật toán cho tìm kiếm nhị phân một số nguyên trong dãy như sau:
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. int Binary_Search( int *, int, int);
    7. void Bubble(int *, int);
    8. void Init(int *, int);
    9.  
    10. int Binary_Search( int *A, int X, int n) {
    11.     int mid, low = 0, hight = n-1;
    12.     while (low<=hight){
    13.         mid = (low +hight)/2;
    14.         if (X >A[mid] ) low = mid +1;
    15.         else if (X<A[mid] ) hight = mid -1;
    16.         else    return (mid);
    17.     }
    18.     return(-1);
    19. }
    20. void Init(int *A, int n){
    21.     int i;
    22.     printf("\n Tao lap day so:");
    23.     for (i=0; i<n;i++){
    24.         A[i]=random(1000);
    25.         printf("%5d",A[i]);
    26.     }
    27.     delay(1000);
    28. }
    29. void Bubble(int *A, int n){
    30.     register i,j,temp;
    31.     for (i=1; i<n; i++){
    32.         for (j=n-1; j>=i;j--){
    33.             if (A[j-1]>A[j]){
    34.                 temp=A[j-1];
    35.                 A[j-1]=A[j];
    36.                 A[j]=temp;
    37.             }
    38.         }
    39.         printf("\n Ket qua lan:%d", i);
    40.         In(A,n);
    41.     }
    42. }
    43. void In(int *A, int n){
    44.     register int i;
    45.     for(i=0;i<n;i++)
    46.         printf("%5d",A[i]);
    47.     delay(1000);
    48. }
    49. void main(void){
    50.     int *A,n, X, k;clrscr();
    51.     printf("\n Nhap n="); scanf("%d",&n);
    52.     printf(“\n Sè cÇn t×m X=); scanf(%d”,&X);
    53.     A=(int *) malloc(n*sizeof(int));
    54.     Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n);
    55.     if ( k>0)
    56.         printf (“\n %d ë vÞ trÝ sè %d”, X, k);
    57.     else
    58.         printf(“\n %d kh«ng thuéc d·y”);
    59.     getch();
    60.     free(A);
    61. }

    Chúc các bạn vui vẻ!
    Trong bài này đã sắp xếp dãy số theo thuật toán Bubble Sort, thuật toán này các bạn có thể tìm hiểu ở các bài đã gửi trước đó trong cùng chủ đề này ở phía trên.

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

    --------------------Configuration: mingw2.95 - CUI Debug, Builder Type: MinGW (Old)--------------------

    Checking file dependency...
    Compiling C:\Program Files\C-Free 4\temp\Untitled1.cpp...
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:24: implicit declaration of function `int random(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:27: implicit declaration of function `int delay(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `i' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `j' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `temp' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:40: implicit declaration of function `int In(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:56: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:56: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:58: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:61: confused by earlier errors, bailing out

    Complete Make Untitled1: 13 error(s), 0 warning(s)

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

    Trích dẫn Nguyên bản được gửi bởi anhtai1281992 Xem bài viết
    --------------------Configuration: mingw2.95 - CUI Debug, Builder Type: MinGW (Old)--------------------

    Checking file dependency...
    Compiling C:\Program Files\C-Free 4\temp\Untitled1.cpp...
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:24: implicit declaration of function `int random(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:27: implicit declaration of function `int delay(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `i' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `j' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:30: ANSI C++ forbids declaration `temp' with no type
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:40: implicit declaration of function `int In(...)'
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:52: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:56: parse error before character 0223
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:56: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:58: stray '\' in program
    [Error] C:\Program Files\C-Free 4\temp\Untitled1.cpp:61: confused by earlier errors, bailing out

    Complete Make Untitled1: 13 error(s), 0 warning(s)
    Hậu quả của việc copy không cần suy nghĩ đây mà. Code trên la C mà dịch bằng trình dịch C++ thì ra một đống lỗi là đương nhiên. Còn mấy cái dấu nháy kép không hợp lệ nữa.

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

    bạn ơi xem giùm mình lỗi này với
    C:\Users\User\Desktop\timkiem.c In function `main':
    C:\Users\User\Desktop\timkiem.c syntax error before "printf"
    C:\Users\User\Desktop\Makefile.win [Build Error] [timkiem.o] Error 1
    thankk trc nha

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

    Mặc định Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C

    Em muốn góp ý chút về tìm kiếm nhị phân ạ. Tại lệnh : mid = (low+high) /2 ; nếu low và high quá to có thể sẽ khiến tràn bộ nhớ, nên sửa lại thành: mid = low+ (high-low)/2

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

  1. Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 31
    Bài viết cuối: 30-01-2015, 10:41 PM
  2. Các giải thuật sắp xếp - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 28
    Bài viết cuối: 15-05-2013, 11:10 AM
  3. Lý thuyết đồ thị | Giải thuật DFS (Depth First Search)
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 1
    Bài viết cuối: 14-01-2013, 10:48 PM
  4. 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
  5. giải thuật trên cây nhị phân tìm kiếm?!?
    Gửi bởi gauconchuabityeu 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: 08-03-2008, 06:29 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