迭代法（Java）

╰+攻爆jí腚メ 2022-03-11 09:35 390阅读 0赞

**迭代法（iteration）**，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代又分为**递推（正推）和倒推法**。

**1.递推法：**  
从小规模的问题推解出大规模问题的一种方法，也称其为正推。  
例题：Fibonacci数列；求两个整数的最大公约数。

**2.倒推法：**  
对某些特殊问题所采用的的违反通常习惯的，从后向前推解问题的方法。  
例题：  
猴子吃桃问题。一只猴子摘了若干桃子，每天吃现有桃子的一半多一个，知道第十天时就只有一个桃子了，求原有多少个桃子。

**Fibonacci数列**

> 我们知道，用传统的递归解决此问题效率十分低下，这和栈的原理有关，现在我们将递归算法改进为递推，可以使求解速度和使用的空间得到非常巨大的优化。

/**
     * 		 斐波那契数列
     *  	f(1) = f(2) = 1;f(n) = f(n - 1) + f(n - 2)(n >= 3)
     *  	对于n非常大的情况，可能最后的结果很大，所以我们输出的结果是对10007取余以后的数字
     * @author 1376417539
     *
     */
    public class Fibonacci {
    	
    	public static int Fib(int num) {
    		if(num == 1 || num == 2)
    			return 1;
    		int a = 1,b = 1,c = 0;
    		for(int i = 0;i < num;i++) {
    			c = (a + b) % 10007;
    			a = b % 10007;
    			b = c % 10007;
    		}
    		return c;
    	}
    	public static void main(String[] args) {
    		System.out.println(Fib(100));
    	}
    
    }

**求两个整数的最大公约数**

> 求两个整数的最大公约数有很多种方法，其中短除法是大家所熟知的，这里我们采用一种更为高效的算法——辗转相除法  
> 辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

**实现代码**

public class GreatestCommonDivisor {
    	
    	//短除法获取最大公约数
    	public static int maxDiv(int a,int b) {
    		int c = 0;
    		c = a % b;
    		while(c != 0) {
    			a = b;
    			b = c;
    			c = a % b;
    		}
    		return b;
    	}
    	public static void main(String[] args) {
    		System.out.println(maxDiv(12,16));
    	}
    /**
     * output:4
     */
    }

**猴子吃桃**

> 猴子吃桃问题。一只猴子摘了若干桃子，每天吃现有桃子的一半多一个，知道第十天时就只有一个桃子了，求原有多少个桃子。

**实现代码**

public class MonkeyPickPeach {
    	//a(10) = 1; a(10) = a(9) - (a(9)/2 + 1 )即 a(9) = (a(10) + 1) * 2;a(8) = (a(9) + 1) * 2..........
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int peach = 1;
    		for( int i = 0;i < 9; i++) {
    			peach = (peach + 1) * 2;
    		}
    		System.out.println(peach);
    	}
    
    }

**杨辉三角形**

public class PascalTriangle {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		sc.close();
    		int[][] tri = new int[n][n];				//我们在这里使用二维数组模拟，虽然浪费一半空间，但是方便操作
    		for(int i = 0;i < tri.length ;i++) {		//第一列全部为1
    			tri[i][0] = 1;
    		}
    		for(int i = 0;i < n;i++) {
    			for(int j = 1;j <= i;j++) {
    				tri[i][j] = tri[i-1][j] + tri[i-1][j-1];	//杨辉三角形递推公式
    			}
    		}
    		for(int i = 0;i < n;i++) {
    			for(int j = 0;j <= i;j++)
    				System.out.print(tri[i][j] + " ");
    			System.out.println();
    		}
    	}
    
    }