python - Python数轴集群练习
问题描述
我正在完成我的教科书(Ex 4.7)中的一个练习,并正在用 Python 实现代码来练习动态编程。我在实际执行算法 4.8 时遇到了一些麻烦。我明白发生了什么,直到我到达“否则范围s
从1
tot-1
并设置s
为最小化” f(s)
。为什么这本书s
在 for 循环中使用以及将其设置为函数f(s)
?应该如何在 Python 中实现这一行?
[当前代码在底部]
到目前为止,我当前的代码是这样的:
x = [1,2,5,6,10]
k = 3
n = 5
r = [[0 for x in range(k)] for x in range(n)]
c = [[0 for x in range(k)] for x in range(n)]
def Union(lst1, lst2):
final_list = lst1 + lst2
return final_list
for j in range(k):
for t in range(n):
if j == 0:
r[t][j] = (x[t]-x[0])/2
c[t][j] = [(x[t]+x[0])/2]
else:
for s in range(t-1):
f = max(r[s][j-1], (x[t]-x[s+1])/2)
#set s to minimize f??
r[t][j] = f
w = []
w.append((x[t]+x[s+1])/2)
if c[s][j-1] == 0:
c[t][j] = w
else:
c[t][j] = Union(c[s][j - 1], w)
print(r)
print(c)
任何帮助深表感谢!
解决方案
算法非常好。我的代码如下。
x = [1,2,5,6,10]
k = 3
n = 5
r = [[[] for _ in range(k)] for _ in range(n)]
c = [[[] for _ in range(k)] for _ in range(n)]
def f(s, j_down, t):
return max(r[s][j_down], (x[t]-x[s+1])/2.)
def get_min_f_and_s(j_down, t):
""" range s from 1 to t-1 and set s to minimize f(s)
for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
And r[5][j] = f(2).
"""
items = [(s, f(s, j_down, t))for s in range(t)]
s, min_f = min(items, key=lambda x:x[1])
return s, min_f
for j in range(k):
if j == 0:
for t in range(n):
for t in range(n):
r[t][j] = (x[t]-x[0])/2.0
c[t][j] = [(x[t]+x[0])/2.0]
else:
for t in range(1, n):
s, min_f = get_min_f_and_s(j-1, t)
r[t][j] = min_f
c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]
print(r[-1][-1])
print(c[-1][-1])
一个建议:不懂算法的时候,你可以在草稿纸上手动运行它,也许你会弄清楚它是如何工作的。
推荐阅读
- powershell - 从 Windows 托盘生成 PowerShell 管理控制台
- php - openweather unix datetimestamp to local datetime in php
- javascript - Selenium 点击每个 html 一个标签
- terraform - 使用 Terraform 在 Azure 应用程序洞察 Web 测试中创建警报
- reactjs - 如何将 json 正文添加到我的 axios 发布请求中?
- excel - 循环浏览文件夹中的文件,如果语句为假一次,代码会中断
- excel - 如何在公式中使用字符串?
- azure - 如何使用 Azure DevOps 将 Asp.net Web 表单网站部署到 Azure Web App 服务?
- javascript - 对象已排序,但未使用 lodash sortBy 保留其键
- c++ - Visual Studio 2019 中的 Intellisense 延迟