ข้อความโจทย์
กำหนดหนังสือ N หน้า งานคือคำนวณจำนวนการพลิกหน้าขั้นต่ำเพื่อไปยังหน้าที่ต้องการ K
- เราสามารถเริ่มพลิกหน้าจากด้านหน้าของหนังสือ (คือ จากหน้า 1) หรือจากด้านหลัง (คือ หน้าที่ N)
- แต่ละหน้ามีสองด้าน คือ ด้านหน้าและด้านหลัง ยกเว้นหน้าแรกที่มีแต่ด้านหลัง และหน้าสุดท้ายที่อาจมีแต่ด้านหลัง ขึ้นอยู่กับจำนวนหน้าของหนังสือ
ถ้า N = 5 และ K = 4 แล้วเราต้องพลิกหน้าขั้นต่ำ 1 ครั้ง -
- ถ้าเริ่มจากด้านหน้า ต้อง 2 ครั้ง (1) -> (2, 3) -> (4,5)
- ถ้าเริ่มจากด้านหลัง (4, 5) ต้อง 1 ครั้ง จำนวนหน้าที่พลิก = 1
ดังนั้น จำนวนหน้าที่ต้องพลิกน้อยที่สุด = 1
อัลกอริทึม
ใช้สูตรด้านล่างเพื่อคำนวณผลลัพธ์สุดท้าย -
1. ถ้า K เป็นเลขคู่ ระยะทางจากหน้า = (K - 0)/2 และระยะทางจากหลัง = (N - 1 - K)/2 2. ถ้า K เป็นเลขคี่ ระยะทางจากหน้า = (K - 1)/2 และระยะทางจากหลัง = (N - K)/2
ตัวอย่างโค้ด
#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;
}
ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -
Required page turns = 1
