numtangle.java

求解数字三角形 可以手动输入和随机生成 输出最大路径的值 和 最大路径！

//数字三角形问题的求解
//假设每个三角形的最大值是唯一的 且 路径是唯一的 （否则按照默认的处理方法处理）
//必须是小于等于10行的数字三角形

import java.util.Random;
import java.util.Scanner;

class TangleArray{
	private static Random ran = new Random();
	private static Scanner san = new Scanner(System.in);
	public void numMake(int[][] a){		//随机生成一个数字三角形
		for(int i=0;i<a.length;i++){
			a[i] = new int[i+1];
			for(int j=0;j<a[i].length;j++){
				a[i][j] = ran.nextInt(10);
			}
		} 
	}
	public void outNum(int[][] a){		//输出二维数组
		for(int i=0;i<a.length;i++){
			for(int k=0;k<a.length-i;k++){	//控制打印格式
				System.out.print("      ");
			}
			for(int j=0;j<a[i].length;j++){
				System.out.printf("%12d",a[i][j]);
			}
			System.out.println();
			System.out.println();
		}
	}
	public void inNum(int[][] a){		//输入一个二维数组
		for(int i=0;i<a.length;i++){
			a[i] = new int[i+1];
			for(int j=0;j<a[i].length;j++){
				a[i][j] = san.nextInt();
			}
			System.out.println();
		}
	}
	public int findMax(int[] a){		//找出一维数组中的最大项
		int max;
		max=a[0];
		for(int i=0;i<a.length;i++){
			if(a[i]>max){
				max = a[i];
			}
		}
		return max;
	}
	public void outMaxPath(int maxPath,int flag){	//输出最大路径 其中flag为数字三角形的高度
		int t,s,m;
		m = maxPath;
		t = 1;
		for(int i=0;i<flag-1;i++){
			t = t*10;
		}
		for(int i=flag;i>0;i--){
			s = m/t;
			m = m%t;
			t = t/10;
			System.out.print("["+(flag+1-i)+"]"+"["+s+"]"+" ");
		}
		System.out.println();
	}
}

public class NumTangle{
	private static Scanner san = new Scanner(System.in);
	public static void main(String[] args){
		int m,flag;
		TangleArray tan = new TangleArray();
		System.out.print("请输入计算数字三角形的高度(大于2小于10的自然数)：");		//暂时高度最多为4
		m = san.nextInt();
		int[][] newNum = new int[m][];
		//给newNum初始化
		System.out.print("      1:手动输入值请输入    2:自动生成请输入请选择：");
		flag = san.nextInt();
		if(flag == 1){
			tan.inNum(newNum);
		}
		else if(flag == 2){
			tan.numMake(newNum);
		}
		else{
			System.out.println("输入错误！");
		}
		//打印初始数组的值
		System.out.println("打印初始数组的值:");
		tan.outNum(newNum);
		//计算最大路径和最大值
		int[][] newNumStore = new int[m][];
		int[][] newNumPath = new int[m][];
		newNumStore[0] = new int[1];		//对newNumStore第一行进行初始化
		newNumStore[0][0] = newNum[0][0];
		newNumPath[0] = new int[1];		//对newNumPath第一行进行初始化	
		newNumPath[0][0] = 1;
		for(int i=1;i<newNum.length;i++){	//i=1 从第二行开始
			newNumStore[i] = new int[newNum[i].length];
			newNumPath[i] = new int[newNum[i].length];
			for(int j=0;j<i+1;j++){
				if(j==0){	//newNumStore每行的第一个和最后一个进行计算
					newNumStore[i][0] = newNumStore[i-1][0]+newNum[i][0];
					newNumPath[i][0] = newNumPath[i-1][0]*10+1;
				}
				else if(j==i){
					newNumStore[i][i] = newNumStore[i-1][i-1]+newNum[i][i];
					newNumPath[i][j] = newNumPath[i-1][j-1]*10+(j+1);
				}
				else{		//对每行中间的元素进行处理
					if(newNumStore[i-1][j-1]>newNumStore[i-1][j]){	
						newNumStore[i][j] = newNumStore[i-1][j-1]+newNum[i][j];
						newNumPath[i][j] = newNumPath[i-1][j-1]*10+(j+1);
					}
					else{	//值相同时的路径用默认的方法进行处理，暂时不计算相同时的所有路径
						newNumStore[i][j] = newNumStore[i-1][j]+newNum[i][j];
						newNumPath[i][j] = newNumPath[i-1][j]*10+(j+1);
					}
				}
			}
		}
		//找出其中的最大值
		System.out.println("最大值："+tan.findMax(newNumStore[m-1]));
		//找出相应的最大值的路径
		int f=0;
		for(int i=0;i<newNumStore[m-1].length;i++){
			if(newNumStore[m-1][f] < newNumStore[m-1][i]){
				f = i;
			}
		}
		System.out.print("最大值的路径：");
		tan.outMaxPath(newNumPath[m-1][f],m);
	}
}