我看到,通过一个简单的例子是如何产生的斐波那契序列大多数编程语言教程教递归,我的问题是,有没有比产生Fibonacci序列解释递归是如何工作之外的另一个很好的例子？
我正在做一个主题的任务是fib(0)被定义为= 1.但那不可能是正确的？fib(0)是0？
Program with fib(0) = 1; spits out fib(4) = 5
Program with fib(0) = 0; spits out fib(3) = 3
什么是正确的定义？
所以,我们看到了很多斐波纳契问题.我个人非常讨厌他们.很多.不止一切.我认为如果我们可以让任何人都不可能再次将其用作面试问题,那就太好了.让我们看看有多接近O(1)我们可以得到斐波那契.
这是我的开始,几乎来自维基百科,当然还有足够的空间.重要的是,这个解决方案将引爆任何特别大的fib,它包含一个相对天真的power函数使用,如果你的库不好,它会把它放在最坏的O(log(n)).我怀疑我们可以摆脱电源功能,或至少专攻它.有人帮忙吗？除了使用查找表的有限*解决方案之外,是否存在真正的O(1)解决方案？
#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.
int main()
{
int target = 10;
cin >> target;
// should be close enough for anything that won't make us explode anyway.
float mangle = 2.23607610;
float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);
}
*我知道,我知道,这足以满足斐波纳契的任何零实际用途.
我试图找到使用递归树的Fibonacci系列的复杂性,并因此得出height of tree = O(n)最坏情况cost of each level = cncomplexity = n*n=n^2
怎么回事O(2^n)？
var x=0,
var y=1;
var z;
fib[0] = 0;
fib[1] = 1;
for(i=2; i<=10; i++)
{
alert(x+y);
fib[i]=x+y;
x=y;
z=y;
}
我试图生成一个简单的Fibonacci序列,但没有输出.谁能告诉我什么是错的？
我正试图用Ruby单行解决Project Euler中的问题,我很好奇是否有更优雅的问题解决方案:
Fibonacci序列中的每个新术语都是通过添加前两个术语生成的.从1和2开始,前10个术语将是:
1,2,3,5,8,13,21,34,55,89 ......
通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和.
这是我在Ruby中的一行解决方案:
(1..32).inject([0,1]) {|arr, i| (arr << arr[-1] + arr[-2] if arr[-1] + arr[-2] <= 4000000) || arr}.inject(0) {|total, i| total += i.even? ? i : 0}
我主要担心的是我只使用范围(1..32),因为我碰巧知道在Fibonacci序列中的数字开始超过4,000,000之前,这一切都是必要的.我希望不知怎的,它会以某种方式构建在单行中,但我无法弄明白.
不允许使用半冒号!
我一直在研究在Perl 6中构造惰性列表的各种方法,我想收集描述Fibonacci序列的所有简洁方法.
我将从马萨克的期刊中的三个开始:
my @fibs := (0, 1, -> $a, $b { $a + $b } ... *);
my @fibs := (0, 1, { $^a + $^b } ... *);
my @fibs := (0, 1, *+* ... *);
我认为这样的东西也会起作用,但我认为我的语法有误:
my @fibs := (0, 1, (@fibs Z+ @fibs[1..*]));
有什么东西急切(切片？)并导致Rakudo进入无限循环.它是Haskell定义的翻译:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
更新:
看起来像zipWith示例的问题是@fibs[1..*]切片.if tail定义为sub tail (@x) {my $i = 1; {@x[$i++]}...*}然后它正常工作.我很想知道为什么切片对任何熟悉Rakudo内部的人来说都不是懒惰的.
另一个不错的是:
my …以下大约需要30秒才能运行,而我希望它几乎是即时的.我的代码有问题吗？
x <- fibonacci(35);
fibonacci <- function(seq) {
if (seq == 1) return(1);
if (seq == 2) return(2);
return (fibonacci(seq - 1) + fibonacci(seq - 2));
}
def fibSeq(n: Int): List[Int] = {
var ret = scala.collection.mutable.ListBuffer[Int](1, 2)
while (ret(ret.length - 1) < n) {
val temp = ret(ret.length - 1) + ret(ret.length - 2)
if (temp >= n) {
return ret.toList
}
ret += temp
}
ret.toList
}
所以上面是我使用Scala生成一个Fibonacci序列的代码n.我想知道Scala中是否有更优雅的方法可以做到这一点？
我有这个用于计算fibonacci数字的代码python.它起作用并给出预期的结果.但是当我翻译相同时Java,它失败了.知道这里出了什么问题吗？
在python:
def fib3(n):
a,b=0,1
while n>0:
a,b=b,a+b
n-=1
return a
fib3(12) --> 144
在Java:
public static int fib2(int n){
int a = 0;
int b =1;
while(n-- >0){
a=b;
b=a+b;
}
return a;
}
fib2(12) --> 2048