算法思想有很多,业界公认的常用算法思想有8种,分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分,是一个“仁者见仁、智者见智”的问题。
1.1 枚举算法思想
枚举算法思想的最大特点是,在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时,如果逐个考察了某类事件的所有可能情况,因而得出一般结论,那么这个结论是可靠的,这种归纳方法叫作枚举法。
1.1.1 枚举算法基础
枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。在C语言中,枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。
①确定枚举对象、枚举范围和判定条件。
②逐一列举可能的解,验证每个解是否是问题的解。枚举算法一般按照如下3个步骤进行。
①题解的可能范围,不能遗漏任何一个真正解,也要避免有重复。
②判断是否是真正解的方法。
③使可能解的范围降至最小,以便提高解决问题的效率。
1.2 递推算法思想
与枚举算法思想相比,递推算法能够通过已知的某个条件,利用特定的关系得出中间推论,然后逐步递推,直到得到结果为止。由此可见,递推算法要比枚举算法聪明,它不会尝试每种可能的方案。
1.2.1 递推算法基础
递推算法可以不断利用已有的信息推导出新的东西,在日常应用中有如下两种递推算法。
①顺推法:从已知条件出发,逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
②逆推法:从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。