黑马程序员技术交流社区

标题: Java递归与反向思维的实例 [打印本页]

---

作者: CodeUser1997    时间: 2018-8-2 22:29
标题: Java递归与反向思维的实例


** 假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木
    棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切
    分木棒。
    求最多有 m 个人时，最少要切分几次？
    例如:n ＝ 8， m ＝ 3 时如下所示，切分 4 次就可以了。
            == == == == | == == == ==                       第一次
            == == | == ==       == == | == ==               第二次
            == | ==   == | ==      == | ==   == ==          第三次
            ==  ==  ==  ==         ==  ==    == | ==        第四次
            ==  ==  ==  ==         ==  ==  ==  ==        最终切完结果
* @question
*/
public class DivideClub {
    public static void main(String[] args){
        System.out.println(getTimes(20,3,1));
        System.out.println(getTimes02(20,3));
    }

    /**
     * @thought         采用递归的思想
     * @param length    木棒长度
     * @param people    人的个数
     * @param currents    木棒的个数
     * @return          切了多少次
     */
public static int getTimes(int length,int people,int currents){
        if(currents>=length){
            return 0;
        }else if(currents<people){
            return 1+getTimes(length,people,currents*2);
        }else{
            return 1+getTimes(length,people,currents+people);
        }
    }

    /**
     * @though  反向思维，将1厘米的木棒组合成length长度即可，
     *          即people个人只要组合的长度为length长度
     * @param length
* @param people
* @return
*/
public static int getTimes02(int length,int people){
        int counts=0;
        int currents=1;//当前木棒长度
        while(currents<=length){
            currents+=currents<people?currents:people;
            counts++;
        }
        return counts;
    }
}

---

作者: CodeUser1997    时间: 2018-8-2 22:32
** 假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木
    棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切
    分木棒。
    求最多有 m 个人时，最少要切分几次？

    例如:n ＝ 8， m ＝ 3 时如下所示，切分 4 次就可以了。
            == == == == | == == == ==                       第一次
            == == | == ==       == == | == ==               第二次
            == | ==   == | ==      == | ==   == ==          第三次
            ==  ==  ==  ==         ==  ==    == | ==        第四次
            ==  ==  ==  ==         ==  ==  ==  ==        最终切完结果
* @question
*/
public class DivideClub {
    public static void main(String[] args){
        System.out.println(getTimes(20,3,1));
        System.out.println(getTimes02(20,3));
    }

    /**
     * @thought         采用递归的思想
     * @param length    木棒长度
     * @param people    人的个数
     * @param currents    木棒的个数
     * @return          切了多少次
     */
    public static int getTimes(int length,int people,int currents){
        if(currents>=length){
            return 0;
        }else if(currents<people){
            return 1+getTimes(length,people,currents*2);
        }else{
            return 1+getTimes(length,people,currents+people);
        }
    }

    /**
     * @though  反向思维，将厘米的木棒组合成length长度即可，
     *          即people个人只要组合的长度为length长度
     * @param length
     * @param people
     * @return
     */
    public static int getTimes02(int length,int people){
        int counts=0;
        int currents=1;//当前木棒长度
        while(currents<=length){
            currents+=currents<people?currents:people;
            counts++;
        }
        return counts;
    }
}

---

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

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