算法趣题第四天

深藏阁楼爱情的钟 2022-12-07 11:42 114阅读 0赞

# 本篇介绍 #

本篇博客的题目来源于《程序员的算法趣题》。

这是一本非常有意思的算法书，不像其他的算法书从链表，二叉树等数据结构原理入手，通过一道道的题目，从实际问题出发，来使读者了解算法的运用。不过唯一不足之处在于书中的算法源码多用Ruby与JavaScript来实现，对于刚上手学习编程的读者来说，这两种语言不会是首选的编程语言。因此，博主使用Java对书中的源码进行重构实现，对使用Java的初学者能够明白其中的算法。

PS：博主的技术水平有限，可能代码会比较的臃肿冗余，在时间复杂度和空间复杂度上无法做到最优，也欢迎在评论区讨论留言，共同进步。

# 系列链接 #

[算法趣题 第一天][Link 1]  
[算法趣题 第二天][Link 2]  
[算法趣题 第三天][Link 3]  
[算法趣题 第四天][Link 4]

# Q8 优秀的扫地机器人 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center]

## 难点 ##

本题的难点在于如何编程**模拟机器人的行径**以及**判断路径是否重复**

## 源码 ##

import java.util.ArrayList;
    import java.util.List;
    
    public class Test08 {
        
    	
    	//定义行走路径的坐标
    	private static int[][] objects = {
        {
        1,0},{
        -1,0},{
        0,1},{
        0,-1}};
    	//计数
    	private static int count = 0;
    	//步数常量
    	private static final int N = 12; 
    	
    	public static void main(String[] args) {
        
    		//声明一个列表存放行径数组
    		List<int[]> steps = new ArrayList<int[]>(N);
    		//起始点添加坐标（0,0）
    		steps.add(new int[] {
        0,0});
    		//计算路径数
    		count = moveNext(1,steps);
    		System.out.print(count);
    	}
    	
    	//模拟移动
    	private static int moveNext(int nextStep,List<int[]> steps) {
        
    		//步数超过则结束移动
    		if((steps.size())==N+1){
        
    			return 1;
    		}
    		//计数
    		int cnt = 0;
    		int i;
    		for(int j =0;j<objects.length;j++) {
        
    			i=nextStep;
    			for(int k = steps.size();k>nextStep;k--) {
        
    				steps.remove(k-1);
    			}
    			//记录路径，
    			int[] next = {
        steps.get(i-1)[0]+objects[j][0],steps.get(i-1)[1]+objects[j][1]};
    			//路径不重复
    			if(!contains(steps,next)) {
        
    				//添加路径
    				steps.add(next);
    				//递归
    				cnt+=moveNext(++i,steps);
    			}
    		}
    		return cnt;
    	}
    	//判断路径是否重复
    	private static boolean contains(List<int[]> steps,int[] next) {
        
    		boolean res = false;
    		//防止列表为空
    		if(steps==null) {
        
    			return res;
    		}
    		//遍历路径列表
    		for(int i = 0;i<steps.size();i++) {
        
    			//判断路径坐标
    			if(steps.get(i)[0]==next[0]&&steps.get(i)[1]==next[1]) {
        
    				return true;
    			}
    		}
    		return res;
    	}
    }

## 要点 ##

1.  解决这个问题的关键在与如何表达移动路径，博主这里是定义了一个二维数组来表示坐标。
    
        //定义行走路径的坐标
        private static int[][] objects = {
              {
              1,0},{
              -1,0},{
              0,1},{
              0,-1}};
    
    这个数组内的坐标分别表示左右上下移动，这样通过初始化起始坐标(0,0)，便可通过数组元素的加减来表示路径。
2.  在本题中还使用了递归的设计思想。递归是一种很常用的编程思想，基本上包含三要素：
    
    1.  递归的定义：接受什么参数，返回什么值，代表什么意思 。当函数直接或者间接调⽤⾃⼰时，则发⽣了递归
    2.  递归的拆解：每次递归都是为了让问题规模变⼩
    3.  递归的出⼝：必须有⼀个明确的结束条件。因为递归就是有“递”有“归”，所以必须又有一个明确的点，到了这个点，就不用“递下去”，而是开始“归来”。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 1]  
        就用阶乘的例子来说明一下吧
    
        // 算 n 的阶乘(假设n不为0)
        	public int f(int n){
              
        		if(n <= 2){
              
            		return n;
        		}
        		// 把 f(n) 的等价操作写进去
        		return f(n-1) * n;
        	}
    
    当n=1或n=2时，n!是等于其自身的，当n>3时，我们直接调用(n-1)!乘上n，这样就得到了n!。

**PS：这道题可以说是目前做到最难的一题了，可能对于初学者理解有一定的难度。博主也是想了许久才碰巧完成了，可能在讲解上有许多欠考虑的地方，见谅。**

# 结语 #

如果说这篇文章有让你学到一定的知识的话，不妨点个赞和关注，让博主能够看到。如果讲解中有什么错误和疏忽，也劳烦在评论中指出或提问，博主会第一时间进行更新和答复，谢谢！

[Link 1]: https://blog.csdn.net/weixin_44018540/article/details/108510424
[Link 2]: https://blog.csdn.net/weixin_44018540/article/details/108532431
[Link 3]: https://blog.csdn.net/weixin_44018540/article/details/108554156
[Link 4]: https://blog.csdn.net/weixin_44018540/article/details/108596376
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3a1eb22b75864bfb9ac9b43517f97f87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/dcdb3dca1349471797ba351253bf4811.png