解答算法题的一个小技巧

简介: 解答算法题的一个小技巧

坦白说,这不是一篇怎么教你用具体的哪一门编程语言来编程的文章,而是想和大家分享一下如何用程序来解决一个具体问题。

最近面试的时候,会出一些简单的题,主要是想考察一下面试对象的逻辑能力。题目本身很简单,也算面试中的常见题了,然而还是有很多人做不出来。我认为主要还是解题思路的问题。

这里我们先给大家看看题目:

给你一个整数n. 从 1 到 n 按照下面的规则打印每个数:

  1. 如果这个数被3整除,打印fizz;
  2. 如果这个数被5整除,打印buzz;
  3. 如果这个数能同时被3和5整除,打印fizz buzz;
  4. 如果这个数既不能被3整除,也不能被5整除,打印它本身。

很多程序员,有些已经有很多年工作经验的程序员,一看到题目很快的就开始码代码了,最后改来改去,有些改成功了,大部分的并不能完全处理这三种情况,解题以失败告终。

这道题其实并不难,只有用合理的解题思路,一定可以轻松的写出来答案。

那么正确的解题思路是什么?对于任意复杂的算法题,大体都可以分这几步来完成:

  1. 分析题目,理解题目的要求;
  2. 用自然语言描述解题思路;
  3. 用伪代码来描述算法;
  4. 编程
  5. 重构

大体上一个算法题,都必须经历这几个过程,有些简单的题目,2,3这两步可以省略,但也增加了第4步的难度。有一个小窍门就是,1-3步最好在纸上完成。

从我个人经历来说,我们毕竟从小到大都是面对的纸质的课本、试卷,因此,我觉得在纸上写答案会更自然一些,思路也会更加清晰一些。当然,现在是数字时代了,可能大家的感受不太一样。

以这道题为例,第一步我们先分析一下这道题考的是什么?即所谓的考点。这个题主要考察的是同学对 if 这种选择结构的掌握,也考察了同学对各种条件逻辑推理能力。很多人的容易忽略的就是题目中第三个条件,只处理了题目中第一、二种可能。

分析完题目以后,可以尝试用我们自己的语言来重新组织一下这个题目:给一个整数n,然后打印从1到n的数字,如果是3的倍数的话打印fizz,如果是5的倍数的话打印成buzz,如果正好既是3的倍数也是5的倍数那么输出fizz buzz。

这么一说我们就很清楚了,要处理四种情况,一种这个数是3的倍数,一种是这个数是5的倍数,一种是这个数是3 * 5的倍数,一种是其他不满足以上条件的数。

接下来我们可以尝试把上面的这段话写成伪代码,为了便于理解,我们用中文来写这段伪代码:

n.times do  | i |
  假如 i 是3的倍数, 打印fizz
  假如 i 是5的倍数,打印buzz
  假如i 是3 * 5的倍数, 打印fizz buzz
  其他 打印 i
end

这里需要考虑的一点是,如果按照以上的伪代码,如果 i = 15, 那么打印出来的是fizzbuzzfizz buzz, 而我们要的是fizz buzz, 所以我们要调整一下我们的伪代码:

n.times do  | i |
  假如i 是3 * 5的倍数, 打印fizz buzz;next;
  假如 i 是3的倍数, 打印fizz
  假如 i 是5的倍数,打印buzz
  其他 打印 i
end

这时候,我们的思路已经很清晰了,我们可以开始对着编辑器来编程了:

def print_numbers( n)
    n.times do | i |
        if i % 15 == 0
           print "fizz buzz"
           next
        elsif i % 3 == 0
           print " fizz "
        elsif i % 5 == 0
           print " buzz "
         else
           print " #{i} "
         end
    end
end

这里写代码有两个技巧:1. 第一时间内闭合。比如说你写了 {, 那么要第一时间 写 } (当然现在很多都是编辑器帮我们完成了) 2. 我们能完成的,别让机器来完成。比如第一个条件,可以写成 i % 3 == 0 and i %5 == 0, 但是我们写成 i % 15 ==0 提高了程序运行的效率。

这时候我们可以尝试运行一下代码:

print_numbers(16)
=>  fizz buzz 1  2  fizz  4  buzz  fizz  7  8  fizz  buzz  11  fizz  13  14 fizz buzz=> 16

竟然多了一个fizz buzz, 少了一个16, 这和我们的想要的结果差一点。

究其原则是因为 n.times 是从 0 开始,所以我们可以fix 一下这个 bug:

def print_numbers( n)
    n.times do | i |
        if (i + 1) % 15 == 0
           print "fizz buzz"
           next
        elsif (i + 1) % 3 == 0
           print " fizz "
        elsif (i + 1) % 5 == 0
           print " buzz "
         else
           print " #{ i  + 1} "
         end
    end
end

这时候输出的结果是:

pry(main)> print_numbers 16
1  2  fizz  4  buzz  fizz  7  8  fizz  buzz  11  fizz  13  14 fizz buzz 16 => 16

和我们想要的是一样的。

这里面我们看到有四个 ( i + 1), 对于同样的数字,程序要计算四次,所以我们可以简单重构一下:

def print_numbers( n)
    n.times do | i |
        m = i + 1
        if m % 15 == 0
           print "fizz buzz"
           next
        elsif m % 3 == 0
           print " fizz "
        elsif m % 5 == 0
           print " buzz "
         else
           print " #{ i  + 1} "
         end
    end
end

至此, 我们的编程工作貌似基本完成了。为什么说貌似完成了呢?因为在实际生产中假如我们需要实现一个这样的功能的话,可能我们还需要做好应对修改的准备。

而且,在以上写代码的过程中,我们第一次实现的代码竟然引入了一个bug。

如何能避免出现这样的问题呢?我们可以求助于测试驱动开发,即TDD, 当然这又是另外一个话题了。

相关文章
|
2月前
|
存储 算法 容器
算法刷题小技巧【持续补充~】
算法刷题小技巧【持续补充~】
14 2
|
存储 算法 Java
【算法攻坚】整数翻转的小技巧
【算法攻坚】整数翻转的小技巧
125 0
|
算法
超实用的算法小技巧
本篇文章我们将介绍一些超级实用的算法小技巧,灵活使用这些算法小技巧可以帮助我们更好的解决遇到的问题,让我们的时间复杂度,空间复杂度大大降低,有效的提高我们的编程能力。
131 0
|
22小时前
|
算法 vr&ar
基于自适应波束成形算法的matlab性能仿真,对比SG和RLS两种方法
```markdown - MATLAB2022a中比较SG与RLS自适应波束成形算法。核心程序实现阵列信号处理,强化期望信号,抑制干扰。RLS以其高效计算权重,而SG则以简单和低计算复杂度著称。[12345] [6666666666] [777777] ```
|
1天前
|
算法 索引
基于Prony算法的系统参数辨识matlab仿真
Prony算法在MATLAB2022a中用于信号分析,识别复指数信号成分。核心程序通过模拟信号X1,添加不同SNR的噪声,应用Prony方法处理并计算误差。算法基于离散序列的复指数叠加模型,通过构建矩阵并解线性方程组估计参数,实现LTI系统动态特性的辨识。
|
3天前
|
算法 安全 数据库
基于结点电压法的配电网状态估计算法matlab仿真
**摘要** 该程序实现了基于结点电压法的配电网状态估计算法,旨在提升数据的准确性和可靠性。在MATLAB2022a中运行,显示了状态估计过程中的电压和相位估计值,以及误差随迭代变化的图表。算法通过迭代计算雅可比矩阵,结合基尔霍夫定律解决线性方程组,估算网络节点电压。状态估计过程中应用了高斯-牛顿或莱文贝格-马夸尔特法,处理量测数据并考虑约束条件,以提高估计精度。程序结果以图形形式展示电压幅值和角度估计的比较,以及估计误差的演变,体现了算法在处理配电网状态估计问题的有效性。
|
3天前
|
算法
基于PSO粒子群优化的PID控制器参数整定算法matlab仿真
该文探讨了使用PSO(粒子群优化)算法优化PID控制器参数的方法。通过PSO迭代,不断调整PID控制器的Kp、Ki、Kd增益,以减小控制误差。文中提供了MATLAB2022a版本的核心代码,展示了参数优化过程及结果。系统仿真图像显示了参数随迭代优化的变化。PID控制器结合PSO算法能有效提升控制性能,适用于复杂系统的参数整定,未来研究可关注算法效率提升和应对不确定性。
|
3天前
|
算法
m基于GA遗传优化的高斯白噪声信道SNR估计算法matlab仿真
**MATLAB2022a模拟展示了遗传算法在AWGN信道中估计SNR的效能。该算法利用生物进化原理全局寻优,解决通信系统中复杂环境下的SNR估计问题。核心代码执行多代选择、重组和突变操作,逐步优化SNR估计。结果以图形形式对比了真实SNR与估计值,并显示了均方根误差(RMSE),体现了算法的准确性。**
10 0
|
5天前
|
机器学习/深度学习 存储 算法
基于SFLA算法的神经网络优化matlab仿真
**摘要:** 使用MATLAB2022a,基于SFLA算法优化神经网络,降低训练误差。程序创建12个神经元的前馈网络,训练后计算性能。SFLA算法寻找最优权重和偏置,更新网络并展示训练与测试集的预测效果,以及误差对比。SFLA融合蛙跳与遗传算法,通过迭代和局部全局搜索改善网络性能。通过调整算法参数和与其他优化算法结合,可进一步提升模型预测精度。