एम दिनों में एन अध्याय वाले एक पुस्तक को पढ़ने का सबसे अच्छा तरीका

Question

मैं इस साक्षात्कार के प्रश्न में आया: एन अध्यायों के साथ एक पुस्तक (प्रत्येक अध्याय में निश्चित रूप से पृष्ठों की अलग संख्या है), पूरी पुस्तक को पूरा करने का सबसे अच्छा तरीका क्या है एम दिनों में बाधा के साथ कि एक अध्याय को उसी दिन पूरी तरह से पढ़ना है।

उदाहरण:

Chapters[] = {7, 5, 3, 9, 10} 
Days = 4 

एक पढ़ना चाहिए:

Chapter1 on Day1, Chapters2 and Chapter3 on Day2, Chapter4 on Day3 और Chapter5 on Day4।

मैं समझता हूं कि विचार उन पृष्ठों की औसत संख्या के साथ पढ़ने वाले कुल पृष्ठों के पूर्ण मतभेदों को कम करना चाहिए जिन्हें किसी को 'आदर्श' पढ़ना चाहिए। हालांकि, मैं इस विचार को डेटा संरचना और एल्गोरिदम में अनुवाद करने में सक्षम नहीं हूं। कोई अन्य विचार या इनपुट की सराहना की जाती है।

Answer 1

आप गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं।

1. औसत totalNumberOfPages/numberOfDays के बराबर है और यह जिस तरह से हम किताब पढ़ने पर निर्भर नहीं करता।

2. राज्य (हमारे द्वारा समाप्त अध्यायों की संख्या, हमने कितने दिनों पहले ही खर्च किए हैं)। राज्य का मूल्य अब तक पूर्ण मतभेदों का न्यूनतम योग है।

3. बेस केस यदि f(0, 0) = 0 है।

   • मान लेते हैं कि वर्तमान स्थिति (chapters, days) है दो:

   • संक्रमण इस प्रकार हैं।

   • हम हम अगले दिन पढ़ा जाएगा अध्यायों की संख्या से अधिक पुनरावृति कर सकते हैं (मैं इसे add कॉल करेंगे) और निम्न संक्रमण बनाने: f(chapters + add, days + 1) = min(f(chapters + add, days + 1), f(chapters, days) + abs(average - the number of pages in chapter + 1 ... chapter + add chapters).

4. जवाब f(totalNumberOfChapters, totalNumberOfDays) है।

यह समाधान एक धारणा पर आधारित है हमारा लक्ष्य "कुल पृष्ठों की संपूर्ण मतभेद की राशि को कम से कम है कि एक 'आदर्श' एक दिन पर पढ़ना चाहिए पृष्ठों की औसत संख्या के साथ पठित" करने के लिए है कि।

लेकिन अगर समस्या का बयान यह नहीं कहता कि इष्टतमता का मानदंड क्या है, तो मैं एक दिन के दौरान पढ़ने वाले पृष्ठों की अधिकतम संख्या को कम करने का सुझाव दूंगा (मेरी राय में, लक्ष्य भी एक पंक्ति में बहुत ज्यादा नहीं पढ़ता है और अधिक समझ में आता है)। इस मामले में, एक और सरल और कुशल समाधान है: हम जवाब पर बाइनरी खोज सकते हैं और यह जांचने के लिए एक लालची एल्गोरिदम का उपयोग कर सकते हैं कि कोई निश्चित उम्मीदवार संभव है या नहीं।