算法-递推

概述

　　递推法是一种应用非常广泛的常用算法之一，与递归有着非常密切的联系。

　　递推是利用问题本身所具有的递推关系求解问题的一种方法。递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。使用递推算法编程，既可使程序简练，又可节省计算时间。

　　递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。它针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解，每个子解都是由前面若干子解生成的。我们把这种由前面的子解得出后面的子解的规则称为递推关系。

实施递推的步骤

1. 确定递推定量

   　　　　应用递推算法解决问题，要根据问题具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。

2. 建立递推关系

   　　递推关系是指如何从变量的前一些值推出其下一个值或从变量的后一些值推出其上一个值的公式。

   　　递推关系是递推的依据，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，不断尝试推理，才能确定问题的递推关系。

3. 确定初始条件

   　　对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始值，这是递推的基础。

4. 对递推过程进行控制

   　　　　递推过程不能无休止地执行下去。递推过程在什么时候结束，满足什么条件结束，这是递推算法必须考虑的递推过程控制问题。

   　　递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步根据问题的具体实际归纳出用来结束递推过程的条件。

递推算法框架描述

1. 简单顺推算法

   　　　　顺推即从前往后推，从已求得的规模为1,2,3，…，i-1的一系列解，推出问题规模为i的解，直至得到规模为n的解。框架描述:

   1 2 3 4

   f(1:i-1)=<初始值>; for(k=i;k<=n;k++) f(k)=<递推关系式>; System.out.println(f(n));

2. 简单逆推算法

   　　　　逆推即从后往前推，从以求得的规模为n，n-1，…，i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解。

   1 2 3 4

   f(n:i+1)=<初始值>; for(k=i;k>=1;k--) f(k)=<递推关系式>; System.out.println(f(1));

3. 二维数组顺推算法

   　　简单递推问题设置一维数组实现，较复杂的递推问题需设置二维或二维以上数组。

   1 2 3 4 5

   f(1,1:m)=<初始值>; for(k=2;k<=m;k++) for(j=1;j<=m;j++) f(k,j)=<递推关系式>; System.out.println(f(n,m));

4. 多关系分级递推算法

   　　当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。

   1 2 3 4 5 6 7 8 9 10 11

   f(1:i-1)=<初始值>; for(k=i;k<=n;k++){ if(<条件一>) f(k)=<递推关系1>; . . . if(<条件m>) f(k)=<递推关系式m>; } System.out.println(f(n));

相关例题

1.摆动数列

　　已知递推数列：a(1)=1, a(2i)=a(i)+1, a(2i+1)=a(i)+a(i+1), i为正整数，试求该数列的第n项与前n项中哪些项最大？最大值为多少？

分析

递推式：

1. 当i为偶数时， a(i)=a(i/2)+1
2. 当i为奇数时， a(i)=a((i+1)/2)+a((i-1)/2)

每得一项与最大值max比较，如果a(i)>max,则max=a(i).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.Scanner;
public class 摆动数列_递推 {
	static int n,max=0;
	static int ar[];
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		ar=new int[n+1];
		ar[1]=1;
		f(n);
		System.out.println("最大项为："+max);
	}
	public static void f(int n){
		for(int i=2;i<=n;i++){
			if(i%2==0){
				ar[i]=ar[i/2]+1;
				if(ar[i]>max) max=ar[i];
			} 
			if(i%2==1){
				ar[i]=ar[(i+1)/2]+ar[(i-1)/2];
				if(ar[i]>max) max=ar[i];
			} 
		}
	}
}

2.整数划分问题

　　正整数s（简称为和数）的划分（又称分划）是把s分成为若干个正整数（简称为零数或部分）之和，划分式中允许零数重复，且不记零数的次序。如：

k=2: 1+1 ;2

k=3:1+1+1 ;1+2;3

k=4:1+1+1+1 ;1+1+2;1+3;4

分析

　　和数k的划分式与和数k-1的划分式存在以下递推关系：

1. 在所有和数k-1的划分前加一个零数“1”都是和数k的划分式。
2. 和数k-1的划分式的前两个零数作比较，如果第一个零数x1小于第2个零数x2，则把第1个零数加一后成为和数k的划分式。

设置一个三维数组ar[][][k] [j] [i] 表示和数k第j个划分式的第i个数，k从2开始，初始条件为：

ar[2] [1] [1]=1,ar[2] [1] [2]=1,ar[2] [2] [1]=2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.Scanner;

public class 整数划分_递推 {
	static int n,x=2,y;//x为当前划分式的数量
	static int ar[][][];
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		ar=new int [n+1][800][n+2];
		ar[2][1][1]=1;//初始条件
		ar[2][1][2]=1;
		ar[2][2][1]=2;
		f(n);
		printf();
	}
	public static void f(int n){//递推函数
		for(int i=3;i<=n;i++){
			for(int j=1;j<=x;j++){//此for循环给每个划分式加一
				ar[i][j][1]=1;//划分式的一个数为一
				for(int t=2;t<=i;t++)
					ar[i][j][t]=ar[i-1][j][t-1];//后面加上前一个和数的划分式
			}
			y=x;
			for(int j=1;j<=x;j++){
				if(ar[i-1][j][1]<ar[i-1][j][2]){//判断前一个和数的每个划分式的第一个零数是否小于第二个
					y++;//划分式加一
					ar[i][y][1]=ar[i-1][j][1]+1;//和数i的第y个划分式第一个数等于和数i-1的第i个划分式的第一个数加一
					for(int t=2;t<=i-1;t++)
						ar[i][y][t]=ar[i-1][j][t];
				}
			}
			y++;ar[i][y][1]=i;//和数i的最后一个划分式，（就是自己本身）
			x=y;
		}
	}
	public static void printf(){
		for(int i=1;i<=x;i++){
			System.out.print(ar[n][i][1]);
			int j=2;
			while(ar[n][i][j]>0){
				System.out.print("+"+ar[n][i][j]);j++;
			}
			System.out.println();
		}
	}
}

3.水手分椰子问题

　　n名水手来到一个岛上，采了一堆后，因为疲劳都睡着了。一段时间后，第一个水手醒来，悄悄地将椰子等分成n份，多出m个椰子，便给了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起，继续睡觉。不久，第二名水手醒来，同样将椰子等分成n份，恰好也多出m个，也给了猴子。然后自己也藏了一份，再将剩下的椰子重新合在一起。以后水手醒来，发现椰子少了许多，心照不宣，便把剩下的椰子分成n份，恰好又多出m个，给了猴子。

　　问：原来这堆椰子至少有多少个？

分析

　　根据相邻两人所藏的椰子数相同，确定迭代方程：(n-1)×ar[i]=n×ar[i+1]+1

　　ar[i]为前一个水手分的每一份的个数，ar[i+1]为后一个水手分的每一份的个数.因为前一位水手要给自己留一份，剩下的(n-1)份留个下一个水手分，此时前一个水手分完之后的椰子数和后一个水手还未开始分椰子的椰子数是相同的。

　　如果式子:ar[i]=(n×ar[i+1]+1)×(n-1)经过n次迭代ar[i]都为整数，即找到一个解sum=n×ar[1]+m (因为经过n次迭代ar[1]为第一位水手分的椰子数)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import java.util.Scanner;
public class 水手分椰子 {
	static int n,m;
	static double ar[];
	static double sum,k;
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		m=in.nextInt();
		ar=new double [n+2];
		k=n;
		f(n,m);
		System.out.println("椰子至少有"+sum+"个.");
		print();
	}
	public static void f(int n,int m){
		int i=n+1;
		ar[n+1]=k;
		while(i>1){//当i=1表示已经经过n次迭代
			i--;
			ar[i]=(n*ar[i+1]+m)/(n-1);
			if(ar[i]!=Math.floor(ar[i])){//floor(double x)函数: 取不大于x的最大整数
				k++;
				ar[n+1]=k;
				i=n+1;
			}
		}
		sum=ar[1]*n+m;
	}
	public static void print(){
		for(int i=1;i<=n;i++){
			double x=ar[i]*n+m;
			System.out.println("第"+i+"个水手将"+x+"个椰子分成"+n+"份,自己藏了"+ar[i]+"个椰子.");
		}
	}
}

4.排队买票问题

　　一场电影开始前，售票工作正在紧张进行中。每张电影票为50元，现在有i个人排队等待购票，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这i个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（拿同样面值钞票的人对换位置为同一种排队）

分析

　　第m+n个人排队购票，第m+n个人站在第m+n-1个人的后面，则第m+n个人的排队方式可由下列两种情况获得:

1. 第m+n个人手持100元钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元钞票，此时情况共有f(m,n-1)。

2. 第m+n个人手持50元钞票，则在他之前的m+n-1个人中有m-1个人手持50元钞票，有n个人手持100元钞票，此时情况共有f(m-1,n)。

   所以，递推式为:f(m,n)=f(m,n-1)+f(m-1,n)

代码

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.Scanner;

public class 排队购票_递推 {
	static long dp[][];
	static int m,n;
	static Scanner in=new Scanner(System.in);
	public static void main(String args[]){
		m=in.nextInt();
		n=in.nextInt();
		dp=new long [m+1][n+1];
		dp();
		System.out.println(dp[m][n]);
	}
	public static void dp(){
		for(int i=1;i<=m;i++)
			dp[i][0]=1;
		
		for(int i=1;i<=n;i++)
			for(int j=i;j<=m;j++){
				dp[j][i]=dp[j-1][i]+dp[j][i-1]; //递推式
			}
	}
}

这种解法类似于动态规划。

总结

　　递推的话，就写到这了吧。end!