黑马程序员技术交流社区

标题: 对于递归算术题的思考步骤,对递归题目没头绪的可以来看看 [打印本页]

---

作者: dengwenqiang    时间: 2016-1-8 20:04
标题: 对于递归算术题的思考步骤,对递归题目没头绪的可以来看看
以下是一位大神分享的经验,在此分享给大家,希望对大家有帮助
首先是一道他碰到的一道点招面试题
/**
*
    3.一个球从100米掉落下来,每次回弹 原来高度的 1/2 ,经过10次之后 求这个球总共经过的高度  (需要递归做)
    第十次回弹多少?
* @author Kenny
*
* 思路:1,回弹的高度:
*         第一次: 50
*         第二次:25
*         第三次:12.5
*        ....
*        第n次:100/2^n
*       2,这个球经过的距离
*        第一次: sum(1)＝150;
*        第二次: sum(2)＝sum(1) +75 ;
*        第三次: sum(3)＝sum(2)+37.5;
*        第四次: sum(4)＝sum(3)+18.75;
*        ........
*        第n次: sum(n)＝sum(n-1)+sum(1)/2^(n-1) ;
*/
public class CountHigh {
    public static void main(String[] args) {
        //定义一个方法求得第十次回弹的高度,用递归
        int n = 10;
        double high =getHigh(n);
        System.out.println("第十次球回弹高度为:"+high+"米");
        //递归求得这个球经过的总距离
        double total =sum(n);
        System.out.println("第十次球通过的总距离为:"+total+"米");
    }
   
    public static double getHigh(int n) {
        double high= 100;
        if (n==1) {
            return high/2;//递归跳出条件
        }else{
            return high/(Math.pow(2,n));//否则就递归调用
        }
    }
   
    public static double sum(int n) {
        double sum1 = 150;
        if (n==1) {
            return sum1;//递归跳出条件
        }else{
//sum(n)＝    sum(n-1)+sum(1)/2^(n-1) ;
//即 return     sum(n-1)+sum(1)/2^(n-1) ,要转化为代码形式,Math.pow(2,n-1)就是 2^(n-1),转化为代码后:
//即return   sum(n-1)+sum(1)/(Math.pow(2,n-1))
            return sum(n-1)+sum(1)/(Math.pow(2,n-1));//否则就递归调用
        }
    }
}

对于递归算法题目的一般思考步骤如下
其实递归理解了也挺简单,为什么说简单,因为你只要找到规律,那么代码就出来了(下面会以一个例子说明),递归的基本思路就是:1,递归要有跳出条件,不然就成死递归会内存溢出(现在你只要简单记住就好,一般都是if(n==1){return语句}),为什么是n==1,因为通常我们做的题都是从n=1开始的,2,递归的规律,也就是核心代码,像找规律也挺简单的,你只要列举几个数值出来,看数值变化的规律就可以找到规律了,例如这题 2,这个球经过的总距离
*        第一次: sum(1)＝150;
*        第二次: sum(2)＝sum(1) +75=sum(1) +sum(1)/2 ;
*        第三次: sum(3)＝sum(2)+37.5=sum(2) +sum(1)/4;
*        第四次: sum(4)＝sum(3)+18.75=sum(3) +sum(1)/8;
*        ........
*        第n次: sum(n)＝sum(n-1)+sum(1)/2^(n-1) ;
最后得到通用表达式,sum(n)＝sum(n-1)+sum(1)/2^(n-1) ;
所以所谓的找规律就是找通用表达式,而通用表达式就可以直接作为代码写到递归核心代码中,即
public static double sum(int n) {
        double sum1 = 150;
        if (n==1) {
            return sum1;//递归跳出条件
        }else{
//sum(n)＝    sum(n-1)+sum(1)/2^(n-1) ;
//即 return     sum(n-1)+sum(1)/2^(n-1) ,要转化为代码形式,Math.pow(2,n-1)就是 2^(n-1),转化为代码后:
//即return   sum(n-1)+sum(1)/(Math.pow(2,n-1))
return sum(n-1)+sum1/(Math.pow(2,n-1));//否则就递归调用
        }
    }
总结就两句话:1,定义递归跳出条件,2,找规律

---

作者: hnsfxyzl    时间: 2016-1-8 20:34
学习               

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2