算法思想

算法思想有很多，业界公认的常用算法思想有8种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。至于还有其他的，你们非要抬扛，show me your code. 本文主要介绍以上8种

1. 枚举

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。

在C语言中，枚举算法一般使用while循环实现。

1.1使用枚举算法解题的基本思路如下。

• ① 确定枚举对象、枚举范围和判定条件。
• ② 逐一列举可能的解，验证每个解是否是问题的解。
  枚举算法一般按照如下3个步骤进行。
• ①题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。
• ② 判断是否是真正解的方法。
• ③ 使可能解的范围降至最小，以便提高解决问题的效率。

1.2 示例demo：

问题描述：我国古代数学家在《算经》中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意为：公鸡每只5元，母鸡每只3元，小鸡3只1元。用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少？

    int x,y,z;
               for(x=0;x<=20;x++)
               {
                   for(y=0;y<=33;y++)
                   {
                       z=100-x-y;
                       if (z%3==0 &&x*5+y*3+z/3==100)
                           printf("鸡翁%d¸鸡母%d,鸡雏%d\n",x,y,z);
                   }
               }

结果如下：

鸡翁0¸鸡母25,鸡雏75
鸡翁4¸鸡母18,鸡雏78
鸡翁8¸鸡母11,鸡雏81
鸡翁12¸鸡母4,鸡雏84

2. 递推

与1相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。

2.1 递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推 算法。

• ① 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
• ② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

2.2 示例demo：

问题描述：斐波那契数列因数学家列昂纳多•斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

  int i;
           long fib[NUM] = {1,1};
           
           for(i=2;i<NUM;i++)
           {
               fib[i] = fib[i-1]+fib[i-2];
           }
           for(i=0;i<NUM;i++)
           {
               printf("%d月+++ 兔子数:%ld\n", i, fib[i]);
           }

结果：

0月+++ 兔子数:1
1月+++ 兔子数:1
2月+++ 兔子数:2
3月+++ 兔子数:3
4月+++ 兔子数:5
5月+++ 兔子数:8
6月+++ 兔子数:13
7月+++ 兔子数:21
8月+++ 兔子数:34
9月+++ 兔子数:55
10月+++ 兔子数:89
11月+++ 兔子数:144
12月+++ 兔子数:233

3. 递归

递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。

3.1 递归算法有如下3个特点。

• ① 递归过程一般通过函数或子过程来实现。
• ② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
• ③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

3.2 在使用递归算法时，应该注意如下4点。

• ① 递归是在过程或函数中调用自身的过程。
• ② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
• ③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
• ④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

3.3 示例demo：???

问题描述：寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚A1把这64个盘子全部移动到第3根柱子上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一个。

int count = 0;  //统计移动次数
void hanNuoTa(int n,char x,char y,char z){ //x,y,z分别是三个柱子，
//第二个参数和第四个参数代表上面的盘子从这个柱子到那个柱子的移动过程
                                     //n是盘子数
    if(n == 1){
        printf("%c-->%c\n",x,z);
        count++;
        return;
    }
    hanNuoTa(n-1,x,z,y);  //第一步，把x最上面的n-1个盘子从x移动到y
    printf("%c-->%c\n",x,z);  //第二步，再把x上剩下的最上面的盘子放在z上
    count++;
    hanNuoTa(n-1,y,x,z);  //第三步，把y上面的n-1个盘子从y移动到z
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        int h;
        printf("请您输入要移动的盘子个数: ");
        scanf("%d",&h);
        printf("移动%2d盘子的步骤:\n",h);
        hanNuoTa(h,'a','b','c');
       
    }
    return 0;
}

结果

请您输入要移动的盘子个数: 3
移动 3盘子的步骤:
a-->c
a-->b
c-->b
a-->c
b-->a
b-->c
a-->c
Program ended with exit code: 0

4. 分治

分治算法是采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

4.1 使用分治算法解题的一般步骤如下。

• ① 分解，将要解决的问题划分成若干个规模较小的同类问题。
• ② 求解，当子问题划分得足够小时，用较简单的方法解决。
• ③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

5. 贪心

哈哈，你的温柔我永远不懂

贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，

5.1 贪心算法存在以下3个问题。

• ① 不能保证最后的解是最优的。

• ② 不能用来求最大或最小解问题。

• ③ 只能求满足某些约束条件的可行解的范围。

5.2 贪心算法的基本思路如下。

• ①建立数学模型来描述问题。

• ② 把求解的问题分成若干个子问题。

• ③ 对每一子问题求解，得到子问题的局部最优解。

• ④ 把子问题的局部最优解合并成原来解问题的一个解。

5.3 实现该算法的基本过程如下。

• （1）从问题的某一初始解出发。
• （2）while能向给定总目标前进一步。
• （3）求出可行解的一个解元素。
• （4）由所有解元素组合成问题的一个可行解。

6.试探法(回溯法)

试探法也叫回溯法，试探法的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

6.1试探算法解题的基本步骤如下所示

• ① 针对所给问题，定义问题的解空间。
• ② 确定易于搜索的解空间结构。
• ③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

试探法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

7. 动态迭代-辗转法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。

利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

7.1 在使用迭代算法解决问题时，需要做好如下3个方面的工作。

• （1）确定迭代变量 在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。
• （2）建立迭代关系式 迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。
• （3）对迭代过程进行控制 在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。

7.2 通常可分为如下两种情况来控制迭代过程：

• ① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；
  +② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。

8. 模拟

模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能，可以用语言来模拟那个功能，模拟成功也就相应地表示编程成功。

随机模拟，那就看个人造化和题目规则了