পাইথনের একটি রাস্তায় সমস্ত ঘর আলোকিত করার জন্য সর্বনিম্ন ব্যাসার্ধ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা রয়েছে যা 1-মাত্রিক রেখায় বাড়ির অবস্থানকে প্রতিনিধিত্ব করছে। এখন বিবেচনা করুন আমাদের কাছে 3টি রাস্তার আলো রয়েছে যা আমরা লাইনের যে কোনও জায়গায় রাখতে পারি এবং x অবস্থানের একটি আলো সমস্ত ঘরকে আলোকিত করে [x - r, x + r], সহ। সমস্ত ঘর আলোকিত করার জন্য আমাদের সবচেয়ে ছোট r খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি nums =[4,5,6,7] এর মত হয়, তাহলে আউটপুট হবে 0.5, যেমন আমরা 4.5, 5.5 এবং 6.5-এ ল্যাম্প রাখতে পারি তাই r =0.5। তাই এই তিনটি আলো 4টি ঘর আলোকিত করতে পারে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন বৈধ() সংজ্ঞায়িত করুন। এটি r

  লাগবে

• last_location :=nums[0] + r

• গণনা :=1

• আমি 0 থেকে সংখ্যার আকারের মধ্যে, কর

  • val :=সংখ্যা[i]

  • যদি val - last_location> r, তারপর

    • গণনা :=গণনা + 1

    • last_location :=val + r

• গণনা <=3 হলে true ফেরত দিন, অন্যথায় মিথ্যা

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• তালিকার সংখ্যাগুলি সাজান

• বাম :=0

• ডান :=সংখ্যার শেষ উপাদান

• res :=inf

• itr :=0

• যখন বামে <=ডান এবং এটির <20, করুন

  • মধ্য :=বাম +(ডান - বাম) / 2

  • যদি বৈধ(মধ্য) সত্য হয়, তাহলে

    • res :=ন্যূনতম রেস এবং মিড

    • ডান :=মধ্য

  • অন্যথায়,

    • বাম :=মধ্য

    • itr :=itr + 1

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, nums):
      def valid(r):
         last_location = nums[0] + r
         count = 1
         for i in range(len(nums)):
            val = nums[i]
            if val - last_location > r:
               count += 1
               last_location = val + r
         return count <= 3
      nums.sort()
      left = 0
      right = nums[-1]
      res = float("inf")
      itr = 0
      while left <= right and itr < 20:
         mid = left + (right - left) / 2
         if valid(mid):
            res = min(res, mid)
            right = mid
         else:
            left = mid
         itr += 1
      return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))

ইনপুট

[4,5,6,7]

আউটপুট

0.5