Java / Python / Mathematica 中的递归序列

发布于 2024-08-07 19:13:21 字数 356 浏览 2 评论 0原文

如何用给定语言编写以下语句？

a(0) = 1
a_(n+1) = 1 - 1 / ( a_n + 3)

当a_n -> >时，我需要找到n的最小值。 0.732050...。

我在 Mathematica 中的尝试

a[(x+1)_] = 1 - 1/(a[x_] + 3)

问题显然出在这个 a[(x+1)_] 中。但是，我不知道如何在 Mathematica 中迭代执行此操作。

原文

How can you write the following statement in the given languages?

a(0) = 1
a_(n+1) = 1 - 1 / ( a_n + 3)

I need to find the smallest value of n when a_n -> 0.732050....

My attempt in Mathematica

a[(x+1)_] = 1 - 1/(a[x_] + 3)

The problem is apparently in this a[(x+1)_].
However, I do not know how to do it iteratively in Mathematica.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

别忘他 2024-08-14 19:13:21

Mathematica

a[0] = 1;
a[n_] := a[n] = 1 - 1/(a[n-1] + 3)

（注意记忆技巧。）

此外，a[n] 收敛（非常快）到 sqrt(3)-1：

Solve[x == 1 - 1/(x+3), x]

Mathematica

a[0] = 1;
a[n_] := a[n] = 1 - 1/(a[n-1] + 3)

(Note the memoization trick.)

Also, a[n] converges (very quickly) to sqrt(3)-1:

Solve[x == 1 - 1/(x+3), x]

回复收藏 0 原文

岁月苍老的讽刺 2024-08-14 19:13:21

Python，最简单：

def a(n):
  if n == 0: return 1
  return 1 - 1 / float(a(n-1) + 3)

# limit is sqrt(3) - 1
limit = 3.0 ** 0.5 - 1.0

# get 9 digits' precision
i = 0
while abs(a(i) - limit) > 1.0e-9:
  i += 1

print i

这会发出 8，表明递归消除或记忆等优化可能没有必要。

当然，通常我们希望以数值方式而不是分析方式获得极限，因此正常的循环方式会相当不同——并且最好封装在高阶函数中......：

# get a function's limit numerically
def limit(f, eps=1.0e-11):
  previous_value = f(0)
  next_value = f(1)
  i = 2
  while abs(next_value - previous_value) > eps:
    previous_value = next_value
    next_value = f(i)
    i += 1
  return next_value

非平凡的循环逻辑通常最好封装在生成器：

def next_prev(f):
  previous_value = f(0)
  i = 1
  while True:
    next_value = f(i)
    yield next_value, previous_value
    i += 1
    previous_value = next_value

借助此生成器，limit HOF 变得更加简单：

def limit(f, eps=1.0e-11):
  for next_value, previous_value in next_prev(f):
    if abs(next_value - previous_value) < eps:
      return next_value

注意分离的有用性：next_prev 体现了“获取下一个和上一个值”的概念函数”，limit 只是处理“循环何时终止”。

最后但并非最不重要的一点是， itertools 通常为生成器提供了一个很好的替代方案，让您可以封装挑剔的东西快速迭代逻辑（尽管确实需要一些时间来适应......;-）：

import itertools

def next_prev(f):
  values = itertools.imap(f, itertools.count())
  prv, nxt = itertools.tee(values)
  nxt.next()
  return itertools.izip(prv, nxt)

Python, simplest:

def a(n):
  if n == 0: return 1
  return 1 - 1 / float(a(n-1) + 3)

# limit is sqrt(3) - 1
limit = 3.0 ** 0.5 - 1.0

# get 9 digits' precision
i = 0
while abs(a(i) - limit) > 1.0e-9:
  i += 1

print i

This emits 8, suggesting that optimizations such as recursion elimination or memoizing are likely not warranted.

Of course normally we'd want to get the limit numerically rather than analytically, so the normal way to loop would be rather different -- and best encapsulated in a higher-order function...:

# get a function's limit numerically
def limit(f, eps=1.0e-11):
  previous_value = f(0)
  next_value = f(1)
  i = 2
  while abs(next_value - previous_value) > eps:
    previous_value = next_value
    next_value = f(i)
    i += 1
  return next_value

Nontrivial looping logic is usually best encapsulated in a generator:

def next_prev(f):
  previous_value = f(0)
  i = 1
  while True:
    next_value = f(i)
    yield next_value, previous_value
    i += 1
    previous_value = next_value

with the help of this generator, the limit HOF becomes much simpler:

def limit(f, eps=1.0e-11):
  for next_value, previous_value in next_prev(f):
    if abs(next_value - previous_value) < eps:
      return next_value

Note how useful the separation is: next_prev embodies the concept of "get the next and previous value of the function", limit just deals with "when should the loop terminate".

Last but not least, itertools often offers a good alternative to generators, letting you encapsulate finicky iteration logic in speedy ways (though it does take some getting used to...;-):

import itertools

def next_prev(f):
  values = itertools.imap(f, itertools.count())
  prv, nxt = itertools.tee(values)
  nxt.next()
  return itertools.izip(prv, nxt)

回复收藏 0 原文

§普罗旺斯的薰衣草 2024-08-14 19:13:21

JavaPython

double A = 1;
int n = 0;
while (true) {
  System.out.println(n + " " + A);
  A = 1 - 1 / (A + 3);
  n++;
}

A = 1.0
n = 0
while 1:
  print n, A
  A = 1 - 1 / (A + 3)
  n += 1

Java

double A = 1;
int n = 0;
while (true) {
  System.out.println(n + " " + A);
  A = 1 - 1 / (A + 3);
  n++;
}

Python

A = 1.0
n = 0
while 1:
  print n, A
  A = 1 - 1 / (A + 3)
  n += 1

回复收藏 0 原文

尤怨 2024-08-14 19:13:21

Mathematica：

a[0] := 1
a[k_] := 1 - 1/(a[k - 1] + 3)

我用 k = n + 1 代替，因为这使得表达式更简单。结果是等价的。

Mathematica:

a[0] := 1
a[k_] := 1 - 1/(a[k - 1] + 3)

I substituted k = n + 1 because that makes the expression simpler. The result is equivalent.

回复收藏 0 原文

初心 2024-08-14 19:13:21

Python

next = lambda x: 1.0 - (1.0 / (float(x) + 3.0))
last, z, count = -1, 0.0, 0
while last != z:
  print count, z
  last, z, count = z, next(z), count+1

如果可以的话，我会尽量避免写“while True”之类的。几乎可以肯定，我编写的代码不会永远循环。在这种情况下，它为我运行了十六次。十六比 ℵ-null 小很多。

Python

next = lambda x: 1.0 - (1.0 / (float(x) + 3.0))
last, z, count = -1, 0.0, 0
while last != z:
  print count, z
  last, z, count = z, next(z), count+1

I try to avoid writing "while True" or such if I can avoid it. Almost certainly no code that I write will loop forever. In this case, it ran sixteen times for me. Sixteen is a lot less than ℵ-null.

回复收藏 0 原文

够钟 2024-08-14 19:13:21

Mathematica 中的一行给出了序列的精确元素列表：

In[66]:= NestWhileList[1 - 1/(#1 + 3) &, 1, 
 RealExponent[Subtract[##]] > -8 &, 2]

Out[66]= {1, 3/4, 11/15, 41/56, 153/209, 571/780, 2131/2911, \
7953/10864, 29681/40545}

最后两个元素之间的差异小于 10^-8。因此需要 8 次迭代：

In[67]:= Length[%]

Out[67]= 9

A one-liner in Mathematica which gives a list of exact elements of your sequence:

In[66]:= NestWhileList[1 - 1/(#1 + 3) &, 1, 
 RealExponent[Subtract[##]] > -8 &, 2]

Out[66]= {1, 3/4, 11/15, 41/56, 153/209, 571/780, 2131/2911, \
7953/10864, 29681/40545}

The difference between the last two elements is less than 10^-8. It thus have taken 8 iterations: