如果你要看一个计算第n个Fibonacci数的递归实现(根100,子99和98,孙子98,97,97和96等等),大概是什么比例的数量留下递归树中的节点总数？
100
/ \
98 97
/ \ .
96 97 .
. . .
. .
不是家庭作业,只是在学术上对此感到好奇.(是的,我意识到递归实现是计算斐波纳契数的一种可怕的方法)
我正在使用(a)线性方法计算第n个斐波那契数,以及(b)该表达式
Python代码:
'Different implementations for computing the n-th fibonacci number'
def lfib(n):
'Find the n-th fibonacci number iteratively'
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
def efib(n):
'Compute the n-th fibonacci number using the formulae'
from math import sqrt, floor
x = (1 + sqrt(5))/2
return long(floor((x**n)/sqrt(5) + 0.5))
if __name__ == '__main__':
for i in range(60,80):
if lfib(i) != efib(i):
print i, "lfib:", lfib(i)
print " …确定Fibonacci序列很容易弄清楚:
int num = 0;
int num2 = 1;
int loop;
int fibonacci;
System.out.print(num2);
for (loop = 1; loop <= 10; loop ++)
{
fibonacci = num + num2;
num = num2;
num2 = fibonacci;
System.out.print(" " + fibonacci);
}
我的问题在于试图精确定位指定N的值.如果我想在序列中找到第6个元素,即8,我将如何找到该数字,只有那个数字？
我试图以一种非常简单的方式计算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来添加数字.
所以我需要将一个函数描述为
invFib :: Integer -> Maybe Integer
取一个整数并在斐波那契序列中查找它(如下面的函数所述)
fibs :: [Integer]
fibs = 0:1:(zipWith (+) fibs (tail fibs))
并返回数字示例的索引:
invFib 0 〜> Just 0
invFib 1〜> Just 1或Just 2
map invFib [54, 55, 56] 〜> [Nothing,Just 10,Nothing]
invFib (fibs !! 99) 〜> Just 99
我尝试创建一个函数,它获取整数列表并吐出索引,但它仍然失败.有什么想法吗？
这是我试过的功能 -
findNum :: [Integer] -> Integer -> Integer -> Integer
findNum x:xs y z = if x == y
then z
else findNum xs y (z+1)
编辑:该函数冻结不在斐波那契序列中的数字,也只在输入1时显示1个值
invFib :: Integer -> …我一直在努力创建一个无限的斐波纳契列表,产生的函数可以将前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))) …给定范围[x,y]找到数字的数量,使得一个数字必须将其设置位数作为斐波纳契数？
例如:[15,17]
15 - 1111 - Count of bits is 4 - (4 is not a fibonacci number)
16 - 10000 - Count of bits is 1 - (1 is a fibonacci number)
17 - 10001 - Count of bits is 2 - (2 is a fibonacci number)
所以回答是 2 (16,17)
显然我们计算设置位并检查它是否fibonacci使用条件是否(5x^2 +/- 4)是一个完美的正方形.
注意:这是一个面试问题.面试官对上述方法不满意.
我们可以做得更好吗？
Fibonacci的这种实现很容易理解但很慢:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
实施Fibonacci之后很难理解,但速度非常快.它会立即在我的笔记本电脑上计算出第100,000个斐波纳契数.
fib = fastFib 1 1
fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)
关于后一种实施,这里发生了什么神奇的事情,它是如何运作的？