数列通项公式
F(0)=1F(2n+1)=F(n)
F(2n)=F(n)+F(n-1)
求F(n).
前100项:
F(1)=1
F(2)=2
F(3)=1
F(4)=3
F(5)=2
F(6)=3
F(7)=1
F(8)=4
F(9)=3
F(10)=5
F(11)=2
F(12)=5
F(13)=3
F(14)=4
F(15)=1
F(16)=5
F(17)=4
F(18)=7
F(19)=3
F(20)=8
F(21)=5
F(22)=7
F(23)=2
F(24)=7
F(25)=5
F(26)=8
F(27)=3
F(28)=7
F(29)=4
F(30)=5
F(31)=1
F(32)=6
F(33)=5
F(34)=9
F(35)=4
F(36)=11
F(37)=7
F(38)=10
F(39)=3
F(40)=11
F(41)=8
F(42)=13
F(43)=5
F(44)=12
F(45)=7
F(46)=9
F(47)=2
F(48)=9
F(49)=7
F(50)=12
F(51)=5
F(52)=13
F(53)=8
F(54)=11
F(55)=3
F(56)=10
F(57)=7
F(58)=11
F(59)=4
F(60)=9
F(61)=5
F(62)=6
F(63)=1
F(64)=7
F(65)=6
F(66)=11
F(67)=5
F(68)=14
F(69)=9
F(70)=13
F(71)=4
F(72)=15
F(73)=11
F(74)=18
F(75)=7
F(76)=17
F(77)=10
F(78)=13
F(79)=3
F(80)=14
F(81)=11
F(82)=19
F(83)=8
F(84)=21
F(85)=13
F(86)=18
F(87)=5
F(88)=17
F(89)=12
F(90)=19
F(91)=7
F(92)=16
F(93)=9
F(94)=11
F(95)=2
F(96)=11
F(97)=9
F(98)=16
F(99)=7
F(100)=19 或列式表示F(10^n):
F(10^1)=5
F(10^2)=19
F(10^3)=39
F(10^4)=205
F(10^5)=713
F(10^6)=1287
F(10^7)=9469
F(10^8)=7901
F(10^9)=73411
F(10^10)=77695
F(10^11)=417293
F(10^12)=2077157 设 g(n)=F(n-1)
原数列转化为
g(1)=1
g(2n)=n
g(2n+1)=g(n)+g(n+1)
------------------------------------
所以$g(2^(k-1))=1，g(2^k)=1$
设 $2^(k-1)<n< 2^k $,那么g(n)=a+b。
其中a和b满足：
1. a和b是都小于k的互质的两个正整数
2. n增大,那么$a/b$值也增大。
----------------------------------------
也就是说，对于$2^(k-1)$和 $2^k$之间的 $2^(k-1)-1$个数，其g值恰好是满足
a和b是都小于k的互质的两个正整数
的所有可能的a和b，按照a/b的值从小到大排列而成。
---------------------------------------------------
比如取k=4,
那么g(8)=1,g(16)=1
g(9)g(10)g(11) g(12)g(13)g(14)g(15) 刚好排成如下
4 3 5 2 5 3 4
1+3 1+2 2+3 1+1 3+2 2+1 3+1
$1/3 < 1/2 < 2/3<1/1 <3/2 < 2/1 <3/1$ 本帖最后由 056254628 于 2010-1-11 01:52 编辑
写成如下就一目了然： 第k层
1 1 第1层
1 2 1 第2层
1 3 2 3 1 第3层
1 4 3 5 2 5 3 4 1 第4层
15473857275837451 第5层
k=5: 1+41+32+51+23+52+33+41+14+33+25+32+15+23+14+1
k=6:1+5 1+4 2+7 1+3 3+8 2+5 3+7 1+2 4+7 3+5 5+8 2+3 5+7 3+4 4+5 1+1 4+3 3+2 5+3 2+1 5+2 3+1 4+1
确实都是满足 a和b都是互质的整数，且a/b呈增大趋势，但不满足a<k，b<k,所以3楼的a、b满足的条件还是有问题！ a和b的条件应该为如下：
$g(2^(k-1))=1，g(2^k)=1$
设 $2^(k-1)<n< 2^k $,那么g(n)=a+b。
其中a和b满足：
1. a和b是互质的两个正整数。
2.a<=S，b<=S， S为斐波拉契数列的第k项的值。（1，1，2，3，5，8，13，......）
3. 若a<b，那么$1/k<=a/b<=(k-1)/k$。若a>b，那么$k/(k-1)<=a/b<=k$
4. n增大,那么$a/b$值也增大。 这题粗略的可以理解为 “中位数” 求F(10^n)的算法很简单。
以10^2为例：
把10^2转化为二进制，得1100100。
从a=1，b=0开始，
根据二进制数的序列进行赋值操作。
"0"就是a=a+b，"1"就是b=a+b。
所以F(10^2)的操作序列为
a=1;b=0;
b=a+b; //得b=1
b=a+b; //得b=2
a=a+b; //得a=3
a=a+b; //得a=5
b=a+b; //得b=7
a=a+b; //得a=12
a=a+b; //得a=19
所以F(10^2)=19。
我们再看一下F(10^3)。
10^3的二进制为1111101000。
所以操作序列如下：
b,b, b,b,b,a,b,a, a, a
1,2,3,4,5,6,11,17,28,39
所以F(10^3)=39。
10^4的二进制为10011100010000。
操作序列为baabbbaaabaaaa，结果如下：
b,a,a, b,b,b, a, a,a, b, a, a, a, a
1,2,3,4,7,10,13,23,33,43,76,119,162,205
所以F(10^4)=205。
可是楼主要求列出计算公式。
如何把上述操作用计算公式来表示呢？大家有想法吗？ 以前看过很像的一个题，是求第0-n项中最大值的。
应该没有啥通项公式吧！
http://topic.csdn.net/u/20081023/20/d95b4185-ae29-4363-a24c-41553a66fc4c.html 设 g(n)=F(n-1)
原数列转化为
g(1)=1
g(2n)=n
g(2n+1)=g(n)+g(n+1)
------------------------------------
所以$g(2^(k-1))=1，g(2^k)=1$
设 $2^(k-1)
056254628 发表于 2010-1-11 00:31 http://bbs.emath.ac.cn/images/common/back.gif
如此说来,F(n)/F(n-1) 与F(n)/F(n+1) 可表示所有的有理数了? 求F(10^n)的算法很简单。
以10^2为例：
把10^2转化为二进制，得1100100。
从a=1，b=0开始，
根据二进制数的序列进行赋值操作。
"0"就是a=a+b，"1"就是b=a+b。
所以F(10^2)的操作序列为
a=1;b=0 ...
KeyTo9_Fans 发表于 2010-1-11 11:51 http://bbs.emath.ac.cn/images/common/back.gif
很强大.
似乎对所有的n都可以这样计算.
这样计算F(n)分两步就可以了: n移位, 累加a 或 b