写在前面的话——

这次主要是就是开始讲算法了，主要的来说，主要是分治法、贪婪法还有动态规划，这些我觉得是一种处理问题的思想，还有什么蛮力法，倒推法什么的，也算是思想，但是更多的，这个也算是一种工具，会比较常见的用在之前的三种方法中，特别是倒推，其实我也觉得倒推并没有多神奇，毕竟我们做数学题的时候，就是很多时候按照正常的顺序思考不出来，反着推就能比较顺利，而且我觉得这些个算法，只能算是训练，而实际应用的时候，应该还是适可而止，不要过分强求，实际问题一般都比这些训练题复杂得多，所以我始终觉得这个只是锻炼一个思想而已！

第二篇——

我觉得下面三个题比较简单，就是第一个题有点难度，不过因为是书上例题，所以并没有花很多功夫去思考，反过来想的话，这个题也没法想的太细，因为需要很多数学思想的支撑，特别是一开始要建立一个数学模型，所以掌握方法领悟技巧就好，至于为什么要这么算，凭什么这么算就是最节约的，不讨论比较好。

1.穿越沙漠问题

一辆吉普车穿越1000千米的沙漠。吉普车的总装油量为500加仑，耗油量为1加仑/千米。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。若吉普车用最少的耗油量穿越沙漠，应在那些地方建立油库，以及各处存储的油量。

算法设计：

这个题由于要求用最少的耗油量，也就是最后穿越沙漠之后刚好油量为0，同时，很明显，直接开是无法穿越的，在中间架设油库，只能使用这辆车，一次最所携带500加仑并且行进返回都需要耗油，如果正向分析问题会非常复杂无从下手，但是倒推会发现还是有迹可寻。

从终点倒推，刚好油量为0，则在离终点500千米的地方A建立一个油库并且存油500加仑，设A点之后的油库在B点，从B点到A点运油，满足条件的最佳方案是B点到A点共走三次，第一、二次来回耗油量为装载量的2/3，储油量为装载量的1/3，第三次单向行驶耗油量为装载量的1/3，储油量为装载量的2/3。统计一下，B点的储油量为1000加仑，此段长度为500/3千米。

同理分析B点之后的油库C点，应该需要往返5次，位置就在距离B点500/5千米的位置，存油量为1500，以此类推

代码如下：

1. #include <stdio.h>
3. int main()
4. {
5. int dis[100],k,oil[100];
6. dis[1]= 500;
7. k= 1;
8. oil[1]= 500;
9. do {
10. k++;
11. dis[k]= dis[k-1] + 500/(2 * k – 1);
12. oil[k]= 500 * k;
13. }while(dis[k] < 1000);
15. oil[k]= 500 * (k – 1) + (1000 – dis[k]) * (2 * k – 1);
16. dis[k]= 1000;
18. int i = 0;
19. for(;i<k;i++) {
20. printf(“第%d个临时油库在距离起点%d的位置，储油量为%d\n”,i+1,1000-dis[k-i],oil[k-i]);
21. }
23. return 0;
24. }

算法分析：通过倒推法可以解决一些正向推导很难处理的问题，非常有效。

2.54张扑克牌，两个人轮流拿牌，每个人每次最少取1张，最多取4张，谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。

算法设计：

根据题意，必须先拿且必胜，则可以理解为，在54张减去第一次拿的牌数后，每轮对方先拿，自己后拿，直到最后一轮，刚好剩下1张牌，且对方的拿牌数为一个1-4的随机数，那么此时应该考虑，对方每次的拿牌数是不能确定的，但是每轮的拿牌数是可以确定的，就是可以在对方拿完之后，自己拿一定数量的牌凑成一个可以一定达成的数字，这个数字很明显应该是5，即每轮拿5张牌，最后还剩一张，且之前减去了已经拿走的牌，则很明显，先拿走3张之后，还剩51张，每轮拿走5张，十轮之后，还剩一张，此时必定获胜。

代码如下：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
5. int main()
6. {
7. int i = 3;//计算机初始拿的牌数
8. int n = 54;//当先的牌数量
9. int i_times = 1;//总计拿了多少次
10. int p;//另一方的拿牌数，在1-4之间随机生成一个数
11. srand(time(0));
12. while(n > 0)
13. {
14. p= rand()%4 + 1;
15. printf(“the%d time computer select %d paper and you %d paper\n”,i_times,i,p);
16. n-= i+p;
17. printf(“nowthe paper has left %d\n”,n);
18. i_times++;
19. i= 5 – p;//需要在对方拿牌之后，再取的牌数和之前的牌数凑成固定的5张
20. if(n – i == 1) {//如果还剩一张，此时不可以继续随机了，只能拿这张牌
21. printf(“the%d time computer select %d paper and you have the last one\n”,i_times,i);
22. break;
23. }
24. }
25. return 0;
26. }

算法分析：这个算法的关键在于如何保证最后一定剩一张牌给另一方，而且要保证每一轮拿牌保证一样的数量才可以进行控制，但是每一轮先拿牌的话，就无法控制，只能再对方先拿牌之后才能根据他的数量再决定该拿多少张，此时根据规则，必须先拿又必须赢，此时需要考虑先拿多少张，然后开始每一轮拿牌，最后剩一张牌，顺利写出代码

3.有一堆棋子，2枚2枚的数，最后余1枚；3枚3枚的数，最后余2枚；5枚5枚的数，最后余4枚；6枚6枚的数，最后余5枚；7枚7枚的数，最后正好数完。变成求出这堆棋子最少有多少枚棋子。

算法设计：

从题目来看，很明显是求一个数，这个数对2求余得1，对3求余得2，对5求余得4，对6求余得5，对7整除，使用蛮力法，从最小的数7开始累加，直到满足条件结束

代码如下：

1. int main()
2. {
4. int i = 7;
5. while(1) {
6. if(5 == i % 6 && 4 == i% 5 && 2 == i % 3 &&1 == i % 2) {
7. printf(“这堆棋子的数量为%d\n”,i);
8. break;
9. }else
10. i+= 7;
11. }
13. return 0;
14. }

算法分析：以上实际采用枚举法，将每一个数都进行运算求得余数进行比对，直到符合所有条件的数出现为止，这里简单设计了下，不用每个数都判断，只需要判断7的倍数即可，可以减少循环次数，整个算法看起来比较清晰简洁。

———————-

穷举算法和递推算法（Java）

穷举算法

概念：

最简单算法，依赖计算机的强大计算能力穷尽每一种可能的情况。穷举算法效率不高，但是适合一些没有明显规律可循的场合。

 

思想：

在使用穷举算法时，需要明确问题答案的范围，这样才可能在指定范围搜索答案。指定范围之后，就可以使用循环和条件判断语句进行逐步验证结果了。

 

案例：鸡兔同笼问题

在一个笼子里关着若干只鸡和若干兔子。一共有35个头，和94只脚。问在一个笼子里鸡和兔子各有多少个。

package cmd.chengxuyuanzhilu.arithmetic;

import java.util.Scanner;

/**
 * @author 微信公众号：程序员之路 
 *                 博客：http://www.cnblogs.com/chengxuyuanzhilu/
 * 穷举算法
 */
public class Exhaustion {
    public static void exhaustion(int head,int foot){
        int chicken,rabbit;
        for(chicken=0;chicken<= head;chicken++){
            rabbit=head-chicken;
            if(chicken*2+rabbit*4 == foot){
                System.out.println(String.format("鸡有 %d只，兔子有%d只", chicken,rabbit));
            }
        }
    }
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        int head,foot;
        
        System.out.println("穷举算法解决鸡兔同笼问题");
        System.out.println("输入头的个数");
        Scanner scanner = new Scanner(System.in);
        head = scanner.nextInt();
        System.out.println("输入腿的个数");
        foot = scanner.nextInt();
        exhaustion(head, foot);
    }
}

 

递推算法

概念：

递推算法在数学计算等方面广泛应用。递推算法适合有着明显规律的场合

 

思想：

递推算法往往需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有着明显的计算公式可以遵循，因此可以采用递推算法。

 

案例：兔子产崽子的问题

如果有两个月大的兔子以后每个月都可以产一对小兔子，而一对小兔子出生两个月后可以在生小兔子，也就是1月份出生，3月份才可以产崽子。那么假定一年内没有发生死亡事件，那么现在有一对小兔子一年后共有多少对兔子。

 

案例分析：

1月 1对兔子

2月 1对兔子

3月 2对兔子 一对成熟兔子

4月 3对兔子

5月 5对兔子 两对成熟兔子

6月 8对兔子 三对成熟兔子

。。。。。。

规律：前两个月都是一对兔子，以后每个月的兔子的对数是前两个月的总和

除1,2月份的计算公式：n月  Fn = (Fn-1)+(Fn-2)

package cmd.chengxuyuanzhilu.arithmetic;

import java.util.Scanner;

/**
 * @author 微信公众号：程序员之路 
 *                 博客：http://www.cnblogs.com/chengxuyuanzhilu/
 * 递推算法
 */
public class Recurrence {
    public static int recurrence(int months){
        if( months == 1 || months == 2){
            return 1;
        }else{
            int m1 = recurrence(months-1);
            int m2 = recurrence(months-2);
            return m1+m2;
        }
    }
    
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        int months,rabbits;
        
        System.out.println("递推算法解决兔子生崽子的问题");
        System.out.println("输入月数");
        Scanner scanner = new Scanner(System.in);
        months = scanner.nextInt();
        rabbits = recurrence(months);
        System.out.println(String.format("%d月共有兔子%d对", months,rabbits));
    }
}