資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用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
更新於：2021年1月19日
215 次瀏覽
廣告