Tuyên bố vấn đề
Cho một cuốn sách gồm N trang, nhiệm vụ là tính số lần lật trang tối thiểu để có được một trang mong muốn K.
-
chúng ta có thể bắt đầu lật các trang từ mặt trước của cuốn sách (tức là từ trang 1) hoặc từ mặt sau của cuốn sách (tức là số trang N).
-
Mỗi trang có hai mặt, mặt trước và mặt sau, ngoại 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 cuốn 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 chúng ta bắt đầu lật trang từ phía trước thì cần 2 lượt (1) -> (2, 3) -> (4,5)
-
Nếu chúng ta bắt đầu lật trang từ phía sau, (4, 5) 1 lượt là cần lật trang =1
Vì vậy, Số trang tối thiểu được lật =1.
Thuật toán
Sử dụng công thức dưới đây để tính toán kết quả cuối cùng -
1. If K is even, front distance = (K – 0)/2 and back distance = (N – 1 – K)/2 2. If K is odd, front distance = (K – 1)/2 and back distance = (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;
} Đầu ra
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