美丽联合2019届校招测试类笔试题算法题方格走法-白红宇的个人博客

美丽联合2019届校招测试类笔试题算法题方格走法

发布日期：2021-05-09 04:15:18 浏览次数：14 分类：博客文章

本文共 1211 字，大约阅读时间需要 4 分钟。

编程题]方格走法

热度指数：40 时间限制：1秒空间限制：32768K

有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。

给定两个正整数int x,int y，请返回小团的走法数目。

输入描述:

输入包括一行，空格隔开的两个正整数x和y，取值范围[1,10]。

输出描述:

输出一行，表示走法的数目

示例1

输入

3 2

输出

10 思路分析 直接用递归就能简单明了的解决： 例如输入1,1 （2*2的方格） 递归过程中会存在如下三种情况： ① 网格上一个点有两条路可走（一个节点有两个儿子节点）， 　　　例如当x=0,y=0 时，可向下或向右走 ，所以 return f(++x,y)+f(x,++y) ② 在边界的情况下，一个节点只有一个儿子节点，只有一条路可走, 　　　例如： 　　　　当x=0,y=1 时，y已经到了边界值， 所以 return f(++x,y) 　　　或 　　　　当x=0,y=1 时，y已经到了边界值， 所以 return f(x,++y)

③ 递归到终点（递归到树的叶子结点）后走法加一  　　　　例如：当x=1，y=1时，已经到目标位置，所以return 1 如果是按上面思路，从左上往右下走，还有给递归函数另外另个两个参数最为边界值判断， 所以，不如直接终点变起点，起点变终点，从终点开始，向上或向左走，边界值只需要判断是否大于0就行了，因为0就是x和y的边界 Java 递归代码如下

import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner sca = new Scanner(System.in);        int x = sca.nextInt();        int y = sca.nextInt();        System.out.println(f(x,y));    }    public static int f(int x,int y){        if(x==0&&y==0)            return 1;        else if(x==0 && y>0){            return f(x,--y);        }        else if(y==0 && x>0){            return f(--x,y);        }        else{            return f(x,--y)+f(--x,++y); //在这为啥要++y？因为前面是向左走（--y）了，而后面是向上走（--x），所以y不能变，要加回来        }    }}

上一篇：Java中Synchronized的用法

下一篇：猿辅导2019校招技术类笔试题编程题2：拍照队形

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

输入描述:

输出描述:

输入

输出

发表评论

最新留言

关于作者

推荐文章