পাইথনে একটি সংখ্যার সর্বাধিক সংখ্যার যৌগিক সমষ্টি খুঁজুন

ধরুন আমাদের একটি প্রদত্ত সংখ্যা N আছে যেটি পরিসরে (1<=N<=10^9), আমাদেরকে সবচেয়ে বড় সম্ভাব্য সংখ্যার সমষ্টি হিসাবে N উপস্থাপন করতে হবে এবং এই বৃহত্তম সংখ্যাটি ফেরত দিন, অন্যথায় যখন আমরা কোনো বিভাজন খুঁজে পাই না, তখন -1 ফেরত দিন।

সুতরাং, যদি ইনপুটটি 16 এর মত হয়, তাহলে আউটপুটটি 4 হবে 16 হিসাবে 4 + 4 + 4 + 4 বা 8 + 8 লেখা যেতে পারে, তবে (4 + 4 + 4 + 4) সর্বাধিক সমমান রয়েছে।

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

max_val :=16
একটি ফাংশন pre_calc() সংজ্ঞায়িত করুন। এটি লাগবে
টেবিল :=max_val আকারের একটি তালিকা, তারপর প্রতিটি অবস্থানে -1 সংরক্ষণ করুন
টেবিল[0] :=0
v :=[৪, ৬, ৯]
1 থেকে max_val রেঞ্জের জন্য, 1 দ্বারা বৃদ্ধি করুন, করুন
- k এর জন্য 0 থেকে 2 রেঞ্জে, করুন
  - j :=v[k]
  - যদি i>=j এবং টেবিল[i - j] -1 না হয়, তাহলে
    - টেবিল[i] :=সর্বোচ্চ টেবিল[i], টেবিল[i - j] + 1
রিটার্ন টেবিল
একটি ফাংশন max_summ() সংজ্ঞায়িত করুন। এটি টেবিল নেবে, n
যদি n
- রিটার্ন টেবিল[n]
অন্যথায়,
- t :=(n - max_val) / 4) + 1
  এর পূর্ণসংখ্যা
- ফিরুন t + টেবিল[n - 4 * t]
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
টেবিল :=pre_calc()
প্রদর্শন max_summ(টেবিল, n)

উদাহরণ

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

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))