Python में स्केल और वज़न का उपयोग करके आइटम के मापने योग्य होने की जांच कैसे करें?

मान लीजिए हमारे पास a^0, a^1, a^2, ..., a^100 जैसे कुछ वज़न हैं, यहां 'a' एक पूर्णांक है, और हमारे पास एक वेइंग स्केल भी है जहां वज़न को स्केल के दोनों तरफ रखा जा सकता है। हमें यह जांचना है कि वजन W का एक विशेष आइटम इन वज़न का उपयोग करके मापा जा सकता है या नहीं।

तो, यदि इनपुट a = 4, W = 17 है, तो आउटपुट True होगा क्योंकि वज़न a^0 = 1, a^1 = 4, a^2 = 16 हैं, हम 16 + 1 = 17 प्राप्त कर सकते हैं।

हल करने के चरण

found := False
util() फ़ंक्शन परिभाषित करें। यह idx, itemWt, weights, N लेगा
यदि found true है, तो:
- वापस लौटें
यदि itemWt 0 के समान है, तो:
- 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 या तो 2 या 3 है, तो:
- True लौटाएं
weights := आकार 100 की सूची और 0 से भरें
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 है, तो:
- 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