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

Đề tài: Thuật toán tìm kiếm(searching)

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

    Mặc định Thuật toán tìm kiếm(searching)

    Mọi nguời gợi ý cho em bài tập này nhé.
    Nếu ko dùng thuật toán tìm kiếm tuần tự thì còn thuật toán nào làm bài này nữa không nhỉ.
    Code:
    Input:  file ‘words.in’ chứa N từ (N<=10^5), mỗi từ là một xâu kí tự và viết trên 1 dòng. File 
    ‘lookingwords.in’ chứa M từ (M <= 10^7), mỗi từ là một xâu kí tự và viết trên 1 dòng.  
    Problem: Với mỗi từ trong file ‘lookingwords.in’, tìm vị trí xuất hiện  trong file ‘words.in’. Với 
    mỗi từ chỉ cần chỉ ra một vị trí. Nếu từ ñó không xuất hiện, thì vị trí ñược trả lại là ‘-1’. 
    Output: ‘checkedwords.out’ chứa kết quả tìm kiếm. Dòng thứ i ghi vị trí xuất hiện của từ thứ i 
    trong danh sách.  Vị trí các từ trong file được tính bắt đầu từ 1.  
     
    Ví dụ 
    words.in  lookingwords.in    checkedwords.out 
    hello           love                  3 
    world          you                  4 
    love           K51CC              -1 
    you            hello                 1 
    K51CD
    Mọi người gợi ý em nha.
    Đã được chỉnh sửa lần cuối bởi dangnhapvn : 07-10-2008 lúc 10:33 AM. Lý do: Sai sot

  2. #2
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Bài này bạn nên dùng bảng băm hoặc cây nhiều nhánh để cải thiện tốc độ tìm kiếm.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

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

    Cái này do số lượng số từ nhỏ nên chỉ cần đọc thông tin 2 file lên và thực hiện các thuật toán tìm kiếm chuổi là được mà.

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

    http://forums.congdongcviet.com/showthread.php?t=8746
    1 bài toán tương tự như của cậu,nếu muốn phát triển lên bài của cậu thì làm thêm hàm return lại vị trí của từ là được

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

    Cảm ơn các anh nhiều ạ, nhưng nhà em chưa được thầy dạy mảng băm và cây mới chết chứ, vài tuần nữa mới học Cây và mảng Băm. Giờ ko biết làm kiểu gì đây , chắc là phải tìm kiếm tuần tự thôi(gà quá).

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Thuật toán tìm kiếm(searching)

    Sort lại rùi binary search là xong chứ gì đâu hả cậu
    C++ Code:
    1. #include <iostream>
    2. #include <algorithm>
    3. #include <vector>
    4. #include <string>
    5.  
    6. int bS( const std::vector< std::string >& v, int beg, int end, const std::string& key )
    7. {
    8.     int pos;
    9.     if( beg > end ) {
    10.         pos = -1;
    11.     }
    12.     else {
    13.         int at = ( beg + end ) / 2;
    14.         if( key == v[ at ] )
    15.             pos = at;
    16.         else if( key < v[ at ] )
    17.             pos = bS( v, beg, end - 1, key );
    18.         else
    19.             pos = bS( v, beg + 1, end, key );
    20.     }
    21.     return pos;
    22. }
    23.  
    24. int main()
    25. {
    26.     std::vector< std::string > vc;
    27.  
    28.     vc.push_back( "I" );
    29.     vc.push_back( "love" );
    30.     vc.push_back( "C++" );
    31.  
    32.     std::sort( vc.begin(), vc.end() );
    33.  
    34.     std::cout << " \"love\" is at " << bS( vc, 0, vc.size(), "love" );
    35.  
    36.     return 0;
    37. }

  7. #7
    Ngày gia nhập
    09 2008
    Bài viết
    3

    Sort-> ít nhất là O(n)log(n)-> hu hu + Tìm kiếm nhị phân = ????;
    Tìm kiếm tuần tự-> O(n) + O(n)+.....+O(n) < O(n)log(n);
    Hông biết có đúng ko nữa
    Vấn đề ở đây là tối ưu.
    Cảm ơn bạn.

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Cái đó trường hợp trung bình, tìm kiếm nhị phân O( logn ), cậu cần tìm kiếm bao nhiêu cái ?
    Giả sử cần tìm N phần tử :
    Linear search gives : n x O( n ) = n^2
    Binary search gives : O( n )log( n ) + n.log( n ) = log( n )( n + O( n ) ) = log( n ) x 2( n ) = log( n ) x n
    which ones is faster ?

  9. #9
    Ngày gia nhập
    09 2008
    Bài viết
    3

    Đúng là "Binary search gives" nhanh hơn "Linear search gives" nhưng vấn đề ở đây là mảng chưa được sắp xếp-> làm thế nào mà dùng được
    "Binary search gives". Nếu sắp xếp lại rồi dùng "Binary search gives"-> Chưa tối ưu->hổng biết có đúng ko

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

    Đúng là "Binary search gives" nhanh hơn "Linear search gives" nhưng vấn đề ở đây là mảng chưa được sắp xếp-> làm thế nào mà dùng được
    "Binary search gives". Nếu sắp xếp lại rồi dùng "Binary search gives"-> Chưa tối ưu->hổng biết có đúng ko
    dúng đấy,tìm kiếm nhị phân chỉ có thể dùng được khi dữ liệu được sắp xếp thôi,muốn tìm kiếm không sắp xếp chắc chỉ có cách for n thôi

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

  1. Duplicate Searching - Tool tìm kiếm file trùng lặp
    Gửi bởi DKhanh trong diễn đàn Sản phẩm phần mềm của bạn
    Trả lời: 39
    Bài viết cuối: 28-01-2011, 01:38 PM
  2. Bài 4: Chapter 3 :Searching, Modifying, and Encoding Text
    Gửi bởi snake_programmer trong diễn đàn English for IT | Tiếng anh cho dân CNTT
    Trả lời: 7
    Bài viết cuối: 14-01-2011, 09:44 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. Thuật toán tìm kiếm | Ebooks tổng hợp thuật toán tìm kiếm ???
    Gửi bởi Hoadao trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 1
    Bài viết cuối: 11-05-2009, 02:20 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