Thuật toán
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| algorithm/ˈælɡərɪθəm/ | thuật toán |
| flowchart/ˈfləʊtʃɑːt/ | sơ đồ khối |
| pseudocode/ˈsuːdəʊkəʊd/ | giả mã |
| tracing/ˈtreɪsɪŋ/ | theo dõi |
| binary search/ˈbaɪnəri sɜːtʃ/ | tìm kiếm nhị phân |
| linear search/ˈlɪnɪə sɜːtʃ/ | tìm kiếm tuyến tính |
| efficiency/ɪˈfɪʃənsi/ | hiệu suất |
Nêu rõ các đầu vào mà thủ tục phải xử lý
- Một thuật toán mô tả các bước không mơ hồ cho một nhiệm vụ. Một thủ tục giải quyết một nhiệm vụ hữu hạn được nêu cụ thể phải kết thúc và đưa ra kết quả chính xác cho mọi đầu vào được phép.
- Một thuật toán mô tả các bước không mơ hồ cho một nhiệm vụ. Một thủ tục giải quyết một nhiệm vụ hữu hạn đã nêu phải kết thúc và đưa ra kết quả chính xác cho mọi đầu vào được phép.
Những yếu tố nào bắt buộc để một chuỗi các bước trở thành thuật toán? Chọn tất cả áp dụng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Một thủ tục giải quyết nhiệm vụ hữu hạn được nêu cần các bước không mơ hồ, kết quả chính xác và kết thúc trên các đầu vào được phép. Pseudocode và sơ đồ khối là các biểu diễn, không phải là yêu cầu sử dụng một ngôn ngữ lập trình cụ thể.
Thể hiện sự lựa chọn và cập nhật một cách rõ ràng
- Một sơ đồ khối sử dụng hình thoi quyết định, hình chữ nhật quá trình, hình bình hành input/output và terminal bắt đầu/kết thúc, được kết nối bằng các mũi tên luồng có hướng.
- Một sơ đồ lưu đồ sử dụng hình thoi quyết định, hình chữ nhật quy trình, hình bình hành nhập/xuất và điểm bắt đầu/kết thúc, được kết nối bởi các mũi tên dòng chảy có hướng.
Nối mỗi hình dạng flowchart với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Sử dụng hình chữ nhật quy trình, kim cương quyết định và các đầu cuối bắt đầu/dừng như đã cho; đầu vào/đầu ra thường được hiển thị bằng hình bình hành. Gán nhãn các nhánh quyết định và hướng dòng chảy.
Ghi lại các giá trị biến thực tế
- Ghi chú đường đi (tracing) tuân theo các cập nhật được nêu theo thứ tự. Một biến tạm thời có thể giữ nguyên một giá trị mà nếu không sẽ bị ghi đè lên.
- Vẽ đường dẫn tuân theo thứ tự các cập nhật đã nêu. Một biến tạm có thể giữ lại một giá trị nếu không sẽ bị ghi đè.
Một quy ước tìm kiếm nhị phân được quy định. Sử dụng cận bao gồm dựa trên chỉ số từ 0 và làm tròn xuống của trung bình cộng để lấy chỉ số giữa. Tìm kiếm 7 trong [1,3,5,7,9,11] so sánh chỉ số 2/giá trị 5, chỉ số 4/giá trị 9, sau đó chỉ số 3/giá trị 7. Số lần so sánh là ba dưới quy ước này.
Tuyến tính so với tìm kiếm nhị phân
Chia đôi thắng việc kiểm tra từng bước một, và khoảng cách widening khi danh sách tăng lên.
Sử dụng cận bao gồm zero-based và floor((low+high)/2), tìm kiếm nhị phân sử dụng bao nhiêu phép so sánh để tìm số 7 trong [1,3,5,7,9,11]?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Các chỉ số giữa là 2, 4, sau đó là 3, với các giá trị 5, 9 và 7. Ba phép so sánh theo quy ước được chỉ định.
So sánh công việc dựa trên các giả định của nó
- Tìm kiếm tuyến tính có thể dừng sớm nhưng có thể cần kiểm tra tất cả n mục. Tìm kiếm nhị phân liên tục chia đôi khoảng tìm kiếm đã sắp xếp và cần các cập nhật cận nhất quán.
- Tìm kiếm tuyến tính có thể dừng sớm nhưng có thể xem xét tất cả n mục. Tìm kiếm nhị phân liên tục chia đôi phạm vi tìm kiếm đã sắp xếp và cần cập nhật giới hạn nhất quán.
Đối với danh sách một triệu mục đã được sắp xếp sẵn, khoảng bao nhiêu phép so sánh giá trị giữa có thể cần thiết cho tìm kiếm nhị phân trong trường hợp xấu nhất?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi phép so sánh làm giảm một nửa phạm vi tìm kiếm còn lại; khoảng 20 phép so sánh là đủ cho một triệu mục đã được sắp xếp. Điều này không bao gồm bất kỳ chi phí sắp xếp trước đó.
Tìm kiếm nhị phân hoạt động trên danh sách chưa sắp xếp, chỉ chậm hơn thôi.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Không có thứ tự bắt buộc, việc loại bỏ một nửa có thể bỏ sót một mục đang tồn tại. Một số trường hợp có thể tình cờ thành công, nhưng tính đúng đắn không được đảm bảo.
Kiểm tra chỉ số 0 và chỉ số cuối cùng được phép. Bảng 4.4 xem xét một vòng lặp tổng sử dụng i nhỏ hơn n, điều này bỏ sót hạng tử cuối cùng. Đường đi Euclid của nó cũng giải thích việc kết thúc: mỗi ước số dương được thay thế bởi một phần dư không âm nhỏ hơn cho đến khi đạt được số 0.