Python数字线群集练习 [英] Python number line cluster exercise

问题描述

我正在我的教科书（Ex 4.7）中练习，并在Python中实现代码以练习动态编程。我在执行算法4.8时遇到了一些麻烦。我知道发生了什么，直到我到达否则，范围 s 从 1 到 t -1 并将 s 设置为最小化 f（s）。为什么这本书在for循环中使用 s 并将其设置为功能 f（s）？如何在Python中实现这一行？

I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in 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)

非常感谢您的帮助！

推荐答案

该算法非常好。我的代码如下。

The algorithm is very good. My code is as follow.

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])

建议：
如果不了解算法，则可以手动运行便条纸，也许您会弄清楚它是如何工作的。

A advice : When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.

这篇关于Python数字线群集练习的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！