标签: fibonacci

Python函数对象有一个属性字典func_dict,在函数外部可见并且是可变的,但在调用函数时不会被修改.(我从昨天问过的问题的答案(#1753232)中学到了这一点:谢谢!)我正在阅读代码(http://pythonprogramming.jottit.com/functional_programming),它记住了Fibonacci数字的计算并思考,"为什么不使用该func_dict属性进行记忆？" 它起作用了(见下文;代码末尾的输出).这有点像有一个类属性,但在对象外面有初始化代码(在这种情况下,不是类而是函数).

我想知道使用这个属性可以做什么相似(或不同)的技巧？

def fib(n):
    if n in fib.cache:
        print "found fib.cache[%d] = %d: " %(n, fib.cache[n])
        return fib.cache[n]
    else:
        print "fib.cache[%d] = fib(%d) + fib(%d)" % (n, n-1, n-2)
        fib.cache[n] = fib(n-1) + fib(n-2)
        print "modified fib.cache: ", fib.cache
        return fib.cache[n]

fib.cache = {0:0, 1:1}

for x in range(7):
    print "==================>", x
    print fib( x)

"""
==================> 0
found fib.cache[0] = 0: 
0
==================> 1
found fib.cache[1] = 1: 
1
==================> …

f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

这个功能在Mathematica中运行缓慢,我需要提高速度.我必须使用函数式编程和递归.我不确定为什么这么慢,甚至最轻微的想法如何改善这将是有帮助的.

这里是我认为scala中斐波那契的正确和有用的定义:

lazy val fibs:Stream[Int] = 0 #:: 1 #:: (fibs,fibs.tail).zipped.map(_+_)

但是,我收到以下错误:

fibs take 10 foreach println
0
1
java.lang.StackOverflowError
    at scala.collection.mutable.LazyBuilder.(LazyBuilder.scala:25)
    at scala.collection.immutable.Stream$StreamBuilder.(Stream.scala:492)
    at scala.collection.immutable.Stream$.newBuilder(Stream.scala:483)
    at...

我猜zipped与流无法正常工作？关于如何使这项工作,或为什么这不(不应该？)工作的任何建议？

#!/usr/bin/python2

"""
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
"""

odd, even = 0,1
total = 0
while True:
    odd = odd + even  #Odd
    even = …

我正在尝试编写一个函数,该函数使用C中的forks从给定的int n递归计算得到的fibonacci数.

这是功能规范:如果print为true,则打印它.否则,将其提供给父进程.解决方案应该是递归的,并且必须为每个调用分叉一个新的子节点.每个进程应该只调用一次doFib().方法签名无法更改.不能使用辅助函数.

这是我到目前为止根据我对fork的理解所写的内容.我试图分叉两次,所以我可以产生两个子进程.一个做fib(n-1),一个做fib(n-2).这样我就可以抓住两个结果并将它们组合起来.

static void doFib(int n, int doPrint)
{
    pid_t pid1;
    pid_t retpid1;
    int status1;

    pid_t pid2;
    pid_t retpid2;
    int status2;

    pid = fork();
    if (pid == 0) // Child Process 1
    {
        exit(100); // sends 100 to the parent
    } 
    else if (pid > 0) // Parent Process 1
    {
        pid2 = fork();
        if (pid2 == 0) // Child Process 2
        {
            exit(200); // sends 200 to the parent
        }
        else if (pid2 > 0) // …

我创办了Project Euler.我遇到了问题2并提出了这个代码来得出甚至斐波那契数字达到400万的总和.代码似乎完全符合我的要求.我确实看到代码运行时列出了​​正确的总和.我真正感到困惑的唯一部分是结果中显示的最后一个数字.这就是它所显示的:

JS代码:

var previous = 0;
var current = 1;
var sum = 0;
var next;

   for(i = 1; i < 100; i++){
        next = current + previous;
        previous = current;
        current = next; 
        if(current % 2 === 0 && current < 4000000) {
            sum += current;
        console.log(sum);
        }
   }

结果:

2
10
44
188
798
3382
14328
60696
257114
1089154
4613732 (this is the number i was trying to get)
=> 354224848179262000000 (confused as to why this number …

我必须完成这个练习,而且我没有得到我需要的结果.

规范是:计算斐波那契序列中所有偶数的总和,以获得低于10,000的值.汇总的前几个数字将是:2,8,34,144,610.

我有一个产生这个输出的小提琴:10,44,188,798,3382.

var x = 1;
var y = 2;
var sum = 0;
var limit = 10000;
var evensum = 2;

while ((x + y) < limit) {
    sum = x + y;
    x = y;
    y = sum;

    if (sum % 2 === 0) {
        evensum += sum;
    }
    console.log(evensum);
}

小提琴链接

有人可以帮我弄清楚我缺少的部分来完成这个练习吗？

非常感谢你.

更新 感谢所有发布解决方案的人.他们都很棒.

我已经定义了这个宏

#define FIB(n) (( 4 << n*(3+n))/((4 << (2*n)) - (2 << n) - 1))%(2 << n)

当我试图得到一个答案时,不能正常工作,例如,如果我打电话给FIB(7),它给我0,那显然是错的.我在python中测试了这个函数,它运行得很好.所以,任何人都可以解释为什么它在C和C++中不起作用？

所以log(N)的Fibonacci数 - 没有矩阵.

Ni // i-th Fibonacci number
= Ni-1 + Ni-2              // by definition
= (Ni-2 + Ni-3) + Ni-2     // unwrap Ni-1
= 2*Ni-2 + Ni-3            // reduce the equation
= 2*(Ni-3 + Ni-4) + Ni-3   //unwrap Ni-2
                           // And so on
= 3*Ni-3 + 2*Ni-4
= 5*Ni-4 + 3*Ni-5
= 8*Ni-5 + 5*Ni-6

= Nk*Ni-k + Nk-1*Ni-k-1

现在我们编写一个递归函数,在每一步我们取k~ = I/2.

static long N(long i)
{
    if (i < 2) return 1;
    long k=i/2;
    return N(k) * N(i …

我有以下代码:

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class DynamicFib
{
    private static Map<Integer, BigInteger> myMap = new HashMap<>();

    static {
        myMap.put(0, BigInteger.ZERO); //fibonacci(0)
        myMap.put(1, BigInteger.ONE); //fibonacci(1)
    }

    public static BigInteger fibonacci(int x)
    {
//        System.out.println("x = [" + x + "]");
        return myMap.computeIfAbsent(x, n -> fibonacci(n - 2).add(fibonacci(n - 1)));
    }

    public static void main(String[] args)
    {

        System.out.println("l = " + fibonacci(25));
        System.out.println("myMap = " + myMap);
        System.out.println("myMap = " + myMap.keySet().size());

    }

}

控制台输出:

l = 75025

myMap …