迭代算法

迭代算法

中心思想是用旧值递推新值，一直迭代下来进而得到最终解。

典型的有兔子繁殖问题

一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一-代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，向一年中每个月各有多少对兔子。

简单看，兔子数就是一个斐波那契数列
1 1 2 3 5 8 13 21 34 55 89···
从第三项开始，后一项等于前面两项之和

1+1=2

1+2=3

2+3=5

···

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
import java.math.*;
class Fibonacci {
	void creat() {
		Scanner order=new Scanner(System.in);
		int number=order.nextInt();
		order.close();
		int[] p=new int[number];
		BigInteger sum,former,latter,temp;
		sum=new BigInteger("0");
		former=new BigInteger("0");
		latter=new BigInteger("1");
		temp=new BigInteger("0");
		for(int x:p) {//斐波那契数列
			sum=sum.add(latter);
			temp=latter;
			latter=latter.add(former);
			former=temp;
			System.out.println(former+" ");
	}
			System.out.println("数列和"+sum);
	}
}
1
2
3
4
5
6
public class FibonacciText {
	public static void main(String[] args) {
		Fibonacci a=new Fibonacci();
		a.creat();
	}
}

采用大数类是为了防止数值过大溢出，另外回忆一下Java的BigInteger写法，大数类原理就是把数值以数组的形式存下来，是一种空间换精度的策略。大数不能用加减符号运算，只能通过调sum()等方法运算