数列通项公式

northwolves

F(0)=1
F(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

northwolves

或列式表示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

056254628

设 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

写成如下就一目了然：                                              第k层
1                                                                      1                  第1层
1                                   2                                 1                 第2层
1                3                2                3               1                第3层
1     4        3       5       2      5       3      4      1                 第4层
1  5  4  7  3  8  5  7  2  7  5  8  3  7  4  5  1                第5层


k=5:   1+4  1+3  2+5  1+2  3+5  2+3  3+4  1+1  4+3  3+2  5+3  2+1  5+2  3+1  4+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满足的条件还是有问题！

056254628

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$值也增大。

wayne

这题粗略的可以理解为 “中位数”

KeyTo9_Fans

求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。

可是楼主要求列出计算公式。

如何把上述操作用计算公式来表示呢？大家有想法吗？

litaoye

以前看过很像的一个题，是求第0-n项中最大值的。

应该没有啥通项公式吧！

http://topic.csdn.net/u/20081023 ... c-41553a66fc4c.html

northwolves

设 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

如此说来,F(n)/F(n-1) 与F(n)/F(n+1) 可表示所有的有理数了?

northwolves

求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

很强大.
似乎对所有的n都可以这样计算.
这样计算F(n)分两步就可以了: n移位, 累加a 或 b