Go语言视频零基础入门到精通

javalearner

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;
        }
}

运行结果：
11[/code]

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/20/000448796.zip