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

zj905

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