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