資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查N能否表示為從集合{A, B}中選擇的整數之和（Python）
假設我們有一個目標數字。我們還有另外兩個數字A和B。我們必須檢查是否可以透過任意多次新增A和B來獲得目標數字。
因此，如果輸入像目標 = 26，A = 5，B = 7，則輸出為True，因為我們可以透過新增A和B來獲得26，例如 (7 + 7 + 7 + 5)。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式util()。這將接收x、a、b、is_ok和target。
- 如果x > target，則
- 返回。
- 如果is_ok[x]為True，則
- 返回。
- is_ok[x] := True
- util(x + a, a, b, is_ok, target)
- util(x + b, a, b, is_ok, target)
- 在主方法中執行以下操作：
- is_ok := 一個大小為(target + 1)並填充False的陣列
- util(0, a, b, is_ok, target)
- 返回is_ok[target]
示例
讓我們看看下面的實現來更好地理解：
def util(x, a, b, is_ok, target): if x > target: return if is_ok[x]: return is_ok[x] = True util(x + a, a, b, is_ok, target) util(x + b, a, b, is_ok, target) def solve(target, a, b): is_ok = [False] * (target + 1) util(0, a, b, is_ok, target) return is_ok[target] target = 26 A = 5 B = 7 print(solve(target, A, B))
輸入
26, 5, 7
輸出
True
更新於：2021年1月19日
392 次瀏覽
廣告