「DA:subsetsum bruteforce」の版間の差分
ナビゲーションに移動
検索に移動
| (同じ利用者による、間の5版が非表示) | |||
| 1行目: | 1行目: | ||
= 全探索（再帰関数で実装）を用いて部分和問題を解くPythonプログラム = | = 全探索（再帰関数で実装）を用いて部分和問題を解くPythonプログラム = | ||
配列numbersのいくつかの要素を取り出して，それらの和が target と同じ値になる組み合わせを見つけると，"YES"と表示するプログラムです．また，numbersの長さとその時にかかった計算時間を最後に表示します． | |||
numbers = [1, 3, 4, 5, 8 | import time | ||
numbers = [1, 3, 4, 5, 8] | |||
def solve(x, i=0): | def solve(x, i=0): | ||
| 11行目: | 13行目: | ||
print("YES") | print("YES") | ||
solve(x - numbers[i], i+1) | solve(x - numbers[i], i+1) | ||
solve(x, i+1) | |||
t = time.time() | |||
W = 8 | |||
solve(W) | |||
print('N (length of numbers):', len(numbers)) | |||
print(time.time() - t, 'sec') | |||
2025年4月9日 (水) 06:05時点における最新版
全探索（再帰関数で実装）を用いて部分和問題を解くPythonプログラム
配列numbersのいくつかの要素を取り出して，それらの和が target と同じ値になる組み合わせを見つけると，"YES"と表示するプログラムです．また，numbersの長さとその時にかかった計算時間を最後に表示します．
import time
numbers = [1, 3, 4, 5, 8]
def solve(x, i=0):
if i == len(numbers):
return
if x - numbers[i] == 0:
print("YES")
solve(x - numbers[i], i+1)
solve(x, i+1)
t = time.time()
W = 8
solve(W)
print('N (length of numbers):', len(numbers))
print(time.time() - t, 'sec')