数据结构
网络
关系型数据库管理系统 (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 次浏览
广告