【AtCoder】「ABC 045 C たくさんの数式」の再帰の解き方について

Question

下記のatcoder の45c問題ですが、
https://atcoder.jp/contests/abc045/tasks/arc061_a

再帰処理で解く前提で、
プラスの位置により計算結果
を変えたいという問題です。

分岐
return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

のところの挙動がどのようになっているか
仕組みを教えて頂きたいです。

ソースコード

def dfs(i, f):

if i == n - 1:
    return sum(list(map(int, f.split("+")))
分岐
return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

s = input()
n = len(s)
print(dfs(0, s[0]))

Answer 1

質問は、文法とかではなくてアルゴリズムを知りたいということと理解しました。

アルゴリズムを説明して貰っても、分からないものはわからないことが多いです。

従って、答えではなく、分からないときに調べる方法を書いておきます。

適当なところにprint文を入れて、その出力を見て何が起きているかを考えることです。

以下の例を見て、あとは自分で考えてください。

>>> def dfs(i, f):
...     print(f'i = {i}, f = {f}')
...     if i == n - 1:
...         return sum(list(map(int, f.split("+"))))
...     return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])
...
>>> s = input()
125
>>> n = len(s)
>>> print(dfs(0, s[0]))
i = 0, f = 1
i = 1, f = 12
i = 2, f = 125
i = 2, f = 12+5
i = 1, f = 1+2
i = 2, f = 1+25
i = 2, f = 1+2+5
176

Comments

[mk_script]

ご回答ありがとうございます。
じっくり考えてみます。

Answer 2

Python はインデントが重要です。
teratail のヘルプでコードの投稿の仕方を調べてください。
コンパイル可能なコードを提示してください。
質問のコードは、括弧の対応が取れていなかったり、
「分岐」という文字があってコンパイルできません。

def dfs(i, f):
	if i == n - 1:
		return sum(list(map(int, f.split("+"))))
	return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

s = input()
n = len(s)
print(dfs(0, s[0]))

実行のトレース

s = "125"
n = 3
dfs(0, "1")
    return dfs(1, "12") + dfs(1, "1+2")

	dfs(1, "12")
		return dfs(2, "125") + dfs(2, "12+5")

		dfs(2, "125")
			return sum(list(map(int, "125".split("+"))))

		dfs(2, "12+5")
			return sum(list(map(int, "12+5".split("+"))))

	dfs(1, "1+2")
		return dfs(2, "1+25") + dfs(2, "1+2+5")

		dfs(2, "1+25")
			return sum(list(map(int, "1+25".split("+"))))

		dfs(2, "1+2+5")
			return sum(list(map(int, "1+2+5".split("+"))))

Comments

[mk_script]

ご回答ありがとうございます。
投稿の仕方から調べます。