题目描述

将正整数排成等边三角形（也叫数塔），三角形的底边有个数，下图给出了的一个例
子。从三角形顶点出发通过一系列相邻整数（在图中用正方形表示），如何使得到达底边
时的总和最大？

算法思想

动态规划
自顶向下应用递推式F[i][j] = num[i][j] + max(F[i+1][j], F[i+1][j+1])一级一级向下求解。

结果

代码

package CourseDesign;

import javafx.application.Application;
import javafx.application.Platform;
import javafx.geometry.HPos;
import javafx.geometry.Insets;
import javafx.geometry.Pos;
import javafx.geometry.VPos;
import javafx.scene.Scene;
import javafx.scene.layout.GridPane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
import javafx.scene.text.Font;
import javafx.scene.text.Text;
import javafx.stage.Stage;

import java.util.Arrays;

public class B2 extends Application {
   
    long sleep = 0;

    @Override
    public void start(Stage primaryStage) throws Exception {
   
        // 初始化画布
        GridPane gridPane = new GridPane();
        gridPane.setMinSize(300, 200);
        gridPane.setAlignment(Pos.CENTER);
        gridPane.setPadding(new Insets(10));
        gridPane.setVgap(15);
        gridPane.setHgap(20);

        paintNumes(gridPane);

        // 建立线程开始计算
        Thread thread = new Thread(() -> {
   
            int[][] numes = getNumes();// 得到处理的数塔
            int max = getMax_V(gridPane, numes, 0, 0, true);// 返回计算结果
            Text text1 = new Text("最大值：" + max);// 输出到界面
            text1.setFont(Font.font(30));
            Runnable runnable = () -> {
   
                gridPane.add(text1, 2*numes.length - 1, 1 + numes.length);// 新建线程输出到界面
            };
            Platform.runLater(runnable);
        });
        thread.setDaemon(true);// 设置线程属性
        thread.start();

        primaryStage.setScene(new Scene(gridPane));
        primaryStage.show();
    }

    // 将原始数塔画出来
    private void paintNumes(GridPane gridPane) {
   
        int[][] numes = getNumes();
        int l = numes.length - 1;
        for (int i = 0; i < numes.length; i++) {
   
            int t = l--;
            for (int j = 0; j <= i; j++) {
   
                gridPane.add(getText(numes[i][j]), t, i);
                t += 2;
            }
        }
    }

    // 返回预定义的数组
    private int[][] getNumes() {
   
        int[][] numes = new int[5][5];
        int[] n = {
   9, 12, 15, 10, 6, 8, 2, 18, 9, 5, 19, 7, 10, 4, 16};
        int p = 0;
        for (int i = 0; i < 5; i++) {
   
            for (int j = 0; j <= i; j++) {
   
                numes[i][j] = n[p++];
            }
        }
        return numes;
    }
    // 测试用
    private static int[][] getNumes1() {
   
        int[][] numes = new int[5][5];
        int[] n = {
   9, 12, 15, 10, 6, 8, 2, 18, 9, 5, 19, 7, 10, 4, 16};
        int p = 0;
        for (int i = 0; i < 5; i++) {
   
            for (int j = 0; j <= i; j++) {
   
                numes[i][j] = n[p++];
            }
        }
        return numes;
    }

    // 返回一个带有指定数字k的Text标签
    private Text getText(int k) {
   
        Text text = new Text(Integer.toString(k));
        text.setFont(Font.font(30));
        text.setFill(Color.GREEN);
        return text;
    }



    /** * // 画图动态显示计算 * @param gridPane 面板 * @param nums 数塔 * @param row 行 * @param column 列 * @param biger 是否是较大值 * @return 从当前节点走到数塔底部的最大值 */
    public synchronized int getMax_V(GridPane gridPane, int[][] nums, int row, int column, boolean biger) {
   
        setColor(gridPane, nums, row, column, Color.RED);// 先画红色

        if (row == nums.length - 1) {
   // 到数塔底部
            if (!biger) {
   
                setColor(gridPane, nums, row, column, Color.GREEN);// 不是较大值用绿色
            }
            return nums[row][column];
        }

        int l = getMax(nums, row + 1, column);// 预处理左子树
        int r = getMax(nums, row + 1, column + 1);// 预处理右子树
        int max = nums[row][column] + Math.max(getMax_V(gridPane, nums, row + 1, column, l > r), getMax_V(gridPane, nums, row + 1, column + 1, r > l));
        if (!biger) {
   //不是最大值，画回绿色
            setColor(gridPane, nums, row, column, Color.GREEN);
        }

        return max;
    }

    // 通过节点位置给节点画指定颜色
    private void setColor(GridPane gridPane, int[][] nums, int row, int column, Color color) {
   
        try {
   
            sleep = 600;
            Thread.sleep(sleep);
        } catch (InterruptedException e) {
   
            e.printStackTrace();
        }
        Runnable runnable = () -> {
   
            Text text = getText(nums[row][column]);
            text.setFill(color);
            gridPane.add(text, (nums[0].length - 1) - row + column * 2, row);
        };
        Platform.runLater(runnable);
    }

    // 预处理函数得到指定节点到数塔底部的最大值
    public static int getMax(int[][] nums, int row, int column) {
   
        if (row == nums.length - 1)
            return nums[row][column];
        return nums[row][column] + Math.max(getMax(nums, row + 1, column), getMax(nums, row + 1, column + 1));
    }

    public static void main(String[] args) {
   
        launch(args);
// System.out.println(getMax(getNumes1(), 0, 0));
    }
}