算法练习题(五)——机器人走方格
2023-06-13 09:18:38 时间
import java.util.Scanner;
/**
* 机器人走方格
*
* 有一个X*Y的网格,-个机器人只能走格点,
* 且只能向右或向下走,要从左上角走到右下角。
* 请设计-个算法,计算机器人有多少种走法。
* 给定两个正整数int x,int y,请返回机器人的走法数目。
* 保证x +y小于等于12。
*
*
* 先找规律:
* 发现
* 当前位置的走法 是 左边一格位置的走法 + 上边一格位置的走法
* f(x,y) = f(x-1,y)+f(x+y-1)
* 你返现2*2的时候还可以直接看出来 但是3*3的时候 就直接看不出来了
* 需要你想到 拿3*3的为例
* 你右走一步 下一步面临的就是3*2的样子 直接 加上3*2时的结果即可
* 此时你右走(x-1) 面临的是3*1 -----1种
* 下走(y-1) 面临的是2*2 -----2种
* 可以算出 3*2的时候 == 1+2 种
* 下走同上
* 可算出2*3的时候 == 1+2 种
* 可以算出3*3 == 6种
*
* 可以总结出:
* f(x,y) = f(x-1,y)+f(x+y-1)
*/
public class RecursionTest02 {
public static void main(String[] args) {
RecursionTest02 recursionTest02 = new RecursionTest02();
Scanner scanner =new Scanner(System.in);
System.out.print("input:");
int X = scanner.nextInt();
int Y = scanner.nextInt();
// 方法1
// System.out.println(recursionTest02.solution1(X,Y));
// 方法2
System.out.println(recursionTest02.solution2(X,Y));
}
/**
* 方法1
* 递归(简洁 但是隐藏了许多细节 看得人不容易理解)
* f(x,y) = f(x-1,y)+f(x+y-1)
* @param X
* @param Y
* @return f(x-1,y)+f(x+y-1)
*/
public int solution1(int X,int Y){
if (X<=0||Y<=0){return 0;}
else if (X==1||Y==1){return 1;}
else {
return solution1(X-1,Y)+solution1(X,Y-1);
}
}
/**
* 方法2
* 迭代
* 这里不同于上一题走楼梯的是 那个传入的是1个参数
* 可以使用一维的结构去保存他们
* 而这里是2个参数 且 两个参数不同步变化
* 所以这里可以引入二维数组去解题
* 如下: Y
* ------------------
* 1 1 1 1 1
* ------------------
* 1 2 3
* ------------------
* 1 3 6
* ------------------
* 1
* ------------------
* X 1 (X,Y)
* ------------------
*
* @param X
* @param Y
* @return
*/
public int solution2(int X,int Y){
int [][] state= new int[X][Y];
if (X<0||Y<0){return 0;}
// 初始化第一列和第一行
for (int i = 0; i < X; i++) {
state[i][0] = 1 ;
}
for (int i = 0; i < Y; i++) {
state[0][i] = 1 ;
}
// 将给定的X*Y网格对应的各个位置走法 全部填入对应位置
for (int i = 1; i < X; i++) {
for (int j = 1; j < Y; j++) {
state[i][j] = state[i-1][j]+state[i][j-1];
}
}
return state[X-1][Y-1];
}
}
相关文章
- 滴滴新算法让你应对女友?道翰天琼认知智能机器人平台API接口大脑为您揭秘-64
- 机器人工程专业师生的第二张名片
- 机器人运动|浅谈Time Elastic Band算法
- 手把手教你用低代码30分钟实现ChatGPT AI机器人
- 焊接机器人的组成有哪些部件
- 公开「处刑」!波士顿动力的搬砖机器人,私下竟「翻车」不断
- ROS机器人Diego 1#制作(四)base controller—线速度的标定详解架构师
- 集尘扫地机怎么选,45天不用倒垃圾的米家集尘扫拖机器人给你答案!
- 加州大学教会机器人切菜 还能给人做手术
- 机器人医生用于辅助医疗,有多靠谱?
- 深度丨微软小冰资深产品总监曹文韬:如何把聊天机器人打造为一个“知音+专家”的产品
- 预告:从传感器和算法原理讲起,机器人是如何避障的丨硬创公开课
- 预告:解析波士顿Handle机器人背后的技术 | 硬创公开课
- 第30届IROS正式开幕,深度学习当道的机器人会议都有什么精彩亮点?(多图) | IROS 2017
- 一年半超过Cyberdyne:尖叫科技要用大家电的价格卖外骨骼机器人