我试图回忆一下Fibonacci递归的算法.下列:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
是不是我要找的,因为它是贪婪的.这将呈指数级增长(只需看看Java递归Fibonacci序列 - 初始参数越大,将进行越多无用的调用).
可能有类似"循环参数移位"的东西,其中调用前一个斐波那契值将检索值而不是再次计算它.
所以我正在学习C++.我已经获得了"C++编程语言"和"有效的C++",而且我正在运行Project Euler.问题1 ... dunzo.问题2 ......没那么多.我在VS328上使用Win32控制台应用程序.
什么是斐波纳契数列的所有偶数项的总和低于400万？
它没有工作,所以我减少到100的测试用例......
这是我写的......
// Problem2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
cout << "Project Euler Problem 2:\n\n";
cout << "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:\n\n";
cout << "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\n";
cout …注意:这个问题的重点更多来自好奇心.我想知道是否有可能将Haskell实现音译成功能性的C#等价物.
所以我一直在学习Haskell非常好,在解决Project Euler问题的同时,我遇到了这个美丽的Haskell Fibonacci实现:
fibs :: [Integer]
fibs = 1:1:zipWith (+) fibs (tail fibs)
当然我很想写这样的C#版本,所以:
如果我这样做:
IEnumerable<int> fibs =
Enumerable.Zip(Enumerable.Concat(new int[] { 1, 1 }, fibs),
//^^error
fibs.Skip(1), (f, s) => f + s);
错误表示使用未分配的局部变量fibs.
所以我稍微有点必要,而这个编译......
public static IEnumerable<int> Get()
{
return Enumerable.Zip(Enumerable.Concat(new int[] { 1, 1 }, Get()),
Get().Skip(1), (f, s) => f + s);
}
它打破了堆栈溢出异常!所以我来到这里..
问题:
我刚刚开始使用VS2010学习F#,下面是我第一次尝试生成Fibonacci系列.我要做的是建立一个小于400的所有数字的列表.
let fabList =
let l = [1;2;]
let mutable a = 1
let mutable b = 2
while l.Tail < 400 do
let c = a + b
l.Add(c)
let a = b
let b = c
我的第一个问题是,在最后一个语句中,我在最后一行收到错误消息"表达式中此点或之前的不完整结构化构造".我不明白我在这里做错了什么.
虽然这似乎是以相当有效的方式(从c ++/C#程序员)构建列表的明显方式,但从我对f#的了解很少,这似乎不是正确的方法来执行程序.这种感觉我是否正确？
我正在查看一些示例Fibonacci序列clojure代码:
(def fibs (lazy-cat [1 2] (map + fibs (rest fibs))))
我一般都明白发生了什么,但不明白lazy-cat.我知道这lazy-cat是一个宏,正在翻译成这样的东西:
(def fibs (concat (lazy-seq [1 2]) (lazy-seq (map + fibs (rest fibs)))))
究竟是什么lazy-seq实现的？即使没有,它仍会被懒惰地评估lazy-seq？这是否严格用于缓存目的？
编辑:谢谢你的答案.令我感到困惑的是,它与concatREPL中的一个普通模式一起工作,因为我之前已经在范围内绑定了fibs.
是否有可能有效地使用Clojure中的斐波那契系列reduce？"累加器"包含什么？
我想它一定是懒惰的.显而易见的是如何使用递归或循环/重复.
我似乎无法想出一个算法来解决以下问题,我尝试使用一系列for循环,但它变得太复杂了:
梯子有
n台阶,人们可以使用1步或2步的任意组合爬上梯子.有多少种方法可以让人爬上梯子？
因此,例如,如果梯子有3个步骤,这些将是可能的路径:
并为4个步骤
任何关于如何做到这一点的见解将不胜感激.另外,我在Java工作.
编辑:我确实会使用较小的n值,但知道如何管理较大的值肯定会很好.
的斐波那契堆数据结构在其名称中的"黄金分割",但没有在数据结构似乎使用斐波那契数.根据维基百科的文章:
Fibonacci堆的名称来自Fibonacci数字,用于运行时间分析.
Fibonacci堆中如何出现这些Fibonacci数？
我写了一个正则表达式模式来找到Fibonacci数字(没关系,为什么,我刚刚做了).它按预期工作得非常好(参见ideone.com):
String FIBONACCI =
"(?x) .{0,2} | (?: (?=(\\2?)) (?=(\\2\\3|^.)) (?=(\\1)) \\2)++ . ";
for (int n = 0; n < 1000; n++) {
String s = new String(new char[n]);
if (s.matches(FIBONACCI)) {
System.out.print(n + " ");
}
} // 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
一个占有欲重复(即++主"回路")是至关重要的,因为你不希望这种匹配算法回溯.然而,使重复回溯(即仅+在主"循环"上)不会导致不匹配,而是导致运行时异常!(如ideone.com上所示):
Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
String index out of range: -1
at java.lang.String.charAt(String.java:686) …我对Fibonacci数的迭代算法很感兴趣,所以我在wiki上找到了公式...它看起来很直接,所以我在Python中尝试了...它没有问题编译和公式看起来正确...不是确定为什么它给出了错误的输出......我没有实现它吗？
def fib (n):
if( n == 0):
return 0
else:
x = 0
y = 1
for i in range(1,n):
z = (x + y)
x = y
y = z
return y
for i in range(10):
print (fib(i))
产量
0
无
1
1
1
1
1
1