算法分析与设计之套汇问题java源代码和实验报告

算法分析与设计之套汇问题java源代码和实验报告 算法作为计算机专业学生的必修课，同时也是软件开发过程中必备的编程思想，对学习研究计算机专业意义重大；正因为这门课程难，所以除了相关方面的书籍，网络资源少的可怜,尤其是java代码简直如大海捞针。因此，做完这次课程设计，我决定把这些资源传到广大学生钟爱的CSDN上供大家分享学习，希望能真正帮到大家！

import java.util.Scanner;

public class Test4 {
	final static int MAX_VERTECX_NUM = 20;
	final static int INT_MIN = 0;

	static int[][] Path = new int[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录套汇过程中要经过的路径
	static float[][] value = new float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];//用来记录经过讨回操作后得到的值

	/**
	 * 套汇问题
	 */
	public static void main（String[] args） {
		// TODO Auto-generated method stub

		int i flag = 0;
		MGraph G = new MGraph（）;
		CreateDG（G）;
		ShortestPath_FLOYD（G）;
		//在输出兑换序列时采用了递归算法：这个算法逆序输出了兑换序列
		for （i = 1; i <= G.vexnum; i++） {
			if （value[i][i] > 1） {
				System.out.println（“兑换结果为：“ + value[i][i]）;
				if （Path[i][i] != 0）
					System.out.println（i + “ “ + i）;
				System.out.print（“兑换顺序的逆序输出：“ + i + “ “）;
				Procedure_print（i i）;//递归，货币i至j中间顶点
				System.out.println（）;
				flag = 1;
			}
		}
		if （flag == 0）
			System.out.println（“不存在套汇路线！“）;

	}

	static void CreateDG（MGraph G） {
		int i j = 0 k;
		float w = 0;
		System.out.print（“请输入节点和弧度：“）;
		Scanner sc = new Scanner（System.in）;
		G.vexnum = sc.nextInt（）;
		G.arcnum = sc.nextInt（）;
		System.out.println（“G->vexnum=“ + G.vexnum + ““ + “G->arcnum=“
				+ G.arcnum）;
		for （i = 1; i <= G.vexnum; i++） {
			G.vexs[i] = i;
		}
		for （i = 1; i <= G.vexnum; i++） {
			for （j = 1; j <= G.vexnum; j++） {
				G.arc[i][j] = INT_MIN;
			}
		}
		System.out.println（“请输入矩阵：“）;
		sc = new Scanner（System.in）;
		for （k = 1; k <= G.arcnum; k++） {
			String str = sc.next（）;
			i = Integer.parseInt（str.split（““）[0]）;
			j = Integer.parseInt（str.split（““）[1]）;
			w = Float.parseFloat（str.split（““）[2]）;
			G.arc[i][j] = w;
		}

	}

	static void ShortestPath_FLOYD（MGraph G） {
		int i j k;
		for （i = 1; i <= G.vexnum; i++） {
			for （j = 1; j <= G.vexnum; j++） {
				if （i == j）
					value[i][j] = 1;
				else
					value[i][j] = G.arc[i][j];
				if （G.arc[i][j] > INT_MIN）
					Path[i][j] = i;
				else
					Path[i][j] = 0;
			}
		}
		//算法中的关键步骤：
		for （k = 1; k <= G.vexnum; k++） {
			for （i = 1; i <= G.vexnum; i++） {
				for （j = 1; j <= G.vexnum; j++） {
					if （!（i == j && j == k）） {
						if （value[i][k] * value[k][j] > value[i][j]） {//这里判断是否使兑换率增大，如果增大则记录下来
							value[i][j] = value[i][k] * value[k][j];
							Path[i][j] = Path[k][j];
						}
					}
				}
			}

		}
	}

	static void Procedure_print（int i int j） {
		if （Path[i][j] == i） {
			System.out.println（i）;
			return;
		} else {
			System.out.print（Path[i][j]+“ “）;
			Procedure_print（i Path[i][j]）;
		}
	}

}

class MGraph {
	final static int MAX_VERTECX_NUM = 20;
	final static int INT_MIN = 0;

	static int[][] Path = new int[MAX_VERTECX_NUM][MAX_VERTECX_NUM];
	static float[][] value = new float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];
	int[] vexs = new int[MAX_VERTECX_NUM]; // 顶点向量 可以存储每个顶点的信息
	float[][] arc = new float[MAX_VERTECX_NUM][MAX_VERTECX_NUM];// 邻接矩阵
																// 主要存放关于边的信息
	int vexnum arcnum; // 图中当前顶点数和弧数
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-11-27 12:58  java算法分析与设计之套汇问题源代码和实验报告\
     目录           0  2012-11-27 12:58  java算法分析与设计之套汇问题源代码和实验报告\04\
     文件         232  2012-11-16 12:32  java算法分析与设计之套汇问题源代码和实验报告\04\.classpath
     文件         378  2012-11-19 12:59  java算法分析与设计之套汇问题源代码和实验报告\04\.project
     目录           0  2012-11-27 12:58  java算法分析与设计之套汇问题源代码和实验报告\04\bin\
     文件         609  2012-11-19 17:48  java算法分析与设计之套汇问题源代码和实验报告\04\bin\MGraph.class
     文件        3326  2012-11-19 17:48  java算法分析与设计之套汇问题源代码和实验报告\04\bin\Test4.class
     目录           0  2012-11-27 12:58  java算法分析与设计之套汇问题源代码和实验报告\04\src\
     文件        3178  2012-11-21 13:30  java算法分析与设计之套汇问题源代码和实验报告\04\src\Test4.java
     文件       83721  2012-11-21 19:58  java算法分析与设计之套汇问题源代码和实验报告\04.docx