2017-02-22-递归
Xplorist Lv6
  2017-02-22 14:23:01 2017-02-22 14:23      

2017-02-22-递归

实例1：

递归实现累加和阶乘

递归的核心：1递归结束标志，2递归的递进方式；

累加核心代码：

1
2
3
4
5
6
public int run(int n){
        if(n==1){
            return 1;
        }
        return n+run(n-1);
    }

阶乘的核心代码：

1
2
3
4
5
6
public int runFactorial(int n){
        if(n==1){
            return 1;
        }
        return n*runFactorial(n-1);
    }

阶乘的非递归实现思路：

将每次的结果存储到一个结果变量中，通过循环实现递减和相乘。

阶乘的非递归实现核心代码：

1
2
3
4
5
6
7
public int runF1(int n) {
        int result = 1;
        for (int i = n; i > 1; i--) {
            result *= i;
        }
        return result;
    }

实例2：

 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 
用户输入项数后就告诉他该项的值

规律分析：在从第3项开始，后面的结果都是该项的前两项的相加之和。

代码实现思路：递归实现，结束标志为前两项，递进标志为减一和减二。

实现核心代码：

1
2
3
4
5
6
7
public int run2(int n){
        int result=1;
        if(n>2){
            result=run2(n-1)+run2(n-2);
        }
        return result;
    }

思路2：不使用递归来实现斐波那契数列

分析：由于斐波那契数列的规律和数的后两位数有关系，也就是要确定一个数必须知道它的前两位，在循环中必须找出它的前两位才能够确定

这个数，在这里就要使用到数组，数组来存储前两个数的结果，然后将前两个数相加得到我们需要的数。

仔细分析，其实这里不用数组也能实现算法。

不使用递归也不使用数组的 关键思路：使用三个变量来进行交换，然后通过两层循环来控制交换的移动，实际原理同递归相同，
     * 设置循环的最底层结束标志，设置递变的变量，其实递归必定是先找到最底层的标志才开始一步一步向上变化的，
     * 递变就需要用到循环，外层循环的作用是从最底层开始变化，里层循环的作用是使三个变量交替赋值和移动。

使用循环和数组的算法核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int run21(int n) {
        int result = 1;

        int[] array = new int[100];

        for (int i = 0; i < n; i++) {
            array[i] = 1;
            if (i > 1) {
                array[i] = array[i - 1] + array[i - 2];
            }
            result = array[i];
        }

        return result;
    }

不使用数组和递归实现斐波那契数列的核心算法代码：

（自己想出来的，感觉好厉害，夸奖一下自己。哈哈哈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int run22(int n) {
        int result = 1;

        if (n > 2) {
            int first = 1;
            int second = 1;
            int third = 1;
            for (int i = 3; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    if (j == (i - 2)) {
                        first = second;
                    }
                    if (j == (i - 1)) {
                        second = third;
                    }
                    if (j == i) {
                        third = first + second;
                    }
                }
                result = third;
            }
        }
        return result;
    }

实例3：

上台阶： 两种方法：1一次1阶，一次2阶； 10层 求有多少种上法；

思路：1找规律，运用数学归纳法；

1,1;

2,2;

3,3; 

4,5;

可以直接找出：从第三个数开始，后面的每个数都是前两个数之和。基本类似 斐波那契数列。

2运用数学思维抽象问题，直观解决问题；

将这个问题抽象为x+2y=10,找问题的解的个数，

如果不靠考虑顺序就是排列组合中的组合情况，运用穷举法就能够找出存在的多少个情况；

如果考虑顺序的话，就需要运用到排列公式，n!/(n-m)!;

数学归纳法的核心代码：

1
2
3
4
5
6
7
8
public int run32(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }
        return run32(n-1)+run32(n-2);
    }

不考虑顺序的组合情况的核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int run3(int n) {
        int j = 0;
        int count = 0;
        for (int i = 0; i <= n; i++) {
            if ((n - i) % 2 != 0) {
                continue;
            } else {
                j = (n - i) / 2;
                count++;
            }
        }
        return count;
    }

考虑顺序的排列情况的核心代码（未完成）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int run31(int n) {
        int count = 0;
        int j = 0;
        for (int i = 0; i <= n; i++) {
            if ((n - i) % 2 != 0) {
                continue;
            } else {
                j = (n - i) / 2;
                if (i != 0 && j != 0) {
                    if (i <= j) {
                        count = 1;// 没写完，要用到阶乘公式，太复杂，而且没必要
                    }
                }
                count++;
            }
        }

        return count;
    }

实例4：

泡茶：
 *我门有杯子 3种，有茶叶 3种；
 *让杯子泡茶；
 *我们用户过来之后，可以选择杯子，可以选择茶叶，然互我们给她泡茶

分析：1.在还没涉及到构造方法的思路：在一个方法中列出可能的选择，然后将这些写死了的选择赋给类的属性。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class Cup {
    public String name;
    
    public String choose(int i){
        String str=null;
        switch (i) {
        case 1:
            str="小杯子";
            break;
        case 2:
            str="中杯子";
            break;
        case 3:
            str="大杯子";
            break;

        default:
            break;
        }
        return str;
    }
    
    public void pao(Tea t){
        System.out.println("有1,2,3种杯子，输入1,2,3选择杯子：");
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        if (i > 3) {
            System.out.println("没有这种杯子");
        } else{
            this.name=this.choose(i);
            
            System.out.println("有1,2,3种茶，输入1,2,3选择茶：");
            i = scanner.nextInt();
            if (i > 3) {
                System.out.println("没有这种茶");
            } else {
                t.name = t.choose(i);
                System.out.println("用【" + this.name + "】来泡【" + t.name+"】");
            }
        }
    }

public class Tea {
    public String name;
    
    public String choose(int i){
        String str=null;
        switch (i) {
        case 1:
            str="茉莉花茶";
            break;
        case 2:
            str="苦荞茶";
            break;
        case 3:
            str="龙井茶";
            break;

        default:
            break;
        }
        return str;
    }
}

实例5：

人吃食物：
 * 1人有性别,名字，胃口大小，获取食物(随机获取)，人需要吃食物
 * 2食物，食物有名字，饱食度
 * 3让人吃食物

思路：基本上同上个实例，主要难点在于，如何获取食物上面。

核心代码：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Person {
    public String name;
    public String sex;
    public int stomach;
    
    public Food findFood(){
        Food food=null;
        int i=(int)(Math.random()*5);
        switch (i) {
        case 1:
            food=new Food();
            food.name="苹果";
            food.fullOrNot=2;
            break;
        case 2:
            food=new Food();
            food.name="香蕉";
            food.fullOrNot=1;
            break;
        case 3:
            food=new Food();
            food.name="兔子";
            food.fullOrNot=5;
            break;
        case 4:
            food=new Food();
            food.name="野猪";
            food.fullOrNot=9;
            break;

        default:
            break;
        }
        return food;
    }
    
    public void eat(Food food){
        System.out.print("【"+this.name+"】吃了【"+food.name+"】");
        if(food.fullOrNot>this.stomach){
            System.out.println("然后吃撑了");
        }else if(food.fullOrNot==this.stomach){
            System.out.println("然后吃饱了");
        }else{
            System.out.println("然后没吃饱");
        }
    }

public class MainGate {

    public static void main(String[] args) {
        Person p=new Person();
        p.name="张三";
        p.sex="男";
        p.stomach=7;
        Food f=p.findFood();
        if(f!=null){
            System.out.println(p.name+"找到了食物");
            p.eat(f);
        }else{
            System.out.println(p.name+"没有找到食物");
        }
    }

}

  • 本文标题：2017-02-22-递归
  • 本文作者：Xplorist
  • 创建时间：2017-02-22 14:23:01
  • 本文链接：https://xplorist.tech/2017/02/22/2d0323cb7f6c/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论