Spirit

Google Code Jam - SkipStones的一种递归算法

public class SkipStones {
    private String water = "X";

    public int maxDistance(String water) {
        this.water = water;
        int max = 0;
        int sum = 0;
        for (int initial = 1; initial < water.length() + 1; initial++) {
            sum = bounce(0, initial);
            max = (sum > max ? sum : max);
        }
        return max;
    }

    private int bounce(int startDistance, int bounceDistance) {
        if (bounceDistance == 0)
            return startDistance;

        if ((startDistance + bounceDistance) > water.length())
            return -1;

        if (water.charAt(startDistance + bounceDistance - 1) == 'X')
            return startDistance;

        return bounce(startDistance + bounceDistance, bounceDistance / 2);
    }

    public static void main(String[] args) {
        SkipStones skipStones = new SkipStones();
        System.out.println(skipStones.maxDistance(args[0]));
    }
}

posted on 2005-12-15 13:29 Spirit 阅读(341) 评论(1)  编辑  收藏

评论

# re: Google Code Jam - SkipStones的一种递归算法 2009-05-10 05:41 exceptionxu

验证好像不通过。试用以下的
XXXXXXX.XXX.X......X........XXXXX......XXXXX...
得到的结果是39，但39应该是错误的，怎么算都会碰到X  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: