实验3贪心算法和回溯法.doc

实验3 贪心算法和回溯法一、实验目的1. 理解最小生成树算法Prim算法和Kruskal算法的基本思想，学会编程实现这两种算法；2. 理解并查集的特点与适用环境，学会使用并查集解决常见的问题；3. 理解单源最短路径算法Dijkstra算法的基本思想，学会编程实现Dijkstra算法；4. 理解回溯法的基本思想，学会使用回溯法解决常见的问题。二、实验内容1. 编程实现Prim算法。输入：顶点编号及边权重。例：0 1 100 2 151 2 50输出：最小生成树。例：0 1 100 2 15源代码：import java.util.Scanner;public class prim public static final int MAX1 = 100;public static void main(String args) float c = 0,0,10,15,0,10,0,50,0,1,50,0;/1到2,10 1到3,15 2到3,50for (int i = 1; i = 3; i+) for (int j = 1; j = 3; j+) cij = MAX1;/初始化两点之间的距离为无穷大prim(3, c);public static void prim(int n, float c) float lowcost = new floatn + 1;/记录不在S中的顶点在S中的最近邻接点int closest = new intn + 1;/记录不在S中的顶点到S的最短距离，即到最近邻接点的权值 boolean s = new booleann + 1; /标记顶点是否被访问，访问过的顶点标记为trues1 = true;/标记第一个点被访问过for (int i = 2; i = n; i+) lowcosti = c1i;/获取其他顶点到第一个点之间的距离closesti = 1;si = false;for (int i = 1; i n; i+) float min = Float.MAX_VALUE;int j = 1;for (int k = 2; k = n; k+)if (lowcostk min) & (!sk) min = lowcostk;j = k;System.out.println(closestj + + j + + lowcostj);sj = true;for (int k = 2; k = n; k+) if (cjk lowcostk & (!sk) lowcostk = cjk;closestk = j;2. 在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？输入：第1行的第1个值表示总人数，第2个值表示总信息数；第2行开始为具体的认识关系信息。例：10 42 34 54 85 8输出：单位个数。例：7源代码：import java.util.Scanner;public class npeoplefinal static int MAX=100;/最大的结点的个数static int parent;/结点的父结点static int rank;public npeople(int x)for(int i=0;iranky)parenty=x;elseif(rankx=ranky)ranky+;parentx=y;public static void main(String args) parent=new intMAX;rank=new intMAX;Scanner scan=new Scanner(System.in);int n,m;int x,y;n=scan.nextInt();m=scan.nextInt();for(int i=0;i=n;i+)parenti=i;for(int i=1;i=m;i+)x=scan.nextInt();y=scan.nextInt();union_set(x,y);int count=0;for(int i=1;i=n;i+)if(parenti=i)count+;System.out.println(count);3. 编程实现Kruskal算法。输入：顶点编号及边权重。例：0 1 100 2 151 2 50输出：最小生成树。例：0 1 100 2 15源代码：#include #include using namespace std;/* 定义边(x,y)，权为w */typedef structint x, y;int w;edge;const int MAX = 26;edge eMAX * MAX;int rankMAX;/* x的秩 */int fatherMAX;/*x的父节点 */int sum; /*存储最小生成树的总权重 */ /* 排序函数 */bool cmp(const edge a, const edge b) return a.w ranky)fathery = x;elseif (rankx = ranky)ranky+;fatherx = y;sum += w; /记录权重 int main()int i, j, k, m, n, t;char ch;while(cin m & m != 0)k = 0;for (i = 0; i m; i+) make_set(i); /初始化集合，m为顶点个数 /对后m-1进行逐行处理 for (i = 0; i ch n; /获取字符（顶点） for (j = 0; j ch ek.w; /获取权重 ek.x = i;ek.y = ch - A;k+; sort(e, e + k, cmp); /数组进行排序 sum = 0; for (i = 0; i k; i+)union_set(find_set(ei.x), find_set(ei.y), ei.w); cout sum endl;return 0;4. 编程实现Dijkstra算法。输入：第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边权重。例：5 70 1 100 3 300 4 1001 2 502 4 103 2 203 4 60输出：顶点0到每一个顶点的最短路径长度。例：0 10 50 30 60源代码：import java.util.Scanner;public class Test public static void main(String args) System.out.println(请输入顶点的个数以及边的个数);Scanner in = new Scanner(System.in);int n = in.nextInt();int m=in.nextInt();int map= new intnn;for (int i = 0; im; i+) int a=in.nextInt(); int b=in.nextInt(); int c=in.nextInt(); mapab=c;int dist = new intn;/存放每一个点到源点的距离dijkstra(0,n,map,dist);public static void dijkstra(int s, int n, int map,int dist) boolean used = new booleann;int maxint=0;for (int i = 1; i = map.length; i+) disti = mapsi;int k = 0;for (int i = 1; i = n; i+) int tmin = maxint;for (int j = 1; j distj) tmin = distj;k = j;usedk = true;for (int j2 = 1; j2 = n; j2+) if (distk + mapkj2 distj2)distj2 = distk + mapkj2;5. 使用回溯法求解N皇后问题。输入：皇后的个数。例：4输出：每一个方案及总方案数。例：0 1 0 00 0 0 23 0 0 00 0 4 0-0 0 1 02 0 0 00 0 0 30 4 0 0-总方案数为2。源代码：public class nhuanghou public static final int N = 4;public static int count = 0;public static int M = new intN;/ 同一列public static int L = new int2 * N;/ 右对角线public static int R = new int2 * N;/ 左对角线public static int A = new intNN; / 同一行private static void print(int A) int i, j;for (i = 0; i N; i+) for (j = 0; j N; j+)System.out.print(Aij + );System.out.println();System.out.println();private static int mytry(int i, int M, int L, int R, int A) for (int j = 0; j N; j+)if (Mj != 1 & Li - j + N != 1 & Ri + j != 1) / 若果都没有放置皇后，则往下移动一行Aij = i + 1;Mj = Li - j + N = Ri + j = 1;if (i = N - 1) / 若果到了最后一行，则输出，否则就移除皇后print(A);count+; elsemytry(i + 1, M, L, R, A);Aij = 0;Mj = Li - j + N = Ri + j = 0;return count;public static void main(String args) int n = mytry(0, M, L, R, A);System.out.println(放置皇后的总数count= + n);6. 使用回溯法求解0-1背包问题。输入：两个一维数组分别存储每一种物品的价值和重量，以及一个整数表示背包的总重量。例：价值数组v = 6,3,6,5,4，重量数组w = 2,2,4,6,5，背包重量C=10。输出：背包的最大总价值。例：最大总价值=15源代码：public class Package01static final int N=5;static int v=6,3,6,5,4;/价值数组v = 6,3,6,5,4static int w=2,2,4,6,5;/重量数组w = 2,2,4,6,5static int c=10;/背包重量C=10static int cp; /当前价值 static int bestp=0; /最优价值static int x=new intN; /当前解static int bestx=new intN;/当前最优解public static void main(String args)knap(0);System.out.println(bestp);for(int j=0;j=N)i