算法设计——课程回顾

2021-09-01

毕竟已经过段时间了，能回顾多少就看运气叭。

枚举

1.枚举(Enumerate)也称为列举法、穷举法、又称为暴力法。
2.枚举是一种简单而直接解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形。
3.应用枚举时应注意对问题所涉及的有限情形进行一一列举，既不能重复，又不能遗漏。

上课示例：韩信点兵
·按从1至5报数，记下最末尾士兵报的数为1；
·按从1至6报数，记下最末尾士兵报的数为5；
·按从1至7报数，记下最末尾士兵报的数为4；
·按从1至11报数，记下最末尾士兵报的数为10；
意思就是按不同数字报数，到最后一个士兵报的数不一样，让你猜韩信有多少兵。
输入格式：本题无输入。
输出格式：输出韩信至少拥有的士兵数。

for (int x = 10;;x++){
            if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10){
                System.out.println(x);
                break;
            }
        }

运行结果：2111

课后示例一：
医用外科口罩5元一个，护目镜要30一个，75%的消毒酒精20一瓶，用1000元买100样，问口罩，护目镜，消毒酒精各买多少个刚好凑足1000元。
输入格式：本题无输入。（结尾无空行）
输出格式：在这里给出相应的输出。例如
68 2 30
70 5 25
72 8 20
74 11 15
76 14 10
78 17 5
(结尾无空行)

public class Main {
    public static void main(String[] args) {
        for (int i = 1;i <= 100;i++){
            for (int j = 1;j <= 100;j++){
                for (int q = 1;q<=100;q++){
                    if (i*5+j*30+q*20==1000&&i+j+q==100){
                        System.out.println(i+" "+j+" "+q); } } } } }}

运行结果一致。

排序

冒泡排序，虽然感觉哪里不对劲。

public class Main {
    public static void main(String[] args) {
        int [] a ={4,3,2,5};
        for (int i=0;i<a.length-1;i++){//外循环也就是第i次冒泡排序,最后一次不用，因为已经轮到它就是最小。
            for(int j=0;j<a.length-1-i;j++){//内循环，一个一个往上，-i是可以节省资源空间，因为排序已经完成。
                if (a[j]<a[j+1]){     //修改符号可以使他从小到大排序
                    int value=a[j];
                    a[j]=a[j+1];
                    a[j+1]=value;
                }
            }
        }
       for (int x:a){
           System.out.println(x);
       }}}

运行结果：5432
所以我们为什么不直接Arrays.sort(a)呢？多好用。
sort英文翻译：排序

课后示例一：
将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。

本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。
输入格式：输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。
输出格式：在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。
输入样例：
6 2
2 3 5 1 6 4
输出样例：
2 1 3 4 5 6

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();   //没啥好说的，就是遍历k遍，把中途的结果展现出来而已
        int [] arr=new int[N];
        for (int i=0;i<N;i++){
            arr[i]=sc.nextInt();
        }
        for (int i=0;i<K;i++){
            for (int j=0;j<arr.length-1-i;j++){
                if (arr[j]>arr[j+1]){
                    int a=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=a;
                }
            }
        }
        String txt="";
        for (int i:arr){
            txt+=i+" ";
        }
        System.out.println(txt);}}

课后示例二：根据一张由N个正整数组成的数表，两两相加得到新数（共有N∗(N−1)/2个），然后将新数按照非递减排序。
举个例子呢就是：如果数表里包含有4个数1，4，3，9，那么正确答案就是4，5，7，10，12，13。
输入格式：数据有两行，第1行是一个整数N（1<N≤100），表示数表中的整数个数；
第2行是数表中的N个整数（0≤整数≤5000），相邻整数间以一个空格分隔。
输入的N个整数确保不重复。
输出格式：输出一组按照升序排列的整数的和，相邻整数之间以一个空格分隔。
输入样式：在这里给出一组输入。例如：
4
1 4 3 9
输出样式：4 5 7 10 12 13

public class JavaPractice{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int A[]=new int[N];
        int B[]=new int[N*(N-1)/2];
        int a=0;              //这个是标记，让B数组一个一个添加值,不可换i
        for (int i=0;i<N;i++){
            A[i]=sc.nextInt();
        }
        for (int i=0;i<N;i++){
            for (int j=i+1;j<N;j++){
                B[a]=A[i]+A[j];
                a++;
            }
        }
        Arrays.sort(B);       //直接排序从小到大
        String txt="";
        for (int q:B){        //这样搞的话最后会有个空格，要去除自己看着办
            txt+=q+" ";
        }
        System.out.println(txt);}}

递推

递推算法基本思想：递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果。
递推算法的执行过程如下：
1.根据已知结果和关系，求解中间结果。
2.判断是否达到要求，如果没有达到。则继续根据已知结果和关系求解中间结果；如果满足要求，则表示寻找到一个正确的答案。
课后示例一：Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。随机输入一个整数n，求得 Fn除以10086的余数是多少。
输入格式：输入一个整数n。
输出格式：输出一个整数Fn除以10086的余数。
输入样式：3
输出样式：2

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int A=sc.nextInt();
        int [] a=new int[A];
         if (A>=2){
        a[0]=1;a[1]=1;
            for (int i=2;i<A;i++){
                a[i]=(a[i-1]+a[i-2])%10086;

            }
            System.out.println(a[A-1]);
        }
        else
            System.out.println(A);}}   //这是之前写的

方法二：

public class JavaPractice{
    public static int run(int A){
        if (A<=2){
            return 1; }
        else {
            int num=run(A-1)+run(A-2);
            return num; }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int A=sc.nextInt();
        int s=run(A)%10086;
        System.out.println(s);
    }      //应该算是用递归调用写的了吧

递归

什么是递归？从前有座山山里有座庙，庙里有个和尚在讲故事……
递归调用自己会占用栈的空间，栈满了就会出现栈溢出错误，所以这就是调用函数的代价。
简单的示例：

public class JavaPractice{
    public static int run(int x){
        if (x==1) return 1;
        else return x + run(x-1);
    }//自己调用以前的自己然后加起来
    public static void main(String[] args) {
        System.out.println(run(100));
    }
}

运行结果：5050
课后示例一：编写函数，函数的形式参数为两个正整数a和b,函数返回a与b的最大公约数，要求用递归方式实现。主函数中输入两个整数m和n，输出m和n的最大公约数。
输入样式：36 24
输出样式：12

public class Main {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int m=sc.nextInt();
            int n=sc.nextInt();
            f(m,n);       //接收参数并调用
        }
        public static void f(int a, int b){
            int c=a%b;  //不返回就直接输出
            if (c==0)
                System.out.println(b);
            else {
                f(a=b,b=c);   //已知搞下去总会有的
            }
        }

贪心

贪心算法又称贪婪算法，总是做出在当前看来是最好的选择，不从整体最优解上加以考虑，它所做出的是在某种意义上的局部最优解。
关键的是贪心策略的选择，选择的贪心策略必须具备无后效型。
即某个状态以前的状态不会影响以后的状态至于当前状态有关，在当前情况下贪心算法将问题化为若干个类似的小问题，进行局部的最优解，以此达到整体最优解。
示例一
小明是个好学的程序猿，他想在一天内尽可能多的选择课程进行学习。在下列课程中，他能选择的最多课程是几门？
输入格式：第一行为一个整数n，表示课程总数。接下来每行为x，y，z表示课程名，开始时间，结束时间。
输出格式：输出一个整数，表示小明最多可选的课程数。
输入样式：5
Art 9 10
English 9.3 10.3
Math 10 11
Computer 10.3 11.3
Music 11 12
结尾无空行
输出样式：3 结尾无空行
这边再提一次，类是类，接口是接口，接口是有抽象方法的，类要去实现这些方法，但是抽象类就和接口有一定类似了。