পাইথনে স্কেল এবং কিছু ওজন ব্যবহার করে আইটেমের ওজন মাপা সম্ভব কিনা তা যাচাই করা

মান লিজিয়ে আমাদের কিছু ওজন আছে যেমন a^0, a^1, a^2, ..., a^100, এখানে 'a' একটি পূর্ণসংখ্যা, এবং আমাদের একটি ওজন মাপার স্কেল (weighing scale) আছে যেখানে ওজন দুপাশে রাখা যায়। আমাদের যাচাই করতে হবে একটি নির্দিষ্ট আইটেম যার ওজন W, সেটি এই ওজনগুলো ব্যবহার করে মাপা সম্ভব কিনা।

যেমন, ইনপুট যদি a = 4, W = 17 হয়, তবে আউটপুট হবে True কারণ ওজনগুলো হল a^0 = 1, a^1 = 4, a^2 = 16, আমরা ১৬ + ১ = ১৭ পেতে পারি।

সমাধানের ধাপসমূহ

• found := False
• util() ফাংশন সংজ্ঞায়িত করুন। এটি idx, itemWt, weights, N নেবে
  • যদি found সত্য হয়, তবে:
    • রিটার্ন করুন
  • যদি itemWt ০ সমান হয়, তবে:
    • found := True
    • রিটার্ন করুন
  • যদি idx > N হয়, তবে:
    • রিটার্ন করুন
  • util(idx + 1, itemWt, weights, N)
  • util(idx + 1, itemWt + weights[idx], weights, N)
  • util(idx + 1, itemWt - weights[idx], weights, N)
• মূল মেথড থেকে নিচের কাজ করুন:
  • যদি a ২ বা ৩ হয়, তবে:
    • True রিটার্ন করুন
  • weights := সাইজ ১০০ এর একটি লিস্ট ০ দিয়ে ভরুন
  • total_weights := 0
  • weights[0] := 1, i := 1
  • অনন্ত লুপ করুন:
    • weights[i] := weights[i - 1] * a
    • total_weights := total_weights + 1
    • যদি weights[i] > 10^7 হয়, তবে:
      • লুপ থেকে বের হোন
    • i := i + 1
  • util(0, W, weights, total_weights)
  • যদি found সত্য হয়, তবে:
    • True রিটার্ন করুন
  • False রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

found = False
def util(idx, itemWt, weights, N):
    global found
    if found:
        return
    if itemWt == 0:
        found = True
        return
    if idx > N:
        return
    util(idx + 1, itemWt, weights, N)
    util(idx + 1, itemWt + weights[idx], weights, N)
    util(idx + 1, itemWt - weights[idx], weights, N)

def solve(a, W):
    global found
    if a == 2 or a == 3:
        return True
    weights = [0] * 100
    total_weights = 0
    weights[0] = 1
    i = 1
    while True:
        weights[i] = weights[i - 1] * a
        total_weights += 1
        if weights[i] > 10**7:
            break
        i += 1
    util(0, W, weights, total_weights)
    if found:
        return True
    return False

a = 4
W = 17
print(solve(a, W))

ইনপুট

4, 17

আউটপুট

True