标签: fibonacci

我正在阅读一本编程书,其中一个例子是关于斐波纳契数,以及一个重复函数如何找到第n个的斐波纳契数.

代码如下所示:

Int fib (int n)
{
If (n<3)
Return (1);
Else
Return (fib(n-1))+(fib(n-2))
}

现在这不完全正确,因为我正在通过手机输入并且我理解代码是如何工作的,它会调用自身直到它返回1,然后它会将返回值相加,直到您拥有正确的位置斐波那契数字为止顺序.

所以我不需要代码的帮助.我需要帮助的是理解为什么这有效.如何添加所有回报给出正确的答案？

请有人解释为什么这有效.谢谢.这让我很生气.

这种逻辑编程实际上是在我的命令式编程技巧上跳舞.这是家庭作业,所以请不要给我答案.这就是我所拥有的:

fibo(N,1) :-
   N < 2,
   !. 
fibo(N,R) :-
   N1 is N-1,
   N2 is N-2,
   fibo(N1,R1),
   fibo(N2,R2),
   R is R1+R2.

我想要制作另一个看起来像这样的功能; fib(N,Value,LastValue). N是第n个数字,值是返回值.我不明白我怎么能用累积重写这个.而且由于它向后计数,我不知道它在计算任何东西之前如何"知道"最后一个值.:s任何输入表示赞赏.

我有一个正在进行的调查Fibonacci序列的项目,这只是一个个人项目,我创建了一个二进制文件tree class,它创建了Fibonacci调用图的二叉树,所以f(3)我生成了树:

我想创建一个tree class get_partitions()遍历树的方法来生成分区root value,我在这里看到的顺序不同的顺序作为不同的分区; 所以对于这里的例子f(3),该get_partitions()方法将遍历树并产生:

Partion 1: 2,1
Partion 2: 2,1,0
Partion 3: 1,1,1
Partion 4: 1,1,1,0
Partion 5: 1,0,1,1
Partion 6: 1,0,1,1,0

最后,我想列举Fibonacci数的每个排列root value,在这种情况下3,对于Partition 1枚举的分区将是(2,1),(1,2),或者Partion 2将被枚举(2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2),等等......

[编辑1]我关心的是Partion 4,并Partion 5在这方面的例子如列举这些partions的所有组合会产生重复 partions.

给定的组合数量root value会产生加泰罗尼亚数字是否正确？

我Tree class是:

class FibTree(object):
"""Class which builds binary tree from …

我对Haskell很陌生,我试图围绕Fibonacci序列的懒惰表达如何工作.

我知道之前已经问过这个问题,但是没有一个答案解决了我在查看结果时遇到的问题.

代码是使用的规范 zipWith

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

我理解以下内容:

1. zipWith 字面上将两个列表拉到一起
2. tail 抓取除列表的第一个元素之外的所有元素
3. Haskell将'to-be'计算数据引用为thunks.

从我的理解,它首先添加[0,1,<thunk>]和[1,<thunk>]使用zipWith (+)给予[1,<thunk>].所以现在你有

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

我用谷歌搜索过的很多参考文献都开始将上面的线"可视化"为

fibs = 0 : 1 : 1 : zipWith (+) [1,1,<thunk>] ([1,<thunk>]).

我的问题是:

为什么 fibs 上面一行中 的组件只对应[1,1,<thunk>] 而不是 [0,1,1,<thunk>]？

不应该fibs包含整个列表加<thunk>？

我的空间泄漏发生在我的一个个人项目中.但我不希望有人在我的项目中解决它.我想了解它.

我通过编写这个算法来重现我的空间泄漏:

u是由以下定义的序列:

• u(0)= 1
• 你(1)= 2
• 你(2)= 1
• 你(4)= 3
• ...
• 你(19)= 11

在此之后,定义u:u(n)= u(n-5)+ u(n-10) - u(n-15)

在haskell中易于实现吗？

import System.Environment (getArgs)

u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
        ++ zipWith3 go u' u'' u'''
    where u' = drop 15 u
          u'' = drop 10 u
          u''' = drop 5 u
          go a b c = a + b - c

main = do …

我有一个Fibonacci可以用作任何一个迭代器实现结构One,Zero,Add和Clone.这适用于所有整数类型.

我想将这个结构用于BigInteger使用a实现Vec并且调用昂贵的类型clone().我想Add在两个引用上T使用然后返回一个新的T(然后没有克隆).

对于我的生活,我不能制作一个虽然编译的...

工作:

extern crate num;

use std::ops::Add;
use std::mem;
use num::traits::{One, Zero};

pub struct Fibonacci<T> {
    curr: T,
    next: T,
}

pub fn new<T: One + Zero>() -> Fibonacci<T> {
    Fibonacci {
        curr: T::zero(),
        next: T::one(),
    }
}

impl<'a, T: Clone + Add<T, Output = T>> Iterator for Fibonacci<T> {
    type Item = T;

    fn next(&mut …

过去几天我一直在努力更好地理解计算复杂性以及如何改进Python代码.为此,我尝试了不同的函数来计算Fibonacci数,比较如果我进行小的更改,脚本运行的时间.

我正在使用列表计算斐波那契数字,从列表中添加元素-2和-1的总和.

我很困惑地发现,如果我在循环中添加.pop(),删除列表中不需要的元素,我的脚本运行得更快.我不明白为什么会这样.循环中的每一步计算机都会做一件事.所以我未经训练的直觉表明这会增加计算时间.当列表很长时,"查找"列表的最后一个元素会慢得多吗？

这是我的代码:

import time
import numpy as np

def fib_stack1(n):
    """ Original function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
        return stack[-1]

def fib_stack2(n):
    """ Modified function """
    assert type(n) is int, 'Expected an integer as input.'
    if n < 2:
        return n
    else:
        stack = [0, 1]
        for i in range(n-1):
            stack.append(stack[-1] + stack[-2])
            ### CHANGE …

在 Abelson/Sussman 的经典著作《计算机程序的结构和解释》中，在有关树递归和斐波那契数列的第 1.2.2 节中，他们展示了这个图像：

计算第五个斐波那契数时生成的树递归过程

然后他们写道：“请注意，整个计算(fib 3)（几乎一半的工作）是重复的。事实上，不难证明该过程将计算的次数(fib 1)或(fib 0)（上述树中的叶子数，在一般）正是Fib(n + 1)。”

我知道他们正在阐述树递归的观点，以及斐波那契树递归的经典案例如何效率低下，因为递归函数调用自身两次：

用于计算斐波那契数的树递归函数

我的问题是，为什么叶子的数量等于序列中的下一个斐波那契数是显而易见的（即“不难证明”） ？我可以直观地看到情况确实如此，但我没有看到为什么叶数（减少的向下fib 1和fib 0计算）应该是下一个斐波那契数的指标（在本例中为 8，即斐波那契数）之间的联系6，即第6个斐波那契数，即Fib n+1，其中n为5）。

很明显斐波那契数列是如何计算的 - 序列中前两个数字的总和产生当前数字，但为什么叶子的数量恰好等于序列中的下一个数字？那里有什么联系（除了明显的联系之外，事实上，在这种情况下，查看它并将 1 和 0 叶相加确实会产生总计数 8，这是下一个（第 6 个）斐波那契数，等等在）？

我不一定要找答案,但我正在寻找这个问题的要求.发现这个问题正在学习面试,但不确定他们在问什么？

编写通过斐波那契序列运行并返回传递作为参数的指数函数.

我试图用F序模仿Haskell在F#中着名的无限斐波纳契列表.为什么以下序列没有按预期进行评估？它是如何评估的？

let rec fibs = lazy (Seq.append 
                        (Seq.ofList [0;1]) 
                        ((Seq.map2 (+) (fibs.Force()) 
                                       (Seq.skip 1 (fibs.Force())))))