常用的算法思想——1

发表于 | 分类于 | | 本文总阅读量 次
字数统计: 3k | 阅读时长 ≈ 13

枚举算法

枚举算法思想特点是在面对任何问题时它都会去尝试每一种解决方法，在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论可能是可靠的，这种归纳方法叫归纳法

枚举算法基础

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

枚举算法基本思路

1.确定枚举对象、枚举范围和判定条件

2.逐一列举可能的解，验证每个解是否是问题的解

枚举算法基本步骤

1.题解的可能范围，不能遗漏任何一个真正解，也要避免有重复

2.判断是否是真正解的方法

3.使可能解的范围将至最小，以便提高解决问题的效率

案例

百元买百鸡

公鸡每只5元，母鸡每只3元，小鸡3只1元。用100元买一百只鸡

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    int xj;
    for (int gj=0;gj<=20;gj++){
        for (int mj=0;mj<=33;mj++){
            xj=100-gj-mj;
            if (xj%3==0&&5*gj+3*mj+xj/3==100){
                System.out.println("公鸡："+gj+",母鸡："+mj+",小鸡："+xj);
            }
        }
    }
}

运行结果
运行结果

填写运算符

在下面算式中，添加“＋”“－”“×”“÷”4个运算符使等式成立

5 5 5 5 5 = 5

‘×’，’÷’运算符优先级高于’+’,’-‘且’÷’后面的数不可以是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static void main(String[] args) {
        int[] i=new int[4];        //表示4个运算符
        int sign;   //累加运算时的符号
        int result=5; //运算的结果值
        int count=0;    //结果个数
        int [] num={5,5,5,5,5};
        char [] oper={' ','+','-','*','/'};
        double left,right;
        for (i[0]=1;i[0]<=4;i[0]++){//循环4种运算符，1+2-3*4/
            if (i[0]<4||(num[1]!=0)){//若运算符为/，下一个数值不能为0
                for (i[1]=1;i[1]<=4;i[1]++){
                    if (i[1]<4||num[2]!=0){
                        for (i[2]=1;i[2]<=4;i[2]++){
                            if (i[2]<4||num[3]!=0){
                                for (i[3]=1;i[3]<=4;i[3]++){
                                    if (i[3]<4||num[4]!=0){
                                        left=0;
                                        right=num[0];
                                        sign=1;
                                        for (int j=0;j<4;j++){
                                            switch (oper[i[j]]){
                                                case '+':left=left+sign*right;
                                                sign=1;
                                                right=num[j+1];
                                                break;
                                                case '-':left=left+sign*right;
                                                sign=-1;
                                                right=num[j+1];
                                                break;
                                                case '*':right=right*num[j+1];
                                                break;
                                                case '/':right=right/num[j+1];
                                                break;
                                            }
                                        }
                                        if (left+sign*right==result){
                                            count++;
                                            System.out.print(count+":");
                                            for (int j=0;j<4;j++){
                                                System.out.print(num[j]+""+oper[i[j]]);
                                            }
                                            System.out.print(num[4]+"="+result+" ");
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

运行结果
运行结果

递推算法

递推算法基础

递推算法可以不断利用已有信息推导出新的东西

顺推法：从已知条件出发，逐步推算出要解决问题的方法
逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程

案例

顺推法——裴波那契数列

兔子在出生两个月以后就有繁殖能力，一对兔子每月能生出一对兔子，如果所有兔子都不死，一年后有多少兔子

算法分析
  • 第一个月兔子没有繁殖能力，所以还是一对
  • 二个月后，一对小兔子生出一对新兔子，所以是两对
  • 第三个月后老兔子又生下一对，小兔子还没有繁殖能力，所有有三对
月数： 1 2 3 4 5 6 7 8 …
对数： 1 1 2 3 5 8 13 21 …

得出特征：前面相邻两项之和等于后一项

由此可知n个月的兔子总数为：Fn=Fn-2+Fn-1

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
        int [] fib=new int[13];
        fib[0]=fib[1]=1;
        for (int i=2;i<fib.length;i++){
            fib[i]=fib[i-1]+fib[i-2];
        }
        for (int i=0;i<fib.length;i++){
            System.out.print(i+1+"月："+fib[i]+"个兔子   ");
            if (i%3==0){
                System.out.println();
            }
        }
    }

运行结果
运行结果

逆推法——银行存款问题

母亲为儿子4年大学生活准备了一笔存款，方式是整存零取，规定儿子每月月底取下一个月生活费，现假设银行年利率为1.71%，计算母亲最少要存入多少钱

算法分析

因为按月取钱，所以需要将4年分为48个月

如果48月后，儿子大学毕业时连本带利要取1000，则要先求出第47个月时银行存款的钱数

47月末=1000/(1+0.0171/12)

46月末=(47月末+1000)/(1+0.171/12)

45月末=(46月末+1000)/(1+0.171/12)

44月末=(45月末+1000)/(1+0.171/12)

43月末=(44月末+1000)/(1+0.171/12)

……

2月末=(3月末+1000)/(1+0.171/12)

1月末=(2月末+1000)/(1+0.171/12)

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    double [] corpus=new double[48];
    int i;
    corpus[47]=1000;
    double rate=0.0171;
    for (i=46;i>=0;i--){
        corpus[i]=(corpus[i+1]+1000)/(1+rate/12);
    }
    System.out.println("需存储："+corpus[0]+"元");
}

运行结果
运行结果

递归算法

递归算法基础

在计算机编程中，递归算法对解决大多数问题是十分有效的，它能使算法的描述变得简洁而且易于理解

递归算法的特点

1.递归过程一般通过函数或子过程来实现

2.递归算法在函数或子过程的内部，直接或间接的调用自身

3.递归算法实际上是把问题转化为小规模的同类问题，然后再递归调用函数或过程来表示问题的解

使用递归的注意事项

1.递归是在过程或函数中调用自身的过程

2.在使用递归时，必须有一个明确的结束条件（递归出口）

3.递归算法通常显得很简洁，但运行效率很低，所以一般不提倡用递归算法设计程序

4.在递归调用过程中，系统用栈来存储每一层的返回点和局部变量。如果递归次数过多，则会造成栈溢出，所以一般不提倡使用递归算法设计程序

案例

汉诺塔

详解（https://www.cnblogs.com/vsky/p/5014657.html/ ）（https://blog.csdn.net/qq_37873310/article/details/80461767 ）

1
2
3
4
5
6
7
8
9
public static void move(int n, String x, String y, String z){
        if (n==1){
            System.out.println(""+x+z);
        }else {
            move(n-1,x,z,y);
            //System.out.println(""+x+z);
            move(n-1, y,x ,z);
        }
    }

阶乘

自然数由1~n的n个数连乘积叫做n的阶乘，记作n！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class JieCheng {
    public static void main(String[] args) {
        int i=6;
        long n=fact(i);
        System.out.println(i+"的阶乘是："+n);
    }
    public static int fact(int n){
        if (n<=1){
            return 1;
        }else {
            return n*fact(n-1);
        }
    }
}

运行结果
运行结果
调用过程

分治算法

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

分治算法基础

分治算法基本步骤

1.分解，将要解决的问题划分为若干个规模较小的同类问题

2.求解，当子问题划分的足够小时，用较简单的方法求解

3.合并，按原问题要求将子问题的解逐层合并构成原问题的解

案例

大数相乘

问题详解（https://blog.csdn.net/u011446177/article/details/52894191/ ）

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public static void main(String[] args) {
        String str1 = "2345678900987766655554444455";
        String str2 = "34658743659843759437594387593875";
        int len1 = str1.length();
        int len2 = str2.length();
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        // 高低位对调
        covertdata(s1, len1);
        covertdata(s2, len2);
        System.out.println("乘数："+str1);
        System.out.println("乘数："+str2);
        multiply(s1, len1, s2, len2); 
    }
    public static void covertdata(char data[], int len) {
        //高低位对调
        for (int i = 0; i < len / 2; i++) {
            data[i] += data[len - 1 - i];
            data[len - 1 - i] = (char) (data[i] - data[len - 1 - i]);
            data[i] = (char) (data[i] - data[len - 1 - i]);
        }
    }
    public static void multiply(char a[], int alen, char b[], int blen) {
        // 两数乘积位数不会超过乘数位数和+ 3位
        int csize = alen + blen + 3;
        // 开辟乘积数组
        int[] c = new int[csize];
        // 乘积数组填充0
        for (int ii = 0; ii < csize; ii++) {
            c[ii] = 0;
        }
        // 对齐逐位相乘
        for (int j = 0; j < blen; j++) {
            for (int i = 0; i < alen; i++) {
                c[i + j] +=  Integer.parseInt(String.valueOf(a[i]))* Integer.parseInt(String.valueOf(b[j]));
            }
        }
        int m = 0;
        // 进位处理
        for (m = 0; m < csize; m++) {
            int carry = c[m] / 10;
            c[m] = c[m] % 10;
            if (carry > 0) {
                c[m + 1] += carry;
            }
        }
        // 找到最高位
        for (m = csize - 1; m >= 0;) {
            if (c[m] > 0) {
                break;
            }
            m--;
        }
        // 由最高位开始打印乘积
        System.out.print("乘积：");
        for (int n = 0; n <= m; n++) {
            System.out.print(c[m - n]);
        }
    }

欧洲冠军杯比赛

欧洲冠军杯初赛阶段采用循环制，设共有n队参加，初赛共进行n-1天，每队都要和其他各队进行一场比赛，然后按照最后积分选拔进入决赛的球队。要求每队每天只能进行一场比赛，并且不能轮空。

算法分析

根据分治算法思路，将所有参赛队伍分为两半，则n队比赛日程表可以通过n/2个队的比赛日程来决定，然后继续划分，直到只剩下最后2队为止。

代码实现

转自(https://www.jianshu.com/p/2089e19e7f99/ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class Solution {
    /**
     * 循环赛日程表
     * @param ranksNumber
     */
    static public void raceSchedule(int ranksNumber) {
        if (ranksNumber < 2) {
            System.out.println("无需安排");
            return;
        }
        int[][] resultArray = new int[ranksNumber][ranksNumber];
        for (int counter = 0;counter < ranksNumber;counter++) {
            resultArray[counter][0] = counter + 1;
            for (int counter1 = 1;counter1 < ranksNumber;counter1++) {
                resultArray[counter][counter1] = resultArray[counter][counter1 - 1] + 1;
                if (resultArray[counter][counter1] > ranksNumber)resultArray[counter][counter1] = 1;
            }
        }
        for (int counter = 0;counter < ranksNumber;counter++) {
            if (counter == 0)System.out.print("No.\t");
            else System.out.print("D" + counter + "\t");
        }
        System.out.println();
        for (int counter = 0;counter < ranksNumber;counter++) {
            for (int counter1 = 0;counter1 < ranksNumber;counter1++) {
                System.out.print(resultArray[counter][counter1] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 本算法采用分治策略来解决。
     * @param ranksNumber
     */
    static public void raceSchedule0(int ranksNumber) {
        //判断它是不是2的次幂，并且它还必须至少是2.
        if (!isPowerOfTwo(ranksNumber) || ranksNumber < 2) {
            System.out.println("输入错误");
            return;
        }
        int[][] scheduleArray = new int[ranksNumber][ranksNumber];
        Solution.dAndC(scheduleArray,1,ranksNumber,ranksNumber);
        for (int counter = 0;counter < ranksNumber;counter++) {
            if (counter == 0)System.out.print("No.\t");
            else System.out.print("D" + counter + "\t");
        }
        System.out.println();
        for (int counter = 0;counter < ranksNumber;counter++) {
            for (int counter1 = 0;counter1 < ranksNumber;counter1++) {
                System.out.print(scheduleArray[counter][counter1] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 分治策略的迭代部分
     * @param scheduleArray
     * @param number
     * @param length
     * @param ranksNumber
     */
    static private void dAndC(int[][] scheduleArray,int number,int length,int ranksNumber) {
        //如果就2个队伍就很简单了，就是2个斜方向的问题了。
        if (length == 2) {
            scheduleArray[number - 1][0] = number;
            scheduleArray[number][1] = number;
            scheduleArray[number - 1][1] = number + 1;
            scheduleArray[number][0] = number + 1;
        } else {
            int halfLength = length / 2;
            //迭代处理左上角方阵。
            Solution.dAndC(scheduleArray,number,halfLength,ranksNumber);
            Solution.printMatrix(scheduleArray,ranksNumber);
            //迭代处理左下角方阵。
            Solution.dAndC(scheduleArray,number + halfLength,halfLength,ranksNumber);
            Solution.printMatrix(scheduleArray,ranksNumber);
            //接下来把左下的方阵复制到右上角的方阵去
            for (int counter = number - 1;counter < number - 1 + halfLength;counter++)
                for (int counter0 = halfLength;counter0 < length;counter0++)
                    scheduleArray[counter][counter0] = scheduleArray[counter + halfLength][counter0 - halfLength];
            Solution.printMatrix(scheduleArray,ranksNumber);
            //接下来把左上的方阵复制到右下角的方阵去
            for (int counter = number - 1 + halfLength;counter < number - 1 + length;counter++)
                for (int counter0 = halfLength;counter0 < length;counter0++)
                    scheduleArray[counter][counter0] = scheduleArray[counter - halfLength][counter0 - halfLength];
            Solution.printMatrix(scheduleArray,ranksNumber);
        }
    }

    /**
     * 打印矩阵
     * @param scheduleArray
     * @param rank
     */
    static private void printMatrix(int[][] scheduleArray,int rank) {
        for (int counter = 0;counter < rank;counter++) {
            for (int counter1 = 0;counter1 < rank;counter1++) {
                if (scheduleArray[counter][counter1] == 0)System.out.print("  ");
                else System.out.print(scheduleArray[counter][counter1] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 判断一个数是不是2的幂次
     * @param number
     * @return
     */
    static private boolean isPowerOfTwo(int number) {
        int bitFlag = 1;
        int bitSum = Integer.SIZE - 1;//不算符号位
        int bitIterator = 0;
        int oneCounter = 0;
        while (bitIterator < bitSum) {
            if ((bitFlag & number) != 0) {
                oneCounter++;
                if (oneCounter > 1)
                    return false;
            }
            bitFlag = bitFlag << 1;
            bitIterator++;
        }
        return true;
    }
}
-------------本文结束❤️感谢您的阅读-------------
ボ wechat
扫描二维码，可获得菜鸡一枚
打赏测试
0%