ধরুন আমাদের একটি প্রদত্ত সংখ্যা 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))
ইনপুট
16
আউটপুট
4