标签: fibonacci

当k = 2时,我们都知道斐波那契数列.

即: 1,1,2,3,5,8,13

但这是2-fibonacci.像这样,我可以算第三个斐波那契:

1,1,2,4,7,13,24

而4-fibonacci:

1,1,2,4,8,15,29

......等等

我要问的是计算k-fibonacci系列中'n'元素的算法.

像这样:如果我要求fibonacci(n=5,k=4),结果应该是:8,即4-fibonacci系列中的第五个元素.

我没有在任何网站找到它.帮助的资源可能是mathworld

任何人？如果你知道python,我更喜欢.但如果没有,任何语言或算法都可以提供帮助.

提示我认为这可以帮助:让我们分析k-fibonacci系列,其中k将从1到5

k    fibonacci series

1    1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3    1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4    1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5    1, 1, 2, 4, 8, 16, 31, 61, 120, ... …

确保您在IDE外部运行.这是关键.

-edit-我喜欢SLaks评论."这些答案中的错误信息量是惊人的." :d

冷静下来.几乎所有人都错了.我做了优化. 事实证明,我所做的任何优化都不够好. 我使用gettimeofday在GCC中运行代码(我将在下面粘贴代码)并使用g++ -O2 file.cpp并获得稍快于C#的结果. 也许MS没有创建在这个特定情况下所需的优化,但在下载和安装mingw后,我进行了测试,发现速度几乎相同. Justicle似乎是对的.我可以发誓我在我的电脑上使用时钟并使用它来计算并发现它速度较慢但问题已解决.在MS编译器中,C++速度几乎不会慢两倍.

当我的朋友告诉我这件事时我无法相信.所以我拿了他的代码并把一些定时器放在上面.

而不是Boo我使用C#.我不断在C#中获得更快的结果.为什么？无论我使用什么数字,.NET版本几乎都有一半的时间.

C++版(坏版):

#include <iostream>
#include <stdio.h>
#include <intrin.h>
#include <windows.h>
using namespace std;

int fib(int n)
{
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    __int64 time = 0xFFFFFFFF;
    while (1)
    {
        int n;
        //cin >> n;
        n = 41;
        if (n < 0) break;
__int64 start = __rdtsc();
        int res = fib(n); …

我发送了这个非常好的非递归函数来计算斐波纳契数列.

所以我编写了一些c#并且能够验证所有高达1474的数字是否正确.

尝试计算1475及以上时会出现问题.我的c#数学技能不能达到找出不同方法的任务.那么,有人有更好的方法在c#中表达这个特定的数学函数吗？除了传统的递归函数方式？

顺便说一句,我开始使用BigInteger作为返回类型.但是当试图将(1 + Math.Sqrt(5)/ 2)提升到1475次幂时,问题确实存在.我只是没有看到我需要什么样的数据类型(也没有这个问题的机制)来让它回归到Infinity以外的东西.

这是一个起点.

private Double FibSequence(Int32 input) {
    Double part1 = (1 / Math.Sqrt(5));
    Double part2 = Math.Pow(((1 + Math.Sqrt(5)) / 2), input);
    Double part3 = Math.Pow(((1 - Math.Sqrt(5)) / 2), input);

    return (part1 * part2) - (part1 * part3);
}

而且,不,这不是功课.对于缓慢的一天来说只是一个"简单"的问题.

有人可以解释一下我应该如何决定是否使用一个或另一个堆实现,在标题中提到的那些？

根据问题,我想要一个答案来指导我选择有关结构性能的实施方案.现在,我正在做一个优先级队列,但我想知道这个案例最合适的实现,但是基本允许我在任何其他情况下选择一个实现...

另外需要考虑的是我这次使用的是haskell,所以,如果你知道任何可以改善这种语言实现的技巧或其他东西,请告诉我!但和以前一样,欢迎使用其他语言的评论!

谢谢!对不起,如果问题太基础,但我根本不熟悉.这是我第一次面临实施一项任务的任务......

再次感谢!

如何在O(n)中没有运行循环的情况下实现递归Fibonacci函数？

我正在尝试Julia 1.3使用以下硬件的多线程功能：

Model Name: MacBook Pro
Processor Name: Intel Core i7
Processor Speed:    2.8 GHz
Number of Processors:   1
Total Number of Cores:  4
L2 Cache (per Core):    256 KB
L3 Cache:   6 MB
Hyper-Threading Technology: Enabled
Memory: 16 GB

运行以下脚本时：

function F(n)
if n < 2
    return n
    else
        return F(n-1)+F(n-2)
    end
end
@time F(43)

它给我以下输出

2.229305 seconds (2.00 k allocations: 103.924 KiB)
433494437

但是，当运行下面的代码从Julia页面复制的关于多线程的代码时

import Base.Threads.@spawn

function fib(n::Int)
    if n < 2 …

我想尝试学习Lisp,但我很快就放弃了.我想我会再试一次.我正在关注Euler项目的问题2 - 找到所有甚至斐波那契数字低于4百万的总和.

我写了下面的代码,但有各种丑陋.其中最主要的是它太慢了 - 因为它一直在进行天真的递归.

当我用Python编写这个程序时,我按计算建立了一个列表,从不重新计算数字.我知道我可以在这里(不知何故)这样做,但这似乎不是真正的lisp精神,函数式编程.我在#3之后放弃了,当我达到递归深度限制并且不得不重写我的代码以使用循环而不是递归.

所以我想我的问题是:

1. 什么是解决这个问题的'正确,积极的方式'？
2. 你如何协调递归和"只计算一切"的概念与计算一切的实际限制？
3. 除了Little Schemer和Project Euler之外,还有任何关于学习lisp的建议吗？

这是我的代码:

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ …

在Excel中,我想舍入到最近的斐波纳契数.

我尝试了类似的东西(抱歉使用法语Excel):

RECHERCHEH(C7;FIBO;1;VRAI) -- HLOOKUP(C7, FIBO, 1, TRUE)

其中FIBO是命名范围(0; 0,5; 1; 2; 3; 5; 8;等等)

我的问题是这个函数舍入到最小的数字而不是最近的数字.例如,12.8舍入为8而不是13.

注意:我只想使用excel公式,而不是VBA

我试图以xy(2D)坐标的形式生成一个螺旋星系 - 但数学并不是我的强项.

我从螺旋上的一个优秀来源收集了以下信息:

半径r(t)和角度t与最简单的螺旋,阿基米德的螺旋成比例.因此,等式是:

(3)极坐标方程:r(t)= at [a是常数].
由此得出
(2)参数形式:x(t)= at cos(t),y(t)= at sin(t),
(1)中心方程:x²+y²=a²[arc tan(y/x) ]².

这个问题有点触及了星系的产生,但是反应是分散的,而且仍然过于复杂,因为我需要的东西(也就是说,我的数学愚蠢的头脑无法理解它们).

基本上,我需要做的是在PHP~5000次循环螺旋公式,以在513x513 XY网格上生成点.网格的大小和所需的点数可能在将来发生变化.更好的方法是将这些点与螺旋的原点进行权衡,无论是频率还是偏离精确的数学公式,与星系的实际外观类似.

这篇数学论文讨论了一个描述螺旋星系结构的公式.

完全失去我的是如何将数学公式转换为我可以在PHP中循环的东西!

所以,我已经看到了针对这个问题或类似问题的一些解决方案,但我真的想知道为什么 我的工作不起作用.它比我找到的很多解决方案更容易阅读,所以我很乐意让它发挥作用!

从1对兔子开始,2个月后开始繁殖.跑了n个月,兔子在生活了几个月后就死了.输入'6 3'应该返回4,但它返回3.

#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split() 
n, m = int(n), int(m)
generations = [1, 1, 2] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
    count = 3 #we start at the 3rd generation.
    while (count < i):
        if (count < j):
            generations.append(generations[count-2] + generations[count-1]) #recurrence relation before …