目录
1. 引言
1.1实验目的
1.2实验内容
1.3实验要求
2. 实验运行环境
2.1硬件环境
2.2软件环境
3. 程序设计说明
3.1功能概述
3.2程序目录结构的介绍
3.3程序实现方案
3.3.1迭代法的实现方案
3.3.2黄金分割率法的实现方案
3.3.3矩阵相乘法的实现方案
3.3.4总体调用
4 界面操作说明
5 实验结果及相关结论
6 程序使用的一些技巧和优点
6.1使用的一些技巧
6.2程序的优点
1. 引言
1.1 实验目的
通过使用普通迭代法、黄金分割率法和矩阵相乘法对求 Fibonacci 数的程序进行编写和调试运行，然后比较这三种方法实际的运行时间，来加强对矩阵相乘法中分治法的理解与掌握。
1.2 实验内容
比较不同方法求 Fibonacci 数。
1.3 实验要求
要求交源码，可执行程序，实验报告。
2. 实验运行环境
2.1 硬件环境
CPU: 2.5 GHz Intel Core i7
内存:16.0GB
2.2 软件环境
操作系统:mac OS10.12
语言及编译平台:Java【jdk1.8】，Eclipse
3. 程序设计说明
3.1 功能概述
运行程序后，将提示用户输入一个正整数，用户输入后程序将会通过三种方法分别计算。
3.2 程序目录结构的介绍
在这次程序编写过程中，在mac 系统下采用了 Eclipse IDE 环境，求Fibonacci 数程
序的目录截图如下:
calFibonacci.java实现了程序的所有功能:接收用户的输入使用迭代法、黄金分割率法和分治法对输入进行计算，其中包括大数加减乘除法的实现，以及最后结果的输出操作。
3.3 程序实现方案
3.3.1 迭代法的实现方案
/*** 使用迭代法求Fibonacci数列的第n项 */
3.3.2 黄金分割率法的实现方案:
3.3.3 矩阵相乘法的实现方案:
推导公式如下：
进一步得到：
3.3.4 总体调用:
(1)先获取用户的输入再进行下一步操作;
(2)调用迭代法，开始计算第 n 项 Fibonacci;得到结果后输出第 n 项 Fibonacci 数列，然后输出该方法所花费的时间;
(3)调用黄金分割率法，开始计算第 n 项 Fibonacci;得到结果后输出第 n 项 Fibonacci 数列，然后输出该方法所花费的时间;
(3)调用矩阵相乘分治法，开始计算第 n 项 Fibonacci;得到结果后输出第 n 项 Fibonacci 数列，然后输出该方法所花费的时间。
4 界面操作说明
(1)、运行程序后得到如下界面:
(2)、当输入一个正整数时，有如下的输出:
输入30时，都可以运行出来：
输入40时，迭代法很慢：
输入150000时，迭代法基本不能实现，黄金分割率法很慢：
输入1000000时，黄金分割率法基本不能实现，使用矩阵相乘：[if !vml]
通过在运行程序时，计算 Fibonacci 数列并输出结果所花的时间，可以看出，当输入规模较小时(比如小于 40 时)，迭代法还可以运行;当输入较大(比如小于 200000 时)时，黄金分割率法还可以运行；当大于200000甚至1000000时，矩阵相乘法仍然可以运行。针对不同的输入规模，迭代法、黄金分割率法和矩阵相乘分治法所花的时间对比如下折线图和表格展示:
5 实验结果及相关结论
Fibonacci的n项
迭代法求解所花时间(单位为: 微秒)
黄金分割率法求解所花时间 (单位为: 微秒)
矩阵相乘分治法求解所花时间(单位为: 微秒)
2 0 2 0
30 40 2 1
40 5363 2 1
100 很慢 6 1
1000 36 4
10000 315 17
50000 2277 53
100000 5102 135
150000 11152 210
200000 13546 376
1000000 很慢 4798
6 程序使用的一些技巧和优点
6.1 使用的一些技巧
(1)由于要处理大数的加减乘除操作和sqrt中精度和位数的操作，所以程序使用了BigInteger和BigDecimal来计算，直接使用内部方法即可。
(2)在使用矩阵相乘分治法时，判断n是否为奇数，再递归调用矩阵相乘法。得到的矩阵中rs[0][1]即为F(n)结果。
6.2 程序的优点
(1)程序能够判断用户的输入，并运行到1000000;
(2)能够处理大数的加减乘法操作和double数的高精度计算。如果直接使用 long long(或者_int64) 则能够计算的 Fibonacci 项数会达到inifity;
(3)程序的健壮性比较好，无论需要处理的是否为大数，都可以正确输出结果。
网友评论