套汇问题 Python实现，算法设计，DFS深度遍历
# P67
# 套汇问题可以理解为一个有向图找出环的问题，
# 要想有盈利，需要所有的汇率乘积大于1
# 在贪心条件下，找到一个环路径上的乘积大于1就有套汇的可能性
"""
# 输入一个汇率表
b1 b2 b3 b4
b1 k11 k12 k13 k14
b2 k21 k22 k23 k24
b3 k31 k32 k33 k34
b4 k41 k42 k43 k44
所有不支持兑换的币种均设置为 -1 ,
同币种设置为 -1，不考虑同币种之间的兑换
"""
def path_values(rates_, now_rate, path):
"""
:param rates_: 利率表
:param now_rate: 累乘的利率
:param path: 兑换路径，连续两个表示一条路线
:return:
"""
if len(path) >= 2:
return path_values(rates_, now_rate * rates_[path[0]][path[1]], path[1:])
else:
return now_rate
def find_path(rates_, path, start):
"""
:param rates_: 利率表
:param path: 路径
:param start: 路径中最后一个起始点
:return:
"""
from copy import deepcopy
path = deepcopy(path)
if start in path:
# 生成一条兑换路径并计算汇率
path.append(start)
values = path_values(rates_, 1, path)
if values > 1:
print(path, values)
return
# exit() # 仅适用于IDE 环境
path.append(start)
# 如果这个可能的起始点不在路径中则加入路径中
for i in range(len(rates_)):
# 根据最后一个起始点继续寻找路径遍历表
if rates_[start][i] > 0:
find_path(rates_, path, start=i)
def find_values(rates_):
for i in range(len(rates_)):
find_path(rates_, [], i)
rates = [[-1, 0.7, -1],
[-1, -1, 9.5],
[0.16, -1, -1]]
find_values(rates)
输出