पायथन में दिए गए मोनोटोनिक अनुक्रम में तत्व की स्थिति खोजें

मान लीजिए कि हमारे पास एक संख्या l और एक मोनोटोनिक बढ़ते क्रम f(m) है, जहां f(m) =am + bm [log2(m)] + cm^3 और (a =1, 2, 3,…), (बी =1, 2, 3,…), (सी =0, 1, 2, 3,…)

यहाँ [log2(m)] आधार 2 का लॉग है और मान को नीचे की ओर गोल करता है। तो,

अगर एम =1, मान 0 है।

अगर एम =2-3, मान 1 है।

अगर एम =4-7, मान 2 है।

अगर एम =8-15, मान 3 है और इसी तरह, पर

हमें m का मान इस प्रकार ज्ञात करना है कि f(m) =l, यदि l अनुक्रम में मौजूद नहीं है तो हमें 0 प्रिंट करना होगा। हमें यह ध्यान रखना होगा कि मान इस तरह से हैं कि उनका प्रतिनिधित्व किया जा सकता है 64 बिट और तीन पूर्णांक a, b और c 100 से कम या उसके बराबर।

इसलिए, यदि इनपुट a =2, b =1, c =1, l =12168587437017 जैसा है, तो आउटपुट 23001 होगा f(23001) =12168587437017

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

SMALLER_VAL :=1000000
LARGER_VAL :=1000000000000000
फ़ंक्शन को हल करें () परिभाषित करें। इसमें a, b, c, n
. लगेगा
उत्तर:=ए * एन
lg_val :=n के लघुगणक आधार 2 का तल
उत्तर:=उत्तर + बी * एन * lg_val
उत्तर:=उत्तर + सी * एन^3
वापसी उत्तर
मुख्य विधि से, निम्न कार्य करें -
शुरू :=1
अंत:=SMALLER_VAL
यदि c, 0 के समान है, तो
- अंत:=LARGER_VAL
उत्तर :=0
प्रारंभ करते समय <=अंत, करें
- मध्य:=(शुरू + अंत) / 2 (केवल पूर्णांक भाग लें)
- वैल:=हल करें (ए, बी, सी, मिड)
- अगर वैल k के समान है, तो
  - उत्तर:=मध्य
  - लूप से बाहर आएं
- अन्यथा जब वैल> के, तब
  - अंत:=मध्य - 1
- अन्यथा,
  - प्रारंभ:=मध्य + 1
वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from math import log2, floor
SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000
def solve(a, b, c, n) :
   ans = a * n
   lg_val = floor(log2(n))
   ans += b * n * lg_val
   ans += c * n**3
   return ans
def get_pos(a, b, c, k) :
   begin = 1
   end = SMALLER_VAL
   if (c == 0) :
      end = LARGER_VAL
   ans = 0
   while (begin <= end) :
      mid = (begin + end) // 2
      val = solve(a, b, c, mid)
      if (val == k) :
         ans = mid
         break
      elif (val > k) :
         end = mid - 1
      else :
         begin = mid + 1
   return ans
a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))

इनपुट

2,1,1,12168587437017