Giáo trình ngôn ngữ C
tải về 2.34 Mb. Chế độ xem pdf
|
| Tìm kiếm trên mảng
Giả sử cho trước một mảng các số nguyên A(n), và một số x. hãy kiểm tra x có thuộc mảng A hay không? Với bài toán tìm kiếm trên mảng nói chung, chúng ta phân hai trường hợp: Trường hợp 1: Mảng A không có trật tự (chưa được sắp) thì để tìm kiếm một giá trị nào đó thì chúng ta phải duyệt tuần tự mảng từ phần tử đầu tiên cho tới khi gặp giá trị đó hoặc tới phần tử cuối cùng thì mới khẳng định được giái trị đó có thuộc mảng hay không. Như vậy trong trường hợp kém nhất thì số lần so sánh là n. có thể minh hoạ như sau: // Nhập n, A(n), x i = 0 ; while((i else printf(“%d co trong mang tai vi tri %d”, x, i); Trường hợp 2: Mảng A đã được sắp (không mất tổng quát giả sử tăng dần), trong trường hợp này chúng ta có thể áp dụng phương pháp tìm kiếm nhị phân để giảm số bước phải so sánh. Ý tưởng là ta chia đôi mảng A thành hai phần, so sánh x với phần tử ở giữa của mảng A[g] xảy ra ba trường hợp : à A[g] = = x thì kết luận x thuộc vào A và kết thúc à A[g] > x thì chúng ta lặp lại việc tìm x trong nửa cuối của mảng à A[g] < x thì chúng ta lặp lại việc tìm x trong nửa đầu của mảng Như vậy sau một bước so sánh chúng ta có thể giảm số phần tử cần duyệt còn một nửa. Như vậy số lần kiểm tra so sánh trung bình sẽ giảm so với phương pháp duyệt tuần tự. có thể minh hoạ như sau: // Nhập n, A(n), x // Mảng A theo thứ tụ tăng dần l = 0, r =n-1 ; // l, r chỉ số đầu, cuối của các phần tử cần duyệt while(l <= r) { g = (l+r)/2; // lấy phần tử giữa if (A[g] ==x) printf(“ %d thuộc vào mảng “); return; if (A[g] > x) l = g+1 ; // lặp timg trong nửa cuối Gi¸o tr×nh tin häc c¬ së II - N gôn ngữ C 74 else r = g-1; // tim trong nửa đầu. } printf(“%d khong co trong mang”,x ); //....... Ví dụ V.4: Chương trình sinh ngẫu nhiên một mảng có n phần tử, sắp xếp mảng đó theo thứ tự tăng bằng phương pháp chọn, Nhập x từ bàn phím kiẻm tra x có trong mảng hay không tải về 2.34 Mb. Chia sẻ với bạn bè của bạn:
|