我正在编写一个"简单"程序来确定Fibonacci序列中的第N个数字.例如:序列中的第7个数字是:13.我已经完成了程序的编写,它可以工作,但从第40个数字开始它开始延迟,并且需要更长,更长.我的节目必须到系列中的第100个位置.
我怎么能解决这个问题所以它不需要这么长时间？这是非常基本的程序,所以我不知道所有花哨的语法代码..我的公式是:
if n =1 || n = 0
return n;
else
return F(n-1) + F(n-2);
这很有效,直到它超过第40个学期.我必须添加什么其他声明才能更快地获得更高的数字？
如果你要看一个计算第n个Fibonacci数的递归实现(根100,子99和98,孙子98,97,97和96等等),大概是什么比例的数量留下递归树中的节点总数？
100
/ \
98 97
/ \ .
96 97 .
. . .
. .
不是家庭作业,只是在学术上对此感到好奇.(是的,我意识到递归实现是计算斐波纳契数的一种可怕的方法)
这是我上一个问题的后续行动.
据我所知,以下计算Fibonacci数的方法效率很低,因为fib每个Fibonacci数调用该方法,每次调用它时都会创建一个新流.
def fib:Stream[Int] =
Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))
另一方面,尾递归方法(如此处)看起来非常有效并计算每个斐波那契数O(1)
def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));
现在我得出结论,创建Streams的递归方法是有效的,当且仅当它们是尾递归时.这是对的吗？
我试图以一种非常简单的方式计算C#中的Fibonacci序列,但是当涉及到更高的数字时,它会通过给出错误的答案来阻止并停止工作.
ulong num = 1;
ulong lnum = 0;
uint x = 1;
private void Form1_Load(object sender, EventArgs e)
{
listBox1.Items.Add("(0) " + 1);
}
private void timer1_Tick(object sender, EventArgs e)
{
if (x <= 1000)
{
ulong newnum = lnum + num;
listBox1.Items.Add("(" + x + ") " + newnum);
listBox1.SetSelected((int)x, true);
lnum = num;
num = newnum;
x++;
}
}
我正在通过一种方式制作它,我可以通过一次将它们添加到列表框1来添加数字.
我试图理解计划中的递归,并且我很难为它做干运行,例如一个简单的斐波那契数问题是否有人可以分解添加发生的步骤？
(define (fib n)
(if (<= n 2)
1
(+ (fib (- n 1)) (fib (- n 2)))))
这就是他们所拥有的:
def fib(n):
a, b = 0, 1
while a < n:
print a,
a, b = b, a+b
这就是我所拥有的:
def fib(n):
a = 0
b = 1
while a < n:
print a
a = b
b = b+a
第一个在使用时返回正确的序列,而我的第一个返回0,1,2,4,8,16,32 ......
我目前正在学习编程(没有先前的计算机科学教育),很明显问题是我如何定义我的变量.用逗号分隔变量和用新行分隔变量之间有什么区别(假设这是问题)？
我一直在努力创建一个无限的斐波纳契列表,产生的函数可以将前2个值作为参数.
如果没有指定前两个值,就可以这样做
fib = 1 : 1 : zipWith (+) fib (tail fib)
假设我想用5和6而不是1,1或0,1开始斐波那契序列,那么我将不得不改变上面的代码.但是当我试图制作一个惰性列表生成器,我可以在其中指定斐波那契序列的前2个值时,我很难过.我想出了这个但是没有用.
fib a b = a : b : zipWith (+) fib (tail fib)
问题很明显.我试图转换硬编码列表的使用.我怎么解决这个问题？
我编写了以下代码来生成包含Fibonacci数字的列表.
fibonacci = [a + b | a <- 1:fibonacci, b <- 0:1:fibonacci]
我希望列表[1,2,3,5,8,13..]的输出是,但输出不是Fibonacci序列.
我不太明白为什么它不起作用.
我的理由是,如果斐波那契数字是[1,2,3,5,8,13..]那么这将是等于2名列表之[1,1,2,3,5,8,13..]和[0,1,1,2,3,5,8,13..],这相当于1:[1,2,3,5,8,13..]和0:1:[1,2,3,5,8,13..]或1:fibonacci和0:1:fibonacci
我已经查找了实现此序列的其他方法,但我真的想知道为什么我的代码不起作用.
我受邀参加Google的foobar挑战赛。我目前在2.2级时遇到以下问题。
可爱的幸运羔羊
做一个小伙子并不单单是苦力。有时，当Lambda指挥官感到慷慨时，她会分发Lucky LAMBs（Lambda的多用途钱袋）。武装分子可以使用幸运的羔羊来买东西，例如第二双袜子，铺床上的枕头，甚至是第三顿日常餐！但是，要传播出LAMB并不容易。每个小伙子都有严格的资历等级，必须予以尊重-否则小伙子将起义，而你们所有人都将再次被降级为奴才！
为避免起义，必须遵循4条关键规则：
- 最年轻的小伙子（资历最少）刚好得到1个LAMB。（一个团队中总是至少有1个随从。）
- 如果紧随其后的人获得的LAMB数量增加一倍以上，那将成为反叛者。
- 如果向其下两个下属提供的LAMB数量超过其获得的LAMB数量，则该弓箭手将起义。（请注意，两个最初级的he夫不会有两个下属，因此此规则不适用于他们。第二个最初级的he夫至少需要与最初级的he夫一样多的LAMB。）
- 您总能找到更多要支付的he夫-司令官有大量员工。如果有足够的LAMB剩余，可以在遵守其他规则的同时将另一名行政长官添加为最高级，则您必须始终添加该名警官并向其付款。
请注意，您可能无法分发所有LAMB。单个LAMB不能再细分。也就是说，所有的追随者必须获得正整数的LAMB。
编写一个名为answer（total_lambs）的函数，其中total_lambs是您要除法的讲义中LAMB的整数。它应该返回一个整数，该整数表示可以共享LAMB的小伙子们的最小数量和最大数量之间的差额（即，分别对您所支付的人尽可能慷慨和尽可能小气），同时仍然要遵守上述所有条件避免起义的规则。
例如，如果您有10个LAMB，并且尽可能地慷慨，则您只能支付3名追随者（按升序排列，分别有1、2和4名LAMB），而如果您太小气，则可以支付4追随者（1、2、3和3个小羊）。因此，answer（10）应该返回4-3 =1。为使事情变得有趣，Commander Lambda更改了幸运LAMB支出的大小：您可以期望total_lambs始终在10到10亿之间（10 ^ 9）。
我的方法和代码
为了找到最低限度的血统，必须慷慨地给予LAMB，其几何级数为 1,2,4,8 ...由于几何级数的总和为
（$ S = 2 ^ n -1 $，因此，追随者的人数为[log_2（S + 1）]
要找到最大的帮手，必须以小气的方式给出LAMB，以使他们看起来像斐波那契1，1、2、3、5 ...我们可以使用斐波那契指数法来获得最大的帮手数量：
遵循python代码：
from math import sqrt
from math import log
from math import pow
def answer(total_lambs):
phi = (1+sqrt(5))/2 # golden search ratio
tau = (1-sqrt(5))/2 # equal to 1/phi
eps = pow(10, -10)
max_hunchmen = int(round(log((total_lambs + 1) * sqrt(5)+eps, phi))) - 2
Fib_num = int(round((pow(phi, max_hunchmen+2)-pow(tau,max_hunchmen+2))/sqrt(5))) …我有以下python代码:
a, b = 1, 1
for i in range(0, 100):
print a
a, b = b, a + b
它产生了这个:1 1 2 3 5 8等
我在c中写了同样的文章:
#include <stdio.h>
long long unsigned int a = 1, b = 1;
void main(){
for(int i = 0; i < 100; i++){
printf("%llu \n", a);
a = b, b = a + b;
}
}
它产生了这个:1 1 2 4 8 16 32等
为什么c程序在使用完全相同的操作时会产生2的幂？