Python中的Heron方法

Question

Heron's method生成一个数字序列，表示√n的更好和更好的近似值。序列中的第一个数字是任意猜测的;序列中的每个其他数量从使用公式先前数分组获得：

(1/2)*(prev+n/prev) 

我应该写一个函数heron()其作为输入两个数字：Ñ和错误。该函数应该以初始猜测1.0为√n开始，然后重复生成更好的近似值，直到连续近似值之间的差值（更确切地说，差值的绝对值）最大为误差。

usage: 
    >>> heron(4.0, 0.5) 
    2.05 
    >>> heron(4.0, 0.1) 
    2.000609756097561 

这是一个有点棘手，但我需要保持四个变量的轨迹：

# n, error, prev and current 

我还需要一个while循环与条件：

((current - prev) > error): 

的一般规则，而循环是：

# old current goes into new prev 

所以这是我走到这一步，这不是多，因为下手我不知道如何把而循环下“如果”声明。

def heron(n, error): 
    guess = 1 
    current = 1 
    prev = 0 
    while (current - prev) > error: 
     previous==1/2*(guess+n/guess): 
      print (previous) # just a simple print statement 
          # in order to see what i have so far 

有人可以给我正确的方向几个指针吗？

谢谢

Answer 1

如果你不想使用发电机那么最简单的将是：

def heron(n, error): 
    prev, new = 1.0, 0.5 * (1 + n) 
    while abs(new - prev) > error: 
     prev, new = new, 0.5 * (new + n/new) 
    return new 

您还可以生成鹭号“无限”序列：

def heron(n): 
    prev = 1.0 
    yield prev, float('inf') 
    while True: 
     new = 0.5 * (prev + n/prev) 
     error = new - prev 
     yield new, error 
     prev = new 

现在您可以随意打印如此多的数字，例如：

list(islice(heron(2), 3))  # First 3 numbers and associated errors 

生成只要误差大于0.01：

list(takewhile(lambda x:x[1] > 0.01, heron(2))) 

Answer 2

只是建立在@ elyase的答案，这里是你将如何得到他们所提供的苍鹭数发生器的任意精度的平方根。（发电机只是给下一个数字在鹭序列）

def heron(n): ### posted by elyase 
    a = 1.0 
    yield a 
    while True: 
     a = 0.5 * (a + n/a) 
     yield a 

def sqrt_heron(n, err): 
    g = heron(n) 
    prev = g.next() 
    current = g.next() 
    while((prev - current) > err): 
     prev = current 
     current = g.next() 
     print current, prev 
    return current 

print sqrt_heron(169.0,0.1) 

除了Python语法，可以搞乱您的事情是，你需要从最初的猜测计算的两张猜测上手，并且你比较这两个猜测有多远。因为我们预计前面的猜测更接近平方（因此更大），而当前猜测应该更接近平方根，所以while条件应该是(prev - current) > err而不是(current - prev) > err。由于初始猜测可能是任何正数，因此我们需要计算两次迭代，以确保current将小于prev。

Answer 3

另一个答案，因为我写这是使用Python生成器函数。我喜欢发电机，但对于这个简单的问题，这些都是过度的。下面，使用简单的while循环的解决方案。

评论下面的代码。 heron0()是你要求的; heron()是我的建议版本。

def heron0(n, error): 
    guess = 1.0 
    prev = 0.0 
    while (guess - prev) > error: 
     prev = guess 
     guess = 0.5*(guess+n/guess) 
     print("DEBUG: New guess: %f" % guess) 
    return guess 

def _close_enough(guess, n, allowed_error): 
    low = n - allowed_error 
    high = n + allowed_error 
    return low <= guess**2 <= high 

def heron(n, allowed_error): 
    guess = 1.0 
    while not _close_enough(guess, n, allowed_error): 
     guess = 0.5*(guess+n/guess) 
     print("DEBUG: New guess: %f" % guess) 
    return guess 

print("Result: %f" % heron0(4, 1e-6)) 
print("Result: %f" % heron(4, 1e-6)) 

评论：

• 你并不真的需要两个guess和current。您可以使用guess来保留当前猜测。

• 我不知道你为什么要在while循环中添加if语句。首先，这很容易：您只需将其放入并缩进在if下的声明。其次，这个问题并不需要它。

• 检测guess是否接近prev很容易且快速。但我认为对于数字精度来说，直接测试平方根实际上有多好会更好。所以，请将guess的值平方，看看是否接近n。看看在Python中如何测试一个值是否同时大于或等于较低值并且小于或等于较高值是合法的。 （另一种检查方法：abs(n - guess**2) <= allowed_error）

• 在Python 2.x中，如果你用整数除整数，你可能会得到一个整数结果。因此1/2很可能有0的结果。有几种方法可以解决这个问题，或者您可以使用Python 3.x来运行程序，该程序保证1/2返回0.5，但将guess的起始值设置为浮点数很容易。

Answer 4

我觉得这符合您的要求（注：我使用Python 2.7.10写的）：它不取1猜测，它需要采取“民”和“宽容”作为“参数n'和'错误'。另外，它不使用变量“prev”和“current”或while循环 - 是你需求的一部分，还是你对解决方案的想法？

def heron(num, guess, tolerance): 
    if guess**2 != num: 
     ##print "guess =", guess 
     if abs(float(num) - float(guess)**2) > float(tolerance): 
      avg_guess = 0.5 * (float(guess) + (float(num)/float(guess))) 
      return heron(num, avg_guess, tolerance) 
     print "Given your tolerance, this is Heron's best guess:", guess 
    else: 
     print guess, "is correct!" 

如果您想查看猜测的进展，取消打印cmd的注释。