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.
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ỉ.
Mọi người gợi ý em nha.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
Đã được chỉnh sửa lần cuối bởi dangnhapvn : 07-10-2008 lúc 10:33 AM. Lý do: Sai sot
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.
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à.
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
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á).
Sort lại rùi binary search là xong chứ gì đâu hả cậu
C++ Code:
#include <iostream> #include <algorithm> #include <vector> #include <string> int bS( const std::vector< std::string >& v, int beg, int end, const std::string& key ) { int pos; if( beg > end ) { pos = -1; } else { int at = ( beg + end ) / 2; if( key == v[ at ] ) pos = at; else if( key < v[ at ] ) pos = bS( v, beg, end - 1, key ); else pos = bS( v, beg + 1, end, key ); } return pos; } int main() { std::vector< std::string > vc; vc.push_back( "I" ); vc.push_back( "love" ); vc.push_back( "C++" ); std::sort( vc.begin(), vc.end() ); return 0; }
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.
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?
Đú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Đú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