Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Main {
- static double minAvg;
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- System.out.println("type in frequency from the keyboard, use , to split.。");
- String input = sc.nextLine();
- String[] inputArray = input.split(",");
- double[] inputFrequency= new double[inputArray.length];
- for(int i = 0;i < inputFrequency.length;i++) {
- inputFrequency[i] = Float.parseFloat(inputArray[i]);
- }
- int n = inputFrequency.length ;
- //Root table
- int [][]R = new int[n+1][n+1];
- double A [][] = optst(n,inputFrequency,R);
- showAtable(A);
- System.out.println();
- System.out.println();
- showRtable(R);
- System.out.println();
- System.out.println();
- new BinarySearchTree().showRTableTree(R);
- }
- //algorithm, find min cost
- static double[][] optst(int n, double p[],int R[][]){
- int i,j,diagonal;
- double [][]A = new double[n+1][n+1];
- for (i=1; i<=n; i++) {
- A[i-1][i-1] = 0;
- A[i-1][i] = p[i-1];
- R[i-1][i] = i;
- R[i-1][i-1] = 0;
- }
- for(diagonal=1; diagonal<=n-1; diagonal++) {
- for(i=1; i<=n-diagonal; i++) {
- j = i + diagonal;
- double minimum = Double.MAX_VALUE;
- double sum = 0;
- int minr = 0;
- for(int k=i; k<=j; k++) {
- if (A[i-1][k-1]+A[k][j] < minimum) {
- minimum = A[i-1][k-1]+A[k][j];
- minr = k;
- }
- sum += p[k-1];
- }
- A[i-1][j] = minimum + sum;
- R[i-1][j] = minr;
- }
- }
- return A;
- }
- static void showAtable(double a[][]) {
- for(int i=0;i<a.length;i++)
- {
- for(int z=0;z<a.length;z++) {
- System.out.printf("%.3f"+"\t",a[i][z]);
- }
- System.out.println();
- }
- }
- static void showRtable(int a[][]) {
- for(int i=0; i<a.length; i++) {
- for(int j=0; j<a[0].length;j++) {
- System.out.print(String.valueOf(a[i][j]) + "\t\t");
- }
- System.out.println();
- }
- }
- }
- class BinarySearchTree {
- public void showRTableTree(int array[][]) {
- Node node = new Node();
- build(array, node, 1, array.length-1, 0, -1);
- node.showTree(node);
- }
- Node build(int array[][], Node node, int leftpivot, int rightpivot, int level, int i) {
- if (leftpivot == rightpivot) {//Check if it is a leaf
- Node sub = new Node();
- sub.node = array[leftpivot][rightpivot];
- sub.level = level;
- i++;
- sub.index = i;
- return sub;
- }
- int subRoot = array[leftpivot][rightpivot];//sub Root
- node.node = array[leftpivot][rightpivot];
- node.level = level;
- level ++;
- int new_leftpivot = subRoot-1;
- int new_rightpivot = subRoot+1;
- //find left sub tree
- Node newTree = new Node();
- if (new_leftpivot>=leftpivot) {
- //將傳的左子樹放入次樹的左子樹
- node.leftNode = build(array, newTree, leftpivot, new_leftpivot, level, i);
- i = node.leftNode.index;
- }
- i++;//has several nodes before it.
- node.index = i;
- //find right sub tree
- if (new_rightpivot<=rightpivot) {
- node.rightNode = build(array, newTree, new_rightpivot, rightpivot, level, i);
- i = node.rightNode.index;
- }
- return node;
- }
- class Node {
- Node leftNode ;
- Node rightNode;
- int node = 0;
- int level = 0;
- int index = 0;
- int nowlevel = 0;
- void showTree(Node node) {
- if (nowlevel != node.level) {
- System.out.println();
- nowlevel = node.level;
- }
- //according to this node has how many nodes before it
- for (int i = 0; i< node.index; i++) {
- System.out.print("\t\t");
- }
- System.out.print(node.node);
- if (node.leftNode != null) {
- showTree(node.leftNode);
- }
- if (node.rightNode != null) {
- showTree(node.rightNode);
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment