समस्या कथन
N पृष्ठों की एक पुस्तक दी गई है, कार्य एक वांछित पृष्ठ K तक पहुंचने के लिए न्यूनतम पृष्ठ मोड़ की गणना करना है।
- हम या तो पुस्तक के सामने से (पृष्ठ 1 से) या पीछे से (पृष्ठ N से) पृष्ठ मोड़ना शुरू कर सकते हैं।
- प्रत्येक पृष्ठ के दो पहलू होते हैं, सामने और पीछे, सिवाय पहले पृष्ठ के जिसमें केवल पीछे का पहलू होता है और अंतिम पृष्ठ जिसमें पृष्ठों की संख्या के आधार पर केवल पीछे का पहलू हो सकता है।
यदि N=5 और K=4, तो न्यूनतम 1 पृष्ठ मोड़ना आवश्यक है:
- सामने से: 2 मोड़ (1) → (2,3) → (4,5)
- पीछे से: (4,5) 1 मोड़
एल्गोरिदम
अंतिम परिणाम की गणना के लिए नीचे दिए गए सूत्र का उपयोग करें:
1. यदि K सम है, तो फ्रंट दूरी = (K - 0)/2 और बैक दूरी = (N - 1 - K)/2 2. यदि K विषम है, तो फ्रंट दूरी = (K - 1)/2 और बैक दूरी = (N - K)/2
C++ उदाहरण
#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