算法趣题第二天

Bertha 。 2022-12-05 16:27 156阅读 0赞

# 本篇介绍 #

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

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

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

# 系列链接 #

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

# Q4 切分木棒 #

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

## 难点 ##

本题难点在于如何**理解题意**并且**用编程语言进行表达**

## 源码 ##

public class Test04 {
        
    	
    	//定义函数（m为长度，n为人数）
    	public static void cut(int m,int n) {
        
    		//计数
    		int count = 0;
    		//当前长度初始值为1
    		int current = 1;
    		//当前长度小于总长度
    		while(current < m) {
        
    		/* if(current<n) { current+=current; }else { current+=n; } */
    			//这里是个复合语句
    			current+=current<n?current:n;
    			//计数+1
    			count++;
    		}
    		System.out.println(count);
    	}
    	
    	public static void main(String[] args) {
        
    		//问题一
    		cut(20,3);
    		//问题二
    		cut(100,5);
    	}

## 要点 ##

1.  题意理解
    
    这道题其实可以换一个意思去理解，题意是进行木块的切分，我们可以转换为m 个人黏合 1 厘米的木棒以组成 n 厘米的木棒，这样在编写程序的时候更好理解一些，不需要牵扯到递归的写法。
2.  复合语句

current += current<n ? current:n;

上述代码运用了符合语句，初学者可能会在理解上有问题，这里解读一下。

这句代码的格式可以表达为

**(运算表达式)(条件)？(真执行):(假执行)**

也可以用以下代码进行替换

if(current<n) {
        
    		 current+=current; 
    	}else {
         
    		current+=n; 
    	}

这样是不是好理解多了，当前长度小于设定人数时，返回当前长度相加，不然则返回当前长度与人数相加。这样的四行代码其实可以用一行复合语句进行表示，是不是很简洁呢？

当然啦，这样做虽然保证了简洁性却也一定程度降低了可读性。要是一个庞大的程序中，条件语句都如此书写，怕不是维护的人要痛苦至死。

# Q5 还在用现金支付吗 #

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

## 难点 ##

本题无难点

## 源码 ##

public class Test05 {
        
    
    	public static void main(String[] args) {
        
    		//计数
    		int count=0;
    		//总金额
    		int money = 1000;
    		//通过循环限制每一类硬币个数
    		for(int i=0;i<=15;i++) {
        
    			for(int j=0;j<=15;j++) {
        
    				for(int k=0;k<=10;k++) {
        
    					for(int l=0;l<=2;l++) {
        
    						//满足条件便计数+1
    						if(i+j+k+l<=15 && i*10+j*50+k*100+l*500==money) {
        
    							count++;
    						}
    					}
    				}
    			}
    		}
    		System.out.print(count);
    	}

## 要点 ##

1.  其实这个问题应该是可以进行函数封装，通过修改函数的参数来实现结果的变化，而不是像现在这样，针对一个问题而设计单纯的计算。这也是算法的一大奇妙之处，通过一次设计，解决一类问题，等博主研究出来，便更新这道题的算法。

# 结语 #

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

[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/99ef3a07a52e4b199926854b9db7ff9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d3c9528ddd37498d915b75d7b8b021a5.png