算法与程序设计实验

First Post:

Last Update:

Word Count:
5.8k

Read Time:
34 min

Page View: loading...

算法与程序设计实验

要求

1.复现代码，写上自己的注释

2.结果展示

3.将代码进行修改，bug修改，内容提升

第二章

逆序计数

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
import java.io.*;
import java.util.*;

public class Countlnversions {
    public static void main(String[] args)
    {
        System.out.println("请输入待计数逆序的整数序列(以空格分开，各项值都不同)");
        Scanner in=new Scanner(System.in);
        String line=in.nextLine();
        String[] tokens=line.split(" ");
        //获取用户输入的序列
        int[] S1=new int[tokens.length];
        for(int i=0;i<tokens.length;i++)
            S1[i]=Integer.parseInt(tokens[i]);
        int count=sortAndCount(S1);
        //调用实现SAC算法的方法，返回计数结果

        for (int i=0;i<S1.length;i++)
            System.out.print(S1[i]+" ");
        System.out.print("\n逆序计数为："+count);
        //显示排序后的序列和逆序计数值
    }
    private static int sortAndCount(int[]S){
        if(S.length==1)
            return 0;
        int n=S.length/2;
        int[] A=new int[n];
        int[] B=new int[S.length-n];
        int j=0;
        for (int i=0;i<A.length;i++)
            A[i]=S[j++];
        for (int i=0;i<B.length;i++)
            B[i]=S[j++];
        int rA=sortAndCount(A);
        int rB=sortAndCount(B);
        int r=mergeAndCount(A,B,S);
        return (r+rA+rB);
    }
    private static int mergeAndCount(int[]A,int[]B,int[]C)
    {
        int i=0,j=0,k=0,count=0;
        while (i<A.length&&j<B.length)
        {
            if (A[i]>B[j])
            {
                count+=A.length-i;
                C[k++]=B[j++];
            }
            else {
                C[k++]=A[i++];
            }
        }
        if (i==A.length&&j< B.length)
            for (int l=j;l< B.length;l++)
                C[k++]=B[l];
        if (i< A.length&&j== B.length)
            for (int l=i;l< A.length;l++)
                C[k++]=A[l];
        return count;
    }
}

寻找最近点对

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.util.Arrays;
public class FindClosestPair {
    public static void main(String[] args) {
        int N=30;
        int beishu=5000;
        int[] x=new int[N];
        int[] y=new int[N];
        int[] p2=new int[4];
        int[] x2=new int[N];
        int[] y2=new int[N];
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        for(int i=0;i<N;i++){
            x[i]=(int)(Math.random()*beishu);
            y[i]=(int)(Math.random()*beishu);
            x2[i]=x[i];
            y2[i]=y[i];
        }
        int[][] pX=new int[2][N];
        int[][] pY=new int[2][N];
        int[] flagX=new int[N];
        int[] flagY=new int[N];
        for(int i=0;i<N;i++){
            StdDraw.point(x[i], y[i]);
            flagX[i]=1;
            flagY[i]=1;
        }
        Arrays.sort(x);
        Arrays.sort(y);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(x[i]==x2[j]&&flagX[j]==1){
                    pX[0][i]=x2[j];
                    pX[1][i]=y2[j];
                    flagX[j]=0;
                }
                if (y[i]==y2[j]&&flagY[j]==1){
                    pY[0][i]=x2[j];
                    pY[1][i]=y2[j];
                    flagY[j]=0;
                }
            }
        }
        ClosestPairRec(pX,pY,p2);
        System.out.println(p2[0]+" "+p2[1]+" "+p2[2]+" "+p2[3]);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.line(p2[0], p2[1], p2[2], p2[3]);


    }

    public static void ClosestPairRec(int[][] pX, int[][] pY, int[] p2) {
        if(pX[0].length<=3){
            if (pX[0].length==3){
                int d1=(pX[0][0]-pX[0][1])* (pX[0][0]-pX[0][1])+(pX[1][0]-pX[1][1])* (pX[1][0]-pX[1][1]);
                int d2=(pX[0][1]-pX[0][2])* (pX[0][1]-pX[0][2])+(pX[1][1]-pX[1][2])* (pX[1][1]-pX[1][2]);
                int d3=(pX[0][0]-pX[0][2])* (pX[0][0]-pX[0][2])+(pX[1][0]-pX[1][2])* (pX[1][0]-pX[1][2]);
                if(d1>=d2&&d1>=d3){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][1];
                    p2[3]=pX[1][1];
                }
                if(d2>=d1&&d2>=d3){
                    p2[0]=pX[0][1];
                    p2[1]=pX[1][1];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
                if(d3>=d1&&d3>=d2){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
            }
            if(pX[0].length==2){
                p2[0]=pX[0][0];
                p2[1]=pX[1][0];
                p2[2]=pX[0][1];
                p2[3]=pX[1][1];
            }
            return;
        }
        int foreHalf = pX[0].length/2;
        int[][] qX=new int[2][foreHalf];
        int[][] qY=new int[2][foreHalf];
        int[][] rX=new int[2][pX[0].length-foreHalf];
        int[][] rY=new int[2][pX[0].length-foreHalf];
        int[] qp2=new int[4];
        int[] rp2=new int[4];
        int k=0;
        for(int i=0;i<pX[0].length;i++){
            if(i<foreHalf) {
                qX[0][i] = pX[0][i];
                qX[1][i] = pX[1][i];
                qY[0][i] = pY[0][i];
                qY[1][i] = pY[1][i];
            }
            else{
                rX[0][k] = pX[0][i];
                rX[1][k] = pX[1][i];
                rY[0][k] = pY[0][i];
                rY[1][k] = pY[1][i];
                k=k+1;
            }
        }

        ClosestPairRec(qX,qY,qp2);
        ClosestPairRec(rX,rY,rp2);
        int dd1=(qp2[2]-qp2[0])* (qp2[2]-qp2[0])+(qp2[1]-qp2[3])* (qp2[1]-qp2[3]);
        int dd2=(rp2[2]-rp2[0])* (rp2[2]-rp2[0])+(rp2[1]-rp2[3])* (rp2[1]-rp2[3]);
        int d2=Math.min(dd2,dd1);
        double d=Math.sqrt(d2);
        if (dd1<dd2){
            p2[0]=qp2[0];
            p2[1]=qp2[1];
            p2[2]=qp2[2];
            p2[3]=qp2[3];
        }
        else{
            p2[0]=rp2[0];
            p2[1]=rp2[1];
            p2[2]=rp2[2];
            p2[3]=rp2[3];
        }
        int[][] sY=new int[2][pX[0].length];
        int count=0;
        for(int i=0;i<pX[0].length;i++){
            if(pY[0][i]>(pX[0][foreHalf-1]-d)&&pY[0][i]<(pX[0][foreHalf-1]+d)){
                sY[0][count]=pY[0][i];
                sY[1][count]=pY[1][i];
                count=count+1;
            }
        }
        for (int i=0;i<count;i++){
            for(int j=1;j<=15&&(j+1)<count;j++){
                int dl=(sY[0][i]-sY[0][i+j])* (sY[0][i]-sY[0][i+j])+(sY[1][i]-sY[1][i+j])* (sY[1][i]-sY[1][i+j]);
                if(dl<d2){
                    d2=dl;
                    p2[0]=sY[0][i];
                    p2[1]=sY[1][i];
                    p2[2]=sY[0][i+j];
                    p2[3]=sY[1][i+j];
                }
            }
        }
    }
}

第三章

时序分配

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
//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.util.Arrays;

public class IntervarSchedulingDemo {
    public IntervarSchedulingDemo() {
    }

    public static void main(String[] args) {
        int isN = 10;
        int gis = 50;
        int[] isF = new int[isN];
        int[] isS = new int[isN];
        int[] isY = new int[isN];
        int[] isF2 = new int[isN];
        int[] isS2 = new int[isN];
        int[] isY2 = new int[isN];
        int[] isR = new int[isN];
        int beishu = gis;
        int[] flagX = new int[isN];
        int c = 0;

        int i;
        int j;
        while(c < isN) {
            i = (int)(Math.random() * (double)beishu);
            j = (int)(Math.random() * (double)beishu);
            int d3 = (int)(Math.random() * (double)beishu);
            if (i > j) {
                isS[c] = j;
                isF[c] = i;
                isF2[c] = i;
                isY[c] = d3;
                isR[c] = 1;
                flagX[c] = 1;
                ++c;
            }
        }

        StdDraw.setXscale(0.0, (double)beishu);
        StdDraw.setYscale(0.0, (double)beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);

        for(i = 0; i < isN; ++i) {
            for(j = 0; j < isN; ++j) {
                if (isF[i] == isF2[j] && flagX[j] == 1) {
                    isS2[i] = isS[j];
                    isY2[i] = isY[j];
                    flagX[j] = 0;
                    break;
                }
            }
        }

        for(c = 0; c < isN; ++c) {
            if (isR[c] == 1) {
                for(i = c + 1; i < isN; ++i) {
                    if (isS2[i] < isF[c]) {
                        isR[i] = 0;
                    }
                }
            }
        }

        for(i = 0; i < isN; ++i) {
            if (isR[i] == 1) {
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            } else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            }
        }

    }
}

最小生成树

kru

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
import java.util.Arrays;

public class KruskalDemo2{
    public static void main(String[] arrays){
        int VN=9,eN=17,count;
        count=VN;
        int[] cN=new int[VN];
        int[] cS=new int[VN];
        for(int i=0;i<VN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[][]
                e={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=VN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++)
        {
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])-(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for (int i=0;i<eN;i++){
            for (int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int clb=0;
        while (count>=1){
            if (count==1){
                for (int i=0;i<=eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];
                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else{
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            int szj1,szj2;
            szj1=cN[e2[0][clb]];
            szj2=cN[e2[1][clb]];
            if(szj1!=szj2){
                flagEOG[clb]=1;
                count=count-1;
                int dd,xd;
                if (cS[szj1]>=cS[szj2]){
                    dd=szj1;
                    xd=szj2;
                }
                else {
                    dd=szj1;
                    xd=szj2;
                }
                for(int k=0;k<VN;k++){
                    if(cN[k]==dd){
                        cS[dd]=cS[dd]+cS[xd];
                    }
                }
                for (int k=0;k<VN;k++){
                    if(cN[k]==xd){
                        cN[k]=dd;
                    }
                }
            }
            clb=clb+1;
        }
    }
}

prim

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
import java.util.Arrays;
public class PrimDemo {
    public static void main(String[] args) {
        int vN=9,eN=17,count;
        count = vN;
        int[] cN=new int[vN];
        int[] cS=new int[vN];
        for(int i=0;i<vN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[] flagVOG=new int[vN];
        for(int i=0;i<vN;i++){
            flagVOG[i]=0;
        }
        int[][] e ={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=vN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++){
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])+(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for(int i=0;i<eN;i++){
            for(int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int fV=(int)(Math.random()*vN);
        flagVOG[fV]=1;
        int szj1,szj2;
        while (count>=1){
            if(count==1){
                for (int i=0;i<eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];

                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            for(int k=0;k<eN;k++){
                szj1=e2[0][k];
                szj2=e2[1][k];
                if(flagEOG[k]==0&&((flagVOG[szj2]==0&&flagVOG[szj1]==1)||(flagVOG[szj2]==1&&flagVOG[szj1]==0))){
                    flagEOG[k]=1;
                    if(flagVOG[szj2]==0){
                        flagVOG[szj2]=1;
                    }
                    else {
                        flagVOG[szj1]=1;
                    }
                    count--;
                    break;
                }
            }
        }
    }
}

反向删除

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
import java.util.Arrays;

public class ReverseDeleteDemo {
    public static void main(String[] args) {
        int vN = 9, eN = 17, count;
        count = vN;
        int[] c = new int[eN];
        int[] flagv = new int[vN];
        int[] c2 = new int[eN];
        int[] flagEOG = new int[eN];
        int[][] e = {{0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6, 7}, {1, 4, 3, 2, 6, 4, 3, 5, 4, 8, 7, 5, 6, 8, 7, 8, 8}};
        int[][] flag = new int[vN][vN];
        int N = vN;
        int beishu = 9;
        int[] x = {4, 1, 7, 4, 2, 8, 1, 6, 3};
        int[] y = {0, 1, 1, 3, 4, 4, 6, 6, 8};
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2 = new int[2][eN];
        int[] flagX = new int[eN];
        for (int i = 0; i < eN; i++) {
            v3 = e[0][i];
            v4 = e[1][i];
            flagX[i] = 1;
            c[i] = (x[v3] - x[v4]) * (x[v3] - x[v4]) + (y[v3] - y[v4]) * (y[v3] - y[v4]);
            c2[i] = c[i];
            flagEOG[i] = 1;
        }
        Arrays.sort(c);
        for (int i = 0; i < eN; i++) {
            flag[e[0][i]][e[1][i]] = 1;
            flag[e[1][i]][e[0][i]] = 1;
            for (int j = 0; j < eN; j++) {
                if (c[i] == c2[j] && flagX[j] == 1) {
                    e2[0][i] = e[0][j];
                    e2[1][i] = e[1][j];
                    flagX[j] = 0;
                    break;
                }
            }
        }
        int szj1, szj2;
        while (count >= 1) {
            if (count == 1) {
                for (int i = 0; i < eN; i++) {
                    int v1, v2;
                    v1 = e2[0][i];
                    v2 = e2[1][i];
                    if (flagEOG[i] == 1) {
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    } else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    }
                }
                break;
            }
            int cmN = 0;
            for (int k = eN - 1; k >= 0; k--) {
                szj1 = e2[0][k];
                szj2 = e2[1][k];
                flag[szj1][szj2] = 0;
                flag[szj2][szj1] = 0;
                for (int i = 0; i < vN; i++) {
                    flagv[i] = 1;
                }
                cmN = dft(szj1, flag, flagv, vN);
                if (cmN == vN) {
                    flagEOG[k] = 0;
                } else {
                    flag[szj1][szj2] = 1;
                    flag[szj2][szj1] = 1;
                }
            }
            count = 1;
        }
    }

    public static int dft(int v, int[][] flag, int[] flagv, int vN) {
        int count=1;
        flagv[v]=0;
        for(int i=0;i<vN;i++){
            if(flag[v][i]==1&&flagv[i]==1){
                count=count+dft(i,flag,flagv,vN);
            }
        }
        return count;
    }
}

第四章

哈夫曼编码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import java.util.*;
public class HuffmanDemo {
    public static void main(String[] args) {
        int rr = 3;
        //int count=10;
        //char[] cS = {'a','b','c','d','e','f','g','h','i','j'};
        //double[] dF={0.18,0.15,0.11,0.07,0.27,0.019,0.01,0.02,0.17,0.001};
        int count = 7;
        char[] cS = {'a', 'e', 'i', 's', 't', 'b', 'n'};
        double[] dF = {0.1, 0.15, 0.12, 0.03, 0.04, 0.13, 0.01};
        int[] dF2 = new int[count];
        for (int i = 0; i < count; i++) {
            dF2[i] = (int) (dF[i] * 1000);
        }
        int[][] dPS = new int[3][count];
        dPS[2][0] = 0;
        for (int i = 0; i < count; i++) {
            dPS[0][i] = dF2[i];
            dPS[1][i] = i;
            insertHeap(dPS, i + 1);
            dPS[2][0] = dPS[2][0] + 1;
        }
        int[][] cHT = new int[4][count * 2];
        for (int i = 0; i < count; i++) {
            cHT[0][i] = i;
            cHT[1][i] = -1;
            cHT[2][i] = -1;
            cHT[3][i] = 1;
        }
        int beishu = count * rr * 4;
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int root = 0;
        int n = count;
        int count2 = count;
        while (count >= 1) {
            if (count == 1) {
                //输出显示哈夫曼树
                inOrderPaint(root, cS, cHT, count2 * 5, count2 * 4 * rr - 10, rr, count2 * 1.9);
                break;
            }
            int mF = dPS[1][0];
            int f1 = dPS[0][0];
            //从优先队列中取出频率最小的结点
            dPS[0][0] = dPS[0][dPS[2][0]-1];
            dPS[1][0] = dPS[1][dPS[2][0]-1];
            //从优先队列最后结点放到第一个结点的位置
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //重新调整为新的优先队列
            int mS = dPS[1][0];
            int f2 = dPS[0][0];
            dPS[0][0] = dPS[0][dPS[2][0] - 1];
            dPS[1][0] = dPS[1][dPS[2][0] - 1];
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //从优先队列中取出频率次小的结点
            cHT[0][n] = n;
            cHT[1][n] = mF;
            cHT[2][n] = mS;
            if (cHT[3][mF] > cHT[3][mS]) {
                cHT[3][n] = cHT[3][mF] + 1;
            }
            dPS[0][dPS[2][0]] = f1 + f2;
            dPS[1][dPS[2][0]] = n;
            dPS[2][0] = dPS[2][0] + 1;
            insertHeap(dPS, dPS[2][0]);
            //新结点加入优先树
            root = n;
            n = n + 1;
            count = count - 1;
        }
    }

    public static void insertHeap(int[][] dPS, int i) {
        int zj,j;
        if(i>1){
            j=i/2;
            if(dPS[0][i-1]<dPS[0][j-1]){
                zj=dPS[0][i-1];
                dPS[0][i-1]=dPS[0][j-1];
                dPS[0][j-1]=zj;
                zj=dPS[1][i-1];
                dPS[1][i-1]=dPS[1][j-1];
                dPS[1][j-1]=zj;
                insertHeap(dPS,j);
            }
        }
    }

    private static void deleteHeap(int[][] dPS, int i) {
        int n;
        int left,right,zj;
        n=dPS[2][0];;
        int j = 0;
        if(2*i>n)
            return;
        else if(2*i<n){
            left=2*i;
            right=2*i+1;
            if(dPS[0][left-1]>dPS[0][right-1]) {
                j = right;
            }
            else {
                j = left;
            }
        }else if(n==2*i){
            j=2*i;
        }
        if(dPS[0][j-1]<dPS[0][i-1]){
            zj=dPS[0][i-1];
            dPS[0][i-1]=dPS[0][j-1];
            dPS[0][j-1]=zj;
            zj=dPS[1][i-1];
            dPS[1][i-1]=dPS[1][j-1];
            dPS[1][j-1]=zj;
            deleteHeap(dPS,j);
        }
    }
    private static void inOrderPaint(int root, char[] cS, int[][] cHT, double x, double y, double r, double jg) {
        double xC,yC,xS,yS,rC,zj1,zj2;
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.circle(x,y,r);
        if(cHT[1][root]!=-1&&cHT[2][root]==-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]==-1){
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]!=-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[1][root]);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[2][root]);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]==-1&&cHT[1][root]==-1){
            xS=x-0.05*r;
            yS=y;
            String s=""+cS[cHT[0][root]];
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.text(xS,yS,s);
        }
    }
}


时隙最优解权值和

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
import java.util.Arrays;

public class ComputeRDemo {
    public static void main(String[] args){
        int isN=10,gis=50;
        int[] isF=new int[isN];
        int[] isS=new int[isN];
        int[] isV=new int[isN];
        int[] isF2=new int[isN];
        int[] isS2=new int[isN];
        int[] isY2=new int[isN];
        int[] isV2=new int[isN];
        int[] isR=new int[isN];
        int[] isM=new int[isN];
        int beishu=gis;
        int[] flagX=new int[isN];
        int c=0;
        while (c<isN){
            int d1=(int)(Math.random()*beishu);
            int d2=(int)(Math.random()*beishu);
            int d3=(int)(Math.random()*beishu);
            int d4=(int)(Math.random()*beishu);
            if(d1>d2){
                isS[c]=d2;
                isF[c]=d1;
                isF2[c]=d1;
                isV[c]=d4;
                isV2[c]=d4;
                flagX[c]=1;
                c=c+1;
            }
            }
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);
        for (int i=0;i<isN;i++){
            isR[i]=0;
            isM[i]=-1;
        }
        for (int i=0;i<isN;i++){
            for (int j=0;j<isN;j++){
                if (isF[i]==isF2[j]&&flagX[j]==1){
                    isS2[i]=isS[j];
                    isV2[i]=isV[j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int[] isP=new int[isN];
        int[] isSX=new int[isN];
        int[] isSY=new int[isN];
        for (int i=0;i<isN;i++){
            isP[i]=-1;
            isY2[i]=(int)(beishu/isN*(isN-i)-0.5);
            isSY[i]=isY2[i]-2;
            isSX[i]=(int)((isS2[i]+isF[i])/2);
        }
        for(int i=0;i<isN;i++){
            for(int j=i-1;j>=0;j--){
                if (isS2[i]>isF[j]){
                    isP[i]=j;
                    break;
                }
            }
        }
        computeOpt(isV2,isM,isP,isN-1);
        findSolutions(isM,isV2,isR,isP,isN-1);
        for (int i=0;i<isN;i++){
            StdDraw.setPenColor(StdDraw.BLUE);
            StdDraw.text(isSX[i],isSY[i],""+isV2[i]);
            if (isR[i]==1){
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
            else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
        }
    }
    public static int computeOpt(int[] V,int[] M,int[] P,int j) {
        if (j <= -1)
            return 0;
        else {
            int d1 = computeOpt(V, M, P, P[j]);
            int d2 = computeOpt(V, M, P, j - 1);
            if ((V[j] + d1) < d2) {
                M[j]=d2;
                return d2;
            }
            else {
                M[j]=V[j]+d1;
                return (V[j]+d1);
            }
        }
    }
    public static void findSolutions(int[] M,int[] V,int[] R,int[] P,int j){
        int i=j;
        int d1,d2,d3=0;
        while (i>=0){
            if (P[i]==-1)
                d1=d3+V[i];
            else {
                d1=d3+V[i]+M[P[i]];
            }
            if (d1==M[j]){
                R[i]=1;
                d3=d3+V[i];
                i=P[i];
            }
            else {
                i=i-1;
            }
        }
    }
}

分段最小二乘法

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import java.awt.*;
import javax.swing.*;
import java.util.Scanner;
import javax.swing.JPanel;

public class SLMSDemo extends JFrame{
    //16个点的点集，第一行为横坐标，第二行为纵坐标
    static int P[][]={{20,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180},
                {10,11,12,13,14,34,56,77,99,118,121,124,127,128,129,131}};
    //分段限制参数C，C越大，分的段数越少，可避免过拟合
    static double C=100;
    //设置一个极大值常量
    static final int MAXV=1000000000;
    //设置最大分段数
    static int maxS=100;
    //实际分段数
    static int mc=0;
    //点集共16个点
    static int n=16;
    //从1到j,j=1,2,...n的最小拟合误差,下标0做初始值，值为0
    static double[] optC=new double[n+1];
    //每个可能的子集的拟合直线a参数
    static double[][] a=new double[n][n];
    //每个可能的子集的最小乘误差
    static double[][] eC=new double[n][n];
    //每个可能的子集的拟合直线的b参数
    static double[][] b=new double[n][n];
    //最优的分段结果，第一行该子集的第一个点的下标，第二行为该子集的最后一个点的下标
    static int[][] mS=new int[2][maxS];
    //静态块初始化optC的初始边界值为0
    static {
        optC[0]=0;
    }
    public SLMSDemo(){}

    public static void main(String[] args) {
        SLMSDemo frame = new SLMSDemo();
        //计算a,b,eC
        ComputeE();
        //计算每个1...j子集的最优拟合代价
        mc = ComputeOPT();
        //显示输出计算结果
        DrawPanel rd= new DrawPanel(P,a,b,mS,mc);
        frame.add(rd);
        frame.setSize(400,400);
        frame.setTitle("分段最小二乘演示程序");
        frame.setLocationRelativeTo(null);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }



    private static void ComputeE() {
        for(int j=0;j<n;j++){
            for(int i=0;i<=j;i++){
                int xySum=0;
                int xSum=0;
                int ySum=0;
                int xxSum=0;
                for(int k=i;k<=j;k++){
                    xySum+=P[0][k]*P[1][k];
                    xxSum+=P[0][k]*P[0][k];
                    xSum+=P[0][k];
                    ySum+=P[1][k];
                }
                double zj=((j-i+1)*xxSum-xSum*xSum);
                if(zj!=0){
                    a[i][j]=((j-i+1)*xySum-xSum*ySum)/zj;
                }else{
                    a[i][j]=MAXV;
                }
                b[i][j]=(ySum-a[i][j]*xSum)/(j-i+1);
                int eSum=0;
                for(int k=i;k<=j;k++){
                    eSum+=(P[1][k]-P[0][k]*a[i][j]-b[i][j])*(P[1][k]-P[0][k]*a[i][j]-b[i][j]);
                }
                eC[i][j]=eSum;
            }
        }
    }
    public static int ComputeOPT() {
        for(int j=1;j<=n;j++){
            double emin=MAXV;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                }
            }
            optC[j]=emin;
            //System.out.println(optC[j]+"");
        }
        int m=0;
        int j=n;
        while (j>=1){
            double emin=MAXV;
            int imin=0;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                    imin=i;
                }
            }
            mS[0][m]=imin-1;
            mS[1][m]=j-1;
            m=m+1;
            j=imin-1;
        }
        return m;
    }
}
class DrawPanel extends JPanel{
    private int widthP=400;
    private int tw=40;
    private int heightP=widthP-tw;
    private int width=0;
    private int height=0;
    private Color axisColor=Color.BLACK;
    private Color scatColor=Color.BLUE;
    private Point origin;
    private Point originA;
    private int cx=5;
    private int cy=5;
    private int beishu;
    private int sC=100;
    private int[][] P;
    private double[][] a;
    private double[][] b;
    private int[][] mS;
    private int mc;
    public DrawPanel(){
        originA=new Point(2,380-2);
    }
    public DrawPanel(Point p){
        origin=p;
    }
    public DrawPanel(int x,int y){
        origin=new Point(0,0);
        width=x;
        height=y;
    }

    public DrawPanel(int[][]P,double[][]a,double[][]b,int[][]mS,int mc){
        cx=5;
        cy=5;
        sC=16;
        this.P=P;
        this.a=a;
        this.b=b;
        this.mS=mS;
        this.mc=mc;
        beishu=2;
        originA=new Point(cx,this.heightP-cy);
    }
    public int getArea(){
        return width*height;
    }
    protected void paintComponent(Graphics g){
        paintXY(g);
        paintScatters(g);
        paintLines(g);
    }
    private void paintXY(Graphics g){
        g.setColor(axisColor);
        g.drawLine(originA.x,originA.y,originA.x+widthP-cx,originA.y);
        g.drawLine(originA.x,originA.y,originA.x,originA.y-heightP+cy+tw);
    }
    private void paintScatters(Graphics g){
        g.setColor(scatColor);
        for(int i=0;i<sC;i++){
            g.drawOval(originA.x+P[0][i]*beishu,originA.y-P[1][i]*beishu,cx,cy);
        }
    }
    private void paintLines(Graphics g){
        for(int i=0;i<mc;i++){
            int y1=(int)((a[mS[0][i]][mS[1][i]]*P[0][mS[0][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x1=P[0][mS[0][i]]*beishu;
            int y2=((int)(a[mS[0][i]][mS[1][i]]*P[0][mS[1][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x2=P[0][mS[1][i]]*beishu;
            g.setColor(Color.RED);
            g.drawLine(originA.x+x1,originA.y-y1,originA.x+x2,originA.y-y2);
        }
    }

}

背包问题

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
import java.io.*;
import java.util.*;

public class KnapsackDemo {
    static int n = 10;
    static int W = 100;
    //static int[] iW={6,17,8,21,4,7,8,12,9,11};
    //static int[] iV={7,21,14,23,6,6,9,11,8,14};
    static int[] iW = {6, 17, 8, 21, 4, 7, 8, 12, 9, 11};
    static int[] iV = {7, 21, 14, 5, 6, 6, 9, 11, 8, 14};
    static int[][] optC = new int[n + 1][W + 1];
    static int sN = 0;
    static int vG = 0;
    static int wG = 0;
    static int[] iS = new int[n];

    static {
        for (int j = 0; j <= W; j++) {
            optC[0][j] = 0;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("所选物件编号为");
        for (int i = 0; i < n; i++) {
            System.out.print(iS[i] + " ");
        }
        System.out.print("\n");
        System.out.println("占用总空间为: " + wG);
        System.out.println("总价值为: " + vG);
    }

    public static void computeOPT() {
        for (int j = 1; j <= n; j++) {
            for (int w = 0; w <= W; w++) {
                if (w < iW[j - 1]) {
                    optC[j][w] = optC[j - 1][w];
                } else {
                    int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                    if (zj > optC[j - 1][w]) {
                        optC[j][w] = zj;
                    } else {
                        optC[j][w] = optC[j - 1][w];
                    }
                }
            }
        }
        int j = n;
        int w = W;
        while (j > 0) {
            if (w < iW[j - 1]) {
                j = j - 1;
            } else {
                int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                if (zj > optC[j - 1][w]) {
                    iS[sN] = j;
                    sN = sN + 1;
                    vG = vG + iV[j - 1];
                    wG = wG + iW[j - 1];
                    w = w - iW[j - 1];
                    j = j - 1;
                } else {
                    j = j - 1;
                }
            }
        }
    }
}

串匹配

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
import java.util.Hashtable;

public class SequenceAlignmentDemo {
    static int m=10;
    static int n=10;
    static String X="governance";
    static String Y="government";
    static String aY="";
    static String aX="";
    static int d=2;
    static int[][] A=new int[26][26];
    static int[][] M=new int[2][m];
    static int mL=0;
    static{
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                if(i==j){
                    A[i][j]=0;
                }else{
                    A[i][j]=d*2;
                }
            }
        }
    }
    static String elpha[]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n",
                          "o","p","q","r","s","t","u","v","w","x","y","z"};
    static Integer index[]={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};
    static Hashtable<String,Integer> ht=new Hashtable<String,Integer>();
    static{
        for(int i=0;i<26;i++){
            ht.put(elpha[i],index[i]);
        }
    }
    static int[][] optC=new int[m+1][n+1];
    static {
        for(int j=0;j<=m;j++){
            optC[j][0]=j*d;
        }
        for(int j=0;j<=n;j++){
            optC[0][j]=j*d;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("最优匹配代价值为: "+optC[m][n]);
        System.out.println("最优匹配集为: ");
        for(int i=0;i<mL;i++){
            System.out.print("("+M[0][i]+","+M[1][i]+")");
            if(Math.floorMod(i+1,4)==0)
                System.out.print("\n");
        }
        System.out.print("\n");
        System.out.println(aX);
        System.out.println(aY);
    }
    public static void computeOPT(){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                        +optC[i-1][j-1];
                int zj2=d+optC[i-1][j];
                int zj3=d+optC[i][j-1];
                if(zj1<zj2&&zj1<zj3){
                    optC[i][j]=zj1;
                }
                if (zj2<=zj1&&zj2<=zj3){
                    optC[i][j]=zj2;
                }
                if(zj3<=zj1&&zj3<=zj2){
                    optC[i][j]=zj3;
                }
            }
        }
        int i=m;
        int j=n;
        while (i>=1||j>=1){
            int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                    +optC[i-1][j-1];
            int zj2=d+optC[i-1][j];
            int zj3=d+optC[i][j-1];
            if(zj1<zj2&&zj1<zj3){
                aX=X.substring(i-1,i)+aX;
                aY=Y.substring(j-1,j)+aY;
                M[0][mL]=i;
                M[1][mL]=j;
                mL=mL+1;
                i--;
                j--;
            }
            if(zj2<=zj1&&zj2<=zj3){
                aY="-"+aY;
                aX=X.substring(i-1,i)+aX;
                i=i-1;
            }
            if(zj3<=zj1&&zj3<=zj2){
                aX="-"+aX;
                aY=Y.substring(j-1,j)+aY;
                j=j-1;
            }
        }
    }
}
≡