ब्रूट बल के बिना पूर्णांक विभाजन के साथ समीकरण को हल करना

हाल ही में, टोस्टर पर एक सवाल उठाया गया, जिसने मुझे गंभीरता से छुआ। यह एक कार्य में निहित है जिसे मैं यहां कुछ अलग व्याख्या में दूंगा:

एक बार प्रोग्रामरों ने समय पर परियोजना को पारित कर दिया और पुरस्कार प्राप्त किया। जश्न मनाने के लिए, उन्होंने खुद को सोम में फेंक दिया और पूरे पैसे से बीयर खरीदी। उन्होंने उसी दिन सब कुछ पिया, और बीटी ने जारी रखने का फैसला किया, लेकिन अधिक पैसा नहीं बचा था। फिर उन्होंने बोतलें सौंप दीं, कल के बदलाव को जोड़ा, और फिर उन्होंने कल की तरह सब कुछ स्टॉक में डाल दिया। यही बात एसआर और चेत में भी हुई। और पीटी में पैसा बिल्कुल एक बोतल था। सोच - एक बोतल की कीमत याद है, वे कितना कंटेनर ले गए (कीमतें सेंट के बिना थे), और कोई भी नाम नहीं दे सकता था कि मूल रूप से कितना पैसा था। यह परियोजना बड़े पैमाने पर थी, बड़े बोनस - इसलिए यह इसके लायक नहीं है। पीएन में न्यूनतम बजट क्या था ताकि इस तरह से घटनाओं का विकास हो सके?

उस पर तर्क इस प्रकार है


मैं एक समीकरण में आया कि सार इस तरह दिखता है (1):

$$

$$x = a (x // b) + c$$

इस तरह के समीकरणों के समाधान के लिए विस्तृत खोज के बिना एक दृष्टिकोण खोजने की कोशिश करते हुए, मैंने एक घंटे से अधिक समय बिताया, लेकिन अंत में मुझे वास्तव में अद्भुत समाधान मिला , लेकिन पुस्तक के मार्जिन बहुत संकीर्ण हैं ;)

इस मामले में श्रेष्ठता के बारे में भ्रम के बिना, मैं इस प्रक्रिया में प्राप्त खुशी को साझा करना चाहता हूं। अगर किसी को इसके लिए कोई वैकल्पिक तरीका या नाम पता है, तो मुझे बताएं; मैं उन लोगों से आग्रह करता हूं कि वे चर्चा करें, और अधीर लोगों को, मैं आपको बिल्ली के नीचे आमंत्रित करता हूं।

इस रूप में परिणामी समीकरण पर विचार करें (2):

$$

$$(x-c) / a = x // b$$

चूंकि दाईं ओर केवल पूर्णांक मान ले सकते हैं, संपूर्ण अभिव्यक्ति केवल तभी समझ में आती है जब अंश बाईं ओर के हर का एक गुणक होता है। इससे यह स्पष्ट है कि x में c से शुरू होने वाले मान हो सकते हैं और फिर चरण a के साथ ।

तब मैंने समीकरण (1) को दो कार्य माना $$$y1 = x$और $$$y2 = a (x // b) + c$। वे किस तर्क पर प्रतिच्छेद करते हैं, यही समाधान है। उदाहरण के रूप में, मैंने इस तरह से चित्र को प्रदर्शित करने के लिए छोटे पैरामीटर मानों का चयन किया है। तो, एक = 3, बी = 7, सी = 9 दें।


दूसरे फ़ंक्शन की चरणबद्ध प्रकृति के कारण, ग्राफ़ y1 और y2 दो बिंदुओं पर प्रतिच्छेद करता है: X1 = 12 और x2 = 15 के लिए, लेकिन स्थिति के अनुसार, हम पहले मान में रुचि रखते हैं, जितना छोटा। इसलिए, बिना किसी विस्तृत खोज के चौराहे के क्षेत्र को निर्धारित करने के लिए, मैंने एक तीसरा फ़ंक्शन पेश किया - यह सिर्फ एक सीधी रेखा है जो फ़ंक्शन y2 को नीचे से सीमित करती है और इसमें समीकरण है $$$y3 = a / b (x - (b-1)) + c$।

अब यह दो लाइनों ( y1 और y3 ) के प्रतिच्छेदन बिंदु को खोजने और वांछित एक्स पर प्रतिबंध से उत्तर को समायोजित करने के लिए बनी हुई है। दरअसल, स्थिति के आधार पर, यह केवल उन मूल्यों को ले सकता है, जिन पर अंश के गुणक की स्थिति समीकरण (2) में हर के लिए संतुष्ट होती है, अर्थात। $$$x = c + na$, जहां n एक निश्चित प्राकृतिक कारक है। ऐसा करने के लिए, हम एक सरल समीकरण हल करते हैं $$$x = a / b (x - (b-1)) + c$और यदि परिणामी रूट हमारी आवश्यकताओं को पूरा नहीं करता है, तो हम इसे निकटतम उपयुक्त में स्थानांतरित करेंगे। चूंकि सहायक फ़ंक्शन y3 में एक सकारात्मक ढलान है, और y2 के सभी मूल्य इसके ऊपर हैं, रूट को हमेशा ऊपर की ओर समायोजित किया जाना चाहिए। तो, हमारे मामले में, लाइनें x = 11.25 (ग्राफ़ पर काली बिंदी) पर अंतर करती हैं, और स्थिति को संतुष्ट करने वाला निकटतम बड़ा मान 12 (लाल बिंदु) है, जिसका उत्तर है।

चूंकि टोस्टर पर सवाल में एक पायथन टैग था, इसलिए नीचे मैं फ़ंक्शन का उपयोग करके इस समस्या को हल करने के लिए एक स्क्रिप्ट दूंगा, अगले दिन के बजट के आधार पर वर्तमान दिन का बजट खोजने के लिए। हम फ़ंक्शन को आवश्यक संख्या में लागू करते हैं और, वॉइला, हमें जवाब मिलता है!

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) 

निष्कर्ष के बजाय:

इस उदाहरण में कार्य को पैरामीटर मान के रूप में निर्धारित किया गया था $$$a <b <c <x$, और समीकरण ही $$$x = a (x // b) + c$; मामूली बदलाव के साथ प्रस्तावित दृष्टिकोण अन्य समान मामलों में लागू होता है - प्रकाशन का उद्देश्य केवल सामान्य मामले के लिए एक सार्वभौमिक समाधान प्राप्त किए बिना सिद्धांत का वर्णन करना था - इसलिए, सख्ती से न्याय न करें (पायथन कोड, incl।), और एक अच्छा शुक्रवार है!