Đề bài
Cho một cuốn sách N trang, nhiệm vụ là tính số lần lật trang tối thiểu để đến trang mong muốn K.
- Chúng ta có thể bắt đầu lật trang từ mặt trước của sách (tức là từ trang 1) hoặc từ mặt sau của sách (tức là trang số N).
- Mỗi trang có hai mặt, mặt trước và mặt sau, trừ trang đầu tiên chỉ có mặt sau và trang cuối cùng có thể chỉ có mặt sau tùy thuộc vào số trang của sách.
Nếu N = 5 và K = 4 thì chúng ta phải lật tối thiểu 1 trang:
- Nếu bắt đầu lật từ trước thì cần 2 lần lật (1) -> (2, 3) -> (4,5)
- Nếu bắt đầu lật từ sau, (4, 5) chỉ cần 1 lần lật trang = 1
Vậy số trang lật tối thiểu = 1.
Thuật toán
Sử dụng công thức dưới đây để tính kết quả cuối cùng:
1. Nếu K chẵn, khoảng cách từ trước = (K – 0)/2 và khoảng cách từ sau = (N – 1 – K)/2 2. Nếu K lẻ, khoảng cách từ trước = (K – 1)/2 và khoảng cách từ sau = (N – K)/2
Ví dụ
#include <iostream> #include <algorithm> using namespace std; int getMinPageTurns(int n, int k){ if (n % 2 == 0) { ++n; } return min((k + 1) / 2, (n -k + 1) / 2); } int main(){ int n = 5, k = 4; cout << "Required page turns = " << getMinPageTurns(n, k) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Required page turns = 1