分享下以前做过的递归题目

1. 递归算法解题步骤

(1) 分析问题、寻找递归关系。找出大规模问题和小规模问题的关系。
(2) 找出停止条件，控制递归。
(3) 设计函数、确定参数。

2. 问题描述：
   整数的分划问题。

   如，对于正整数n=6，可以分划为：
   6
   5+1
   4+2, 4+1+1
   3+3, 3+2+1, 3+1+1+1
   2+2+2, 2+2+1+1, 2+1+1+1+1
   1+1+1+1+1+1+1

   现在的问题是，对于给定的正整数n,编写算法计算出其分划得数目。

3. 问题分析和递归关系建立

   从上面n=6的实际例子可以看出，很难找到大规模问题P(n)和小规模问题P(n-d)(d=1或2或3...)的关系。
根据n=6的实例发现"第一行及以后的数据不超过6，第二行及以后的数据不超过5...，第六行的数据不超过1"。
   因此，定义一个函数Q(n,m)，表示整数n的"任何加数都不超过m"的分划得数目，n的所有分划数目P(n)就应该
表示为Q(n,n).

   一般地，Q(n,m)有以下递归关系：
   (1) Q(n,n) = 1+Q(n,n-1);
   (2) Q(n,m) = Q(n,m-1) + Q(n-m,m) (m<n)
       Q(n,m-1)表示被加数中不包含m的分划数目；
        Q(n-m,m) 表式被加数中包含m的分划数目。

4. java实现：

/**
 * create on 2010.05.21 TODO:递归
 * 
 * @author 毛正吉
 * @version v1.0
 * 
 */
public class IntegerDivision {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		IntegerDivision id = new IntegerDivision(6);
		int count = id.divInteger(id.getN(), id.getN());
		System.out.println(count);

	}

	private int n;

	public IntegerDivision(int _n) {
		n = _n;
	}

	/**
	 * 递归求解
	 * 
	 * @param n
	 * @param m
	 * @return
	 */
	public int divInteger(int n, int m) {
		if (n < 1 || m < 1) {
			System.out.println("输出参数错误！");
		} else if (n == 1 || m == 1) {
			return 1;
		} else if (n < m) {
			return divInteger(n, n);
		} else if (n == m) {
			return divInteger(n, n - 1) + 1;
		} else {
			return divInteger(n, m - 1) + divInteger(n - m, m);
		}
		return 0;
	}

	public int getN() {
		return n;
	}

	public void setN(int n) {
		this.n = n;
	}

}

  

评论

6 楼 maozj 2010-05-24  

fuliang 写道

简单修改楼主的代码成动态规划实现：

public class DivisionNum {
	private int cache[][];
	private int n;
	
	public DivisionNum(int n){
		this.n =  n;
		this.cache = new int[n+1][n+1];
	}
	
	public static void main(String[] args) {
		int n = Integer.parseInt(args[0]);
		DivisionNum dn = new DivisionNum(n);
		int num = dn.divisionNum();
		System.out.println("Division partition number: " + num);
	}
	
	public int divisionNum(){
		return this.divisionNum(n,n);
	}

	private  int divisionNum(int n,int m){
		assert(n > 0 && m > 0);
		
		if(n == 1 || m == 1)
			return 1;
		if(cache[n][m] != 0){
			return cache[n][m];
		}else if(n < m){
             cache[n][n] = divisionNum(n,n);
			return cache[n][n];
		}else if(n == m){
            cache[n][n-1] = divisionNum(n,n-1);
			return  cache[n][n-1] + 1;
		}else{
            cache[n][m-1] = divisionNum(n,m-1);
            cache[n-m][m] = divisionNum(n-m,m);
			return cache[n][m-1] + cache[n-m][m];
		}
	}
}

ok... 分享

5 楼 fuliang 2010-05-24  

简单修改楼主的代码成动态规划实现：

public class DivisionNum {
	private int cache[][];
	private int n;
	
	public DivisionNum(int n){
		this.n =  n;
		this.cache = new int[n+1][n+1];
	}
	
	public static void main(String[] args) {
		int n = Integer.parseInt(args[0]);
		DivisionNum dn = new DivisionNum(n);
		int num = dn.divisionNum();
		System.out.println("Division partition number: " + num);
	}
	
	public int divisionNum(){
		return this.divisionNum(n,n);
	}

	private  int divisionNum(int n,int m){
		assert(n > 0 && m > 0);
		
		if(n == 1 || m == 1)
			return 1;
		if(cache[n][m] != 0){
			return cache[n][m];
		}else if(n < m){
             cache[n][n] = divisionNum(n,n);
			return cache[n][n];
		}else if(n == m){
            cache[n][n-1] = divisionNum(n,n-1);
			return  cache[n][n-1] + 1;
		}else{
            cache[n][m-1] = divisionNum(n,m-1);
            cache[n-m][m] = divisionNum(n-m,m);
			return cache[n][m-1] + cache[n-m][m];
		}
	}
}

4 楼 maozj 2010-05-24  

mccxj 写道

动态规划算法~~~用递归效率很差劲~

恩 如果可以用动态规划算法实现 可以期待一下。。。

3 楼 mccxj 2010-05-23  

动态规划算法~~~用递归效率很差劲~

2 楼 whaosoft 2010-05-22  

gundumw100 写道

那么，这个可以用在什么地方呢？

估计是做个小练习 要不就是面试题

1 楼 gundumw100 2010-05-22  

那么，这个可以用在什么地方呢？