该题来自Project Euler的第二题,求数值小于4百万的偶数项的和。今天继续我的欧拉计划。
问题描述
英语原文
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
中文描述
在Fibonacci数列中,每一项由它的前两项之和生成。从1,2开始,前十项为:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
考虑Fibonacci数列中数值不超过4百万的项,求出值为偶数的项的和。
解决方案
我的解法
这是中规中矩的方法,用了点循环队列的思想,虽然可以用几个变量替代。在写代码的过程中,还犯了一个傻傻的错误,感谢论坛朋友的帮助。
# include <stdio.h>
# define BOUND 4000000
int main(void)
{
int fib[3];
int i;
long long int sum;
fib[0] = 1;
fib[1] = 2;
sum = 2;
for(i = 2; fib[(i - 1) % 3] < BOUND; i++) {
fib[i % 3] = fib[(i - 1) % 3] + fib[(i - 2) % 3]; //队列的思想
if(fib[i % 3] % 2 == 0) {
sum += fib[i % 3];
}
}
printf("%d\n", fib[(i - 2) % 3]);
printf("%d", sum);
}
下面是题目解析提供的几种解法。
直接求解
这个方法和我的方法原理是一样的。
# include <stdio.h>
int main(void)
{
int limit;
int a, b, h;
int sum;
limit = 4000000;
a = b = 1;
sum = 0;
while(b < limit) {
if(b % 2 == 0) {
sum += b;
}
h = a + b;
a = b;
b = h;
}
printf("%d", sum);
}
另一种方法
仔细观察数列,可以发现,每三个Fibnacci数有一个偶数。利用这个规律,可以省去条件判断。
# include <stdio.h>
int main(void)
{
int limit;
int a, b, c;
int sum;
limit = 4e6;
a = 1;
b = 1;
c = 2;
sum = 0;
while(c < limit) {
sum += c;
a = b + c;
b = a + c;
c = a + b;
}
printf("%d", sum);
}
高效方案
如果把偶数项拿出来:
2,8,34,144……
它们遵循的这样的规律:
E(n)=4*E(n-1)+E(n-2)
# include <stdio.h>
int main(void)
{
int limit;
int a, b;
int sum;
limit = 4e6;
sum = 2;
a = 2;
b = 8;
while(b < limit) {
sum += b;
b = 4 * b + a;
a = (b - a) / 4; //在没有使用第三变量的情况下,变量后移
}
printf("%d", sum);
}
要证明上关系式成立,只需证:
F(n)=4*F(n-3)+F(n-6)
证明过程如下:
F(n) = F(n-1) + F(n-2)
= F(n-2)+F(n-3)+F(n-2)=2 F(n-2) + F(n-3)
= 2(F(n-3)+F(n-4))+F(n-3))=3 F(n-3) + 2 F(n-4)
= 3 F(n-3) + F(n-4) + F(n-5) + F(n-6)
= 4 F(n-3) + F(n-6)
最后答案
4613732
分享到:
相关推荐
欧拉计划1-50题
欧拉计划经典题目,用于练习,一共60题。欧拉计划经典题目,用于练习,一共60题
自己写的程序,借鉴了许多高手的算法,都可以直接运行通过,希望朋友们喜欢。
1. 10以下的自然数中,属于3和5的倍数的有3,5,6和9,它们之和是23。找出1000以下的自然数中,属于3和5的倍数的数字之和。
欧拉计划001求3的倍数和5的倍数之和(Python题解)全文共2页,当前为第1页。欧拉计划001求3的倍数和5的倍数之和(Python题解)全文共2页,当前为第1页。欧拉计划001求3的倍数和5的倍数之和(Python题解) 欧拉计划...
欧拉计划提供了几百道由易到难的数学问题,你可以用任何办法去解决它,当然还得靠编程,但编程语言不限,已经有Java、C#、Python、Lisp、Haskell等各种解法,当然直接用google搜索答案就没什么乐趣了。 这里汇总了...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉计划 我的欧拉计划答案
一些c语言训练题,有难度,想提高的同学可以试试
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
欧拉方法以及改进的欧拉方法的matlab实现,希望有用
欧拉计划(欧拉计划) 算法练习部分,目录分类一塌糊涂,我也不打算好好整理了,就这么乱吧解的题有欧拉计划,ZOJ(这破网站最近登不上了) 目录树 . ├── classical_clang c语言算法练习 │ ├── array 动态...
欧拉公式求长期率的matlab代码欧拉计划 问题:甚至斐波那契 斐波那契数列中的每个新项都是通过将前两个项相加而生成的。 从1和2开始,前10个项将是: 1,2,3,5,8,13,21,34,55,89 ... 通过考虑斐波那契数列中值不超过...
采用下述方法,求解常微分方程初值问题 y’=y-2x/y,y(0)=1,计算区间为[0, 1], 步 长为 0.1。 (1)前向欧拉法。 (2)后向欧拉法。 (3)梯形方法。 (4)改进欧拉方法。