斐波那契数列新的项由前两项的和来生成。以1,2作为开始项,斐波那契数列的前十个元素是:

1,2,3,5,8,13,21,34,55,89,...

考察数列中数值不大于4000000的项,求所有偶数项数值的和。

即:2+8+34+144+...+不大于4000000的项=?

来源:问题2

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

asked 14 Oct '14, 09:59

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131726860896

结果:4613732

(14 Oct '14, 14:18) 仰望星空 %E4%BB%B0%E6%9C%9B%E6%98%9F%E7%A9%BA's gravatar image

分析

项序号:         1,2,3,4,5,6, 7, 8, 9, 10,...
斐波那契数列:   1,2,3,5,8,13,21,34,55,89,...

可以发现,值为偶数的项序号为:
2,5,8,11,14,...

即第(3k-1)项都为偶数, 其中k取1,2,3,...

那么,sum(a(3k-1))就是题目的解,其中k取1,2,3,4,...
并且约束条件为:a(3k-1)  < 4000000

因为:a(3k+1) = a(3k) + a(3k-1)
移项得:a(3k-1) = a(3k+1) - a(3k)
于是:a(3k-1) = a(3k+1) - (a(3k-1) + a(3k-2))
归并后:2 * a(3k-1) = a(3k+1) - a(3k-2) = a(3k+1) - a(3(k-1) + 1)

那么:sum(2*a(3k-1)) = sum(a(3k+1)) - sum(a(3(k-1) + 1))

求解得:sum(a(3k-1)) = (a(3k+1) - a(1)) / 2

程序实现

a = 1
b = 2
c = a + b

limit = 4000000

i = 3

while c < limit:
    a = b
    b = c
    c = a + b
    i = i + 1

while (i + 1) % 3 != 0:
    a = b
    b = c
    c = a + b
    i = i + 1


print (b - 1) / 2

运行结果

4613732

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 30 Oct '14, 01:29

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

编辑于 30 Oct '14, 13:03

@仰望星空 该解法省去了4000000次if判断,效率大大提升~

(30 Oct '14, 01:35) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

@原野之狼 你的解法引入了"while (i + 1) % 3 != 0:",计算机做%3所花的时间比"%2"大很多,从效率上看,可能代价会更大
由于评论字数有制约,看楼下的数据。。。

(30 Oct '14, 09:15) major major's gravatar image

你再仔细分析一下吧~
可以用C写上两端程序对比运行一下就知道结果了,然后发现自己是错的,呵呵.

(30 Oct '14, 09:24) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image
int main(void)
{
        unsigned int first,next,last;
        unsigned int max,no;

        first = 1;
        next = 2;
        last = 3;
        max = 2;
        no = 3;
        for(;last < 4000000;no ++){
                first = next;
                next = last;
                last = next + first;
                if(last % 2 == 0 && last < 4000000)
                        max += last;
        }

        printf("first:%d  next:%d    last:%d   no:%d  max:%d\n",first,next,last,no,max);

        return 0;
}

结果:first:2178309 next:3524578 last:5702887 no:33 max:4613732

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 14 Oct '14, 14:18

%E4%BB%B0%E6%9C%9B%E6%98%9F%E7%A9%BA's gravatar image

仰望星空
285454651

观察可得偶数为a<3k + 2> (k > 0, 整数)以及a<2>
a<3k + 4> = a<3k + 3> + a<3k + 2> = 2a<3k + 2> + a<3k + 1> = 2a<3k + 2> + a<3(k - 1) + 4>
可得a<3k + 4> - a<3(k - 1) + 4> = 2a<3k + 2>
所以sum(a<3k+2>, n) = (sum(a<3k + 4>, n) - sum(a<3(k - 1) + 4>, n) / 2 = (a<3n + 4> - a<4>) / 2
偶数和=a<2> + sum(a<3k + 2>, n) = a<2> + a<3n + 4> / 2 - a<4> / 2

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 29 Oct '14, 23:29

%E4%BD%A0%E6%9C%AC%E5%A6%82%E5%8E%BB's gravatar image

你本如去
1866

编辑于 29 Oct '14, 23:32

@原野之狼 你的解法引入了"while (i + 1) % 3 != 0:",计算机做%3所花的时间比"%2"大很多,从效率上看,可能代价会更大
1:在没有乘法器的(比如一些51 pic mcu),%2可以用移位实现,而%3要调用库函数
2:在一般cpu中
c语言:
if(tmpSum&0x01!=0)
{
testM2 = tmpSum;
}
以及
if(tmpSum%3!=0)
{
testM2 = tmpSum;
}
对应的汇编:
17: if(tmpSum&0x01!=0)
18: {
0x0000075A F0140F01 TST r4,#0x01
0x0000075E D000 BEQ 0x00000762
19: testM2 = tmpSum;
20: }
以及
22: if(tmpSum%3!=0)
23: {
0x00000764 2003 MOVS r0,#0x03
0x00000766 FB94F1F0 SDIV r1,r4,r0
0x0000076A FB004011 MLS r0,r0,r1,r4
0x0000076E B100 CBZ r0,0x00000772
24: testM2 = tmpSum;
25: }
从中可以看出效率上的区别

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 30 Oct '14, 09:17

major's gravatar image

major
351283237

针对本题,你写两段程序对比一下。

(30 Oct '14, 09:25) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

对比可以另外一贴,挺有意思的一个问题。

(30 Oct '14, 12:34) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

注意一下,第二个while循环的次数,实际上没几次,小于3次。

(02 Nov '14, 11:30) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image
a<n> = a<n - 1> + a<n - 2>
可得到a<2k + 1> = a<2k> + a<2k - 1> = a<2(k - 1)+ 1> + a<2k>
进而得到a<2k> = a<2k + 1> - a<2(k - 1) + 1>
所以sum(a<2k>, n) = sum(a<2k + 1>, n) - sum(a<2(k - 1) + 1>, n) = a<2n + 1> - a<1>
系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 29 Oct '14, 17:43

%E4%BD%A0%E6%9C%AC%E5%A6%82%E5%8E%BB's gravatar image

你本如去
1866

编辑于 29 Oct '14, 22:24

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116

题意理解错了。
求值为偶数的项的累加和,而不是偶数项的累加和。

(29 Oct '14, 22:36) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

都是算法呀,这一块比较弱,表示看不懂呀。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 30 Oct '14, 08:55

%E6%9D%8E%E5%B0%8F%E7%99%BD's gravatar image

李小白
309252733

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link: [text](http://url.com/ "title")
  • image: ![alt](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×33
×5

question asked: 14 Oct '14, 09:59

question was seen: 6,519 times

last updated: 02 Nov '14, 11:30

powered by O*S*Q*A

粤ICP备14040061号-1