- 前言
- 一、斐波那契数是什么？实验具体实验要求是什么？
- 二、具体实验要求实现
- 1.利用五种方法计算斐波那契数
- 五种方法代码
- 获取文本和显示内容
- 关键点
- 2.寻找不超过编程环境的最大整数斐波那契是第几个（迭代）
- 3.寻找不超过编程环境的最大整数斐波那契是第几个（递归）
- 4.根据迭代寻找到的不超过环境能支持的斐波那契是第几个，用迭代计算
- 5. 30s内递归和迭代计算出的最大斐波那契是第几个
- 6.利用显示公式计算第n个斐波那契数，找出出现误差时候最小的n值
- 总结
前言
使用Android可视化实现斐波那契数，利用五种方法（迭代、迭代改进、递归、显示公式、矩阵）求解计算，还有另外执行时间和不超过编程环境支持的最大整数的斐波那契等等要求
ps：算法实验要求斐波那契数列求解，还要求可视化，啊，一开始看头都大
顺带吐槽一下java代码，个人认为有些功能还挺复杂（应该是学艺不精，还经常被html的舍友说不如跟我一起C#，C#多快啊，但是没办法他是大佬，学了Android还是要用java）
（算法和代码也许会有与其他大佬雷同 作为学生我也很苦，呜呜呜）
（个人实验总结，为自己以后笔记，不作其他用途，仅供参考）
一、斐波那契数是什么？实验具体实验要求是什么？
啊 斐波那契数列 我觉得大概就是第3项开始，每一项都是等于前两项的和。
Emmmmmm ，实验要求，太懒了就直接贴老师的要求。
代码如下（递归方法）：
（int countNumber）
（countNumber 我是用来计算基本 *** 作次数的，不需要的也可以删掉,直接去掉countNumber++也不影响算法
//递归方法
public long recursion(int n) {
countNumber1++; //用于计数可以直接去掉，不影响算法
if (n == 1 || n == 2) {
return 1; //保证前两个数为1
}
if (n > 2) {
return recursion(n - 1) + recursion(n - 2); //递归调用
}
return -1;
}
递归和迭代应该不需要多解释吧，接下来是（迭代方法），（老样子countNumber用来计数）
就是将值相加，然后让前面两个数往后移
//普通迭代
public long iteration(int n) {
long result = 0, previous = 1, previousPro = 1; //previous为前一个，previousPro为再前一个
if (n == 1 || n == 2) {
countNumber2 = 1; //用于计数可以直接去掉，不影响算法
return 1;
}
if (n > 2) {
for (int i = 2; i < n; i++) {
countNumber2++; //用于计数可以直接去掉，不影响算法
result = previous + previousPro;
previousPro = previous;
previous = result;
}
return result;
}
return -1;
}
显示公式（注意返回值哦，因为是无理数）
//显示公式
public double formulas(int n) {
double result = 0;
double temp = Math.sqrt(5.0); //因为带有√5 分之一 所以要用double哦！
result = (1 / temp) * (Math.pow((1 + temp) / 2, n) - Math.pow((1 - temp) / 2, n));
return result;
}
迭代改进 不得不说迭代改进yyds 真的快
循环变量折半 然后还考虑了输入的n为奇数还是偶数
（用它就完事了，正常来说谁用递归 害）
//迭代改进算法
public long iteration_plus(int n) {
if (n > 1) {
long a;
long b = 1;
n--;
a = n & 1;
n /= 2;
while (n-- > 0) {
countNumber3++;
a += b;
b += a;
}
return b;
}
return n;
}
最后是 矩阵方法
// 关联矩阵
private static final long[][] UNIT = {{1, 1}, {1, 0}}; //定义一个上面公式中需要计算的二维数组
// 全0矩阵
private static final long[][] ZERO = {{0, 0}, {0, 0}}; //定义一个元素均为0的二维数组
public long[][] fb(int n) {
if (n == 0) { //指数n为0时返回该数组
return ZERO;
}
if (n == 1) { //指数n为1时返回该数组
return UNIT;
}
// n是偶数
if ((n & 1) == 0) {
//把（n&1） == 0换成（n%2） == 0等价 ， 唯一区别在于（n&1） == 0计算效率高
long[][] matrix = fb(n >> 1);
//n >> 1意思是指将n的二进制数向右移动1位，最高位补0。相当于把n除以2
return matrixMultiply(matrix, matrix);
}
// n是奇数
long[][] matrix = fb((n - 1) >> 1);
return matrixMultiply(matrixMultiply(matrix, matrix), UNIT);
}
public long[][] matrixMultiply(long[][] m, long[][] n) {
int rows = m.length;
int cols = n[0].length;
long[][] r = new long[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
r[i][j] = 0;
for (int k = 0; k < m[i].length; k++) {
countNumber5++;
r[i][j] += m[i][k] * n[k][j];
}
}
}
return r;
}
//具体实现矩阵相乘算法,斐波那契数矩阵计算结果
public long matrix(int n) {
long[][] m = fb(n);
return m[0][1];
}
获取文本和显示内容
（布局和绑定实例应该不需要多解释的吧，控件要绑定实例找到id哦）
我是使用了一个TextInputEditText（个人喜欢用这个而不用EditText，因为它自带动画，它好看）
来作为输入，输入需要计算的第n个数
//n为编辑输入框输入的数字，因为编辑框得到的内容为Editable类的，所以编辑框输入的内容先转为字符串再转为int类型 n = Integer.parseInt(textInputEditText.getText().toString());
一定一定一定记得要改成字符串类型的然后转成int类型，不然它app会闪退
下面是关于显示结果的（就用递归方法举例）
private BigDecimal divisor = new BigDecimal(1000000000); //（全局） //作为除数将纳秒转化成秒 //显示结果————计算的结果 //显示结果————基本 *** 作次数 //显示结果————时间 //计算程序开始时间 bigDecimal1 = BigDecimal.valueOf(System.nanoTime()); //计算结果显示 result1.setText(Long.toString(recursion(n))); //不转为字符串类型会闪退！！ //基本 *** 作次数显示 count1.setText(Long.toString(countNumber1)); //程序结束时间 endBigDecimal1 = BigDecimal.valueOf(System.nanoTime()); //BigDecimal类 先用subtract进行减法，用差值求出程序执行时间，再除法divide //因为使用System.nanoTime（）方法获取的是纳秒，需要转成秒，除以转换率转成秒 BigDecimal big1 = (endBigDecimal1.subtract(bigDecimal1)).divide(divisor); //最后显示时间 time1.setText(big1.toString());
提一下在用显示公式计算后，要转换为long类型
result4.setText((Long.toString((long) formulas(n))));关键点
- 不知道有没有注意到：返回值使用的都是long类型的，不是int类型的哦，（显示公式返回值是double，但是在设置文本显示内容的时候我也转为了long类型的）因为int类型损失的数据精度会非常非常非常严重
Log.d("1111","000"+result); //0002.971215073000005E9 2971215073 double类型
Log.d("1111","000"+(int)result); //0002147483647
Log.d("1111","000"+(long)result); //0002971215073 int损失很大 使用long
- 关于时间没用double类型，而是使用了BigDecimal，因为他更准确，而且我试了好久的double类型，因为用的时间太短了他都只显示0.0s ,虽然麻烦了点，好歹他显示了
double time = System.currentTimeMillis(); BigDecimal bigDecimal1 = BigDecimal.valueOf(System.nanoTime());2.寻找不超过编程环境的最大整数斐波那契是第几个（迭代）
执行时间和显示文本我就不说了，前面讲了，方法一样
让他内存溢出，我们变找到了最大的那个
方法：（32位和64位）
public int iteration_int() {
int a = 1, b = 1, c = 2;
for (; b < c; ) { //一旦c达到编程环境最大斐波那契数，便会产生内存溢出，从而变成一个负数，到此循环结束
a = b;
b = c;
c = a + b;
count1++;
}
return b;
}
//用迭代法寻找编程环境支持的最大整数(long型)的斐波那契数是第几个斐波那契数
public long iteration_long() {
long a = 1, b = 1, c = 2;
for (; b < c; ) { //一旦c达到编程环境最大斐波那契数，便会产生内存溢出，从而变成一个负数，到此循环结束
a = b;
b = c;
c = a + b;
count2++;
}
return b;
}
因为count在++ ，函数结束时候计数是那个溢出的，所以输出结果的计数要减一哦
3.寻找不超过编程环境的最大整数斐波那契是第几个（递归）又又又又递归，递归太慢了
我是写在点击事件里面的，感觉一点击了就开始计算 比较符合要求珞
public void onClick(View v) {
startTime = BigDecimal.valueOf(System.nanoTime());
int a = 1, b = 1;
while (true) {
b = a;
a = recursion(n);
if (a < 0) { //让他一直递归，直到内存溢出，变成负数
break;
}
n++;
}
result.setText(Integer.toString(b)); //结果输出上一个
count.setText(Integer.toString(n - 1));
endTime = BigDecimal.valueOf(System.nanoTime());
BigDecimal bigDecimal = (endTime.subtract(startTime)).divide(divisor);
time.setText(bigDecimal.toString());
}
4.根据迭代寻找到的不超过环境能支持的斐波那契是第几个，用迭代计算
老样子，开始时间，显示结果，结束时间
然后，因为要看是否能一分钟内完成，就要用BigDecimal的比较了，
具体看BigDecimal的compareTo方法
BigDecimal minBigDecimal = new BigDecimal(60);
int flag = bigDecimal.compareTo(minBigDecimal);
if(flag ==1){
time_min.setText("否");
}
if(flag <=1){
time_min.setText("是");
}
5. 30s内递归和迭代计算出的最大斐波那契是第几个
private BigDecimal minBigDecimal = new BigDecimal(30); //规定的30s private BigDecimal divisor = new BigDecimal(1000000000); //作为除数将纳秒转化成秒
public BigDecimal iterationTime30(){ //迭代 计算机能够在30s内计算出的最大斐波那契是第几个
long a = 1,b = 1,result = 0; //b为第一个 a为第二个
BigDecimal startTime2 = BigDecimal.valueOf(System.nanoTime());
while (true){
result = a+b;
m++;
b = a;
a = result; //开始时间后 一个点一个点的结束，进行时间比较，直到找到超过30s的
BigDecimal endTime2 = BigDecimal.valueOf(System.nanoTime());
subtractTime2 = (endTime2.subtract(startTime2)).divide(divisor);
int flag = subtractTime2.compareTo(minBigDecimal);
if (flag == 1){
break;
}
}
return subtractTime2;
}
public BigDecimal recursionTime30() { //递归
int a = 1, b = 1; //b为a前一个
BigDecimal startTime1 = BigDecimal.valueOf(System.nanoTime()); //开始时间 //计算机能够在30s内计算出的最大斐波那契是第几个
while (true) {
n++;
b = a;
a = recursion(n);
BigDecimal endTime1 = BigDecimal.valueOf(System.nanoTime()); //时间点
subtractTime = (endTime1.subtract(startTime1)).divide(divisor); //时间差值
int flag = subtractTime.compareTo(minBigDecimal); //和30s进行比较
if (flag ==1){
break;
}
}
return subtractTime;
}
自己在写的时候，不知道是不是全局变量用的太多，还是点击事件写的不好，占用内存太多
因为递归和迭代都是要找30s的，所以就要运行一分钟，经常导致app未响应
后面减少了全局变量，并且修改了一下点击事件才能比较好的运行结果
哈哈哈 很辛苦的终于到了最后了
最后这个就相对简单很多，因为前面公式都有啦
private int n = 1; private long x = 0, y = 0;
public int compare(int n) {
while (true) {
x = iteration_plus(n);
y = (long) formulas(n);
if (x != y) { //因为迭代改进yyds 所以用它来和显示公式比较
break; //只要值不相等 就可以结束了
}
n++;
}
return n;
}
ps:因为显示公式double类型，转为long类型时候，肯定是会有精度的丢失的，所以就会出现差值哦
总结
啊 斐波那契的实验终于做完了，我设计的布局太丑了，就不摆出来看了，方法写出来就好了
这就是自己用Android写的斐波那契实验了，
其实具体感觉写的也不是很好，还有很多地方可以优化
刚开始写文章，感觉写的也不是很好，以后加油
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）