3

我想编写一个 Mathematica 函数，该函数构造一个包含所有小于 n 的斐波那契数的列表。此外，我想尽可能优雅和功能性地做到这一点（所以没有明确的循环）。

从概念上讲，我想获取一个无限的自然数列表，将 Fib[n] 映射到它上面，然后从这个列表中获取小于 n 的元素。我怎样才能在 Mathematica 中做到这一点？

4

4 回答 4

3

第一部分可以在Mathematica中相当容易地完成。下面，我提供了两个函数nextFibonacci，它提供了下一个大于输入数字的斐波那契数（就像NextPrime）和fibonacciList，它提供了一个小于输入数字的所有斐波那契数的列表。

ClearAll[nextFibonacci, fibonacciList]
nextFibonacci[m_] := Fibonacci[
    Block[{n}, 
        NArgMax[{n, 1/Sqrt[5] (GoldenRatio^n - (-1)^n GoldenRatio^-n) <= m, n ∈ Integers}, n]
    ] + 1
]
nextFibonacci[1] := 2;

fibonacciList[m_] := Fibonacci@
    Range[0, Block[{n}, 
      NArgMax[{n, 1/Sqrt[5] (GoldenRatio^n - (-1)^n GoldenRatio^-n) < m, n ∈ Integers}, n]
    ]
]

现在您可以执行以下操作：

nextfibonacci[15]
(* 21 *)

fibonacciList[50]
(* {0, 1, 1, 2, 3, 5, 8, 13, 21, 34} *)

但是，第二部分很棘手。您正在寻找的是 Haskell 类型的惰性评估，它只会在必要时评估（否则，您无法在内存中保存无限列表）。例如，类似（在 Haskell 中）：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

然后允许您执行以下操作

take 10 fibs
-- [0,1,1,2,3,5,8,13,21,34]

takeWhile (<100) fibs
-- [0,1,1,2,3,5,8,13,21,34,55,89]

不幸的是，没有对您想要的内容的内置支持。但是，您可以扩展Mathematica以实现惰性样式列表，如本答案所示，它也作为包实现。现在你已经拥有了你需要的所有部分，我会让你自己处理这个。

于 2012-12-28T18:40:20.117 回答
3

如果你从 GitHub获取我的Lazy 包，你的解决方案很简单：

Needs["Lazy`"]
LazySource[Fibonacci] ~TakeWhile~ ((# < 1000) &) // List

如果您想稍微从字面上实现您的原始描述

从概念上讲，我想获取一个无限的自然数列表，将 Fib[n] 映射到它上面，然后从这个列表中获取小于 n 的元素。

你可以这样做：

Needs["Lazy`"]
Fibonacci ~Map~ Lazy[Integers] ~TakeWhile~ ((# < 1000) &) // List

为了证明这完全是惰性的，请尝试前面没有// List结尾的示例。你会看到它以（相当丑陋的）形式停止：

LazyList[First[ 
  LazyList[Fibonacci[First[LazyList[1, LazySource[#1 &, 2]]]], 
   Fibonacci /@ Rest[LazyList[1, LazySource[#1 &, 2]]]]], 
 TakeWhile[
  Rest[LazyList[Fibonacci[First[LazyList[1, LazySource[#1 &, 2]]]], 
    Fibonacci /@ Rest[LazyList[1, LazySource[#1 &, 2]]]]], #1 < 
    1000 &]]

这包括一个LazyList[]表达式，其第一个元素是您正在延迟评估的表达式的第一个值，其第二个元素是有关如何继续扩展的指令。

改进

一直不停地调用有点低效Fibonacci[n]，尤其是当n开始变大时。实际上可以构造一个惰性生成器，它会在我们流式传输时计算斐波那契数列的当前值：

Needs["Lazy`"]

LazyFibonacci[a_,b_]:=LazyList[a,LazyFibonacci[b,a+b]]
LazyFibonacci[]:=LazyFibonacci[1,1]

LazyFibonacci[] ~TakeWhile~ ((# < 1000)&) // List

最后，我们可以将其推广到一个更抽象的生成函数，它为累加器获取初始值，a Listof Rules 用于计算下一步的累加器值，a Listof Rules 用于根据当前累加器值计算结果。

LazyGenerator[init_, step_, extract_] := 
 LazyList[Evaluate[init /. extract], 
  LazyGenerator[init /. step, step, extract]]

并且可以使用它来生成斐波那契数列，如下所示：

LazyGenerator[{1, 1}, {a_, b_} :> {b, a + b}, {a_, b_} :> a]
于 2012-12-28T23:24:29.170 回答
1

好的，我希望我理解了这个问题。但请注意，我不是纯数学专业的，我是机械工程专业的学生。但这听起来很有趣。所以我查了公式，这就是我现在能想到的。我必须运行，但如果有错误，请告诉我，我会修复它。

这个操作要求n然后列出所有小于 n 的斐波那契数。没有循环可以找到小于 的斐波那契数n。它用于Reduce求解小于 的斐波那契数n。我接受了结果的底限，还扔掉了一个常数，该常数在解决方案中产生了一个复数乘数。

Fibonacci然后使用 Mathematica命令简单地制作所有这些数字的表格。所以如果你输入n=20它会列出1,1,2,3,5,8,13等等。由于内存不足（我的电脑上只有 8 GB 内存），我可以无限执行此操作。

我将限制n随意500000编辑和更改代码。

数学图形

Manipulate[
 Module[{k, m}, 
  k = Floor@N[Assuming[Element[m, Integers] && m > 0, 
        Reduce[f[m] == n, m]][[2, 1, 2]] /. Complex[0, 2] -> 0];
  TableForm@Join[{{"#", "Fibonacci number" }}, 
    Table[{i, Fibonacci[i]}, {i, 1, k}]]
  ],

  {{n, 3, "n="}, 2, 500000, 1, Appearance -> "Labeled", ImageSize -> Small}, 
  SynchronousUpdating -> False, 
  ContentSize -> {200, 500}, Initialization :>
  {
   \[CurlyPhi][n_] := ((1 + Sqrt[5])/2)^n;
   \[Psi][n_] := -(1/\[CurlyPhi][n]);
   f[n_] := (\[CurlyPhi][n] - \[Psi][n])/Sqrt[5];
   }]

截屏

数学图形

于 2012-12-28T17:28:08.320 回答
0

k=Floor[Log[GoldenRatio,Fk]*Sqrt[5]+1/2]]斐波那契数 Fk的 索引 k 是https://en.wikipedia.org/wiki/Fibonacci_number。因此，小于或等于n 的斐波那契数列是

 FibList[n_Integer]:=Fibonacci[Range[Floor[Log[GoldenRatio,Sqrt[5]*n+1/2]]]]
于 2013-02-20T01:09:03.730 回答