4.演示汉诺塔问题:设计并实现一个求解Hanoi…
- User
4.演示汉诺塔问题:设计并实现一个求解Hanoi 塔问题的图形版程序。允许用户设置解题所使用的圆盘数。用户应当能以两种主要的方式与程序交互。一是可以在程序确认合法的情况下用鼠标将圆盘从一个塔座移到另一个塔座。二是可以用暂停/继续按钮观看解题过程的动画,并且允许用户控制动画速度。
- Assistant
以下是一个基于Python和Pygame库实现的图形版汉诺塔问题求解程序的示例:
import pygame import time # 初始化Pygame窗口 pygame.init() WIDTH, HEIGHT = 800, 600 screen = pygame.display.set_mode((WIDTH, HEIGHT)) pygame.display.set_caption("Hanoi Tower") # 设置颜色 BACKGROUND_COLOR = (255, 255, 255) TOWER_COLOR = (0, 0, 0) DISK_COLOR = (128, 128, 128) # 设置参数 tower_width = 10 tower_height = HEIGHT // 2 disk_width = 80 disk_height = 20 tower1_x = WIDTH // 4 tower2_x = WIDTH // 2 tower3_x = WIDTH * 3 // 4 tower_y = HEIGHT // 2 - tower_height // 2 # 存储塔座和圆盘状态的列表 tower1 = [] tower2 = [] tower3 = [] # 塔座和圆盘的类 class Tower: def __init__(self, x, y, width, height): self.x = x self.y = y self.width = width self.height = height def draw(self): pygame.draw.rect(screen, TOWER_COLOR, (self.x, self.y, self.width, self.height)) class Disk: def __init__(self, width, height): self.width = width self.height = height def draw(self, x, y): pygame.draw.rect(screen, DISK_COLOR, (x - self.width // 2, y, self.width, self.height)) # 创建塔座和初始的圆盘 tower1 = Tower(tower1_x, tower_y, tower_width, tower_height) for i in range(4, 0, -1): tower1.append(Disk(disk_width * i, disk_height)) # 将圆盘从一个塔座移动到另一个塔座的函数 def move_disk(source, target): disk = source.pop() target.append(disk) # 递归求解汉诺塔问题的函数 def hanoi(n, source, target, auxiliary, speed): if n > 0: hanoi(n - 1, source, auxiliary, target, speed) move_disk(source, target) draw_towers(speed) hanoi(n - 1, auxiliary, target, source, speed) # 绘制塔座和圆盘的函数 def draw_towers(speed): screen.fill(BACKGROUND_COLOR) tower1.draw() tower2.draw() tower3.draw() for i, disk in enumerate(tower1): x = tower1_x y = tower_y + tower_height - (i + 1) * disk_height disk.draw(x, y) for i, disk in enumerate(tower2): x = tower2_x y = tower_y + tower_height - (i + 1) * disk_height disk.draw(x, y) for i, disk in enumerate(tower3): x = tower3_x y = tower_y + tower_height - (i + 1) * disk_height disk.draw(x, y) pygame.display.update() pygame.time.wait(speed) # 主循环 def main(): running = True solving = False speed = 100 n = 4 # 主循环 while running: for event in pygame.event.get(): if event.type == pygame.QUIT: running = False elif event.type == pygame.KEYDOWN: if event.key == pygame.K_SPACE: if not solving: solving = True hanoi(n, tower1, tower3, tower2, speed) solving = False elif event.key == pygame.K_UP: if speed > 0: speed -= 50 elif event.key == pygame.K_DOWN: speed += 50 draw_towers(speed) # 退出 pygame.quit() if __name__ == "__main__": main()该程序创建了一个Pygame窗口,并使用塔座和圆盘类来表示和绘制汉诺塔问题的状态。用户可以使用空格键开始自动解决问题,使用上下箭头键来加速或减慢动画速度,点击窗口的关闭按钮来退出程序。程序使用递归算法来求解汉诺塔问题,并通过调整绘制速度来控制动画的流畅度。
- User
用JAVA来实现上述功能
- Assistant
以下是一个使用Java和JavaFX库实现的图形版汉诺塔问题求解程序的示例:
import javafx.animation.TranslateTransition; import javafx.application.Application; import javafx.geometry.Pos; import javafx.scene.Scene; import javafx.scene.control.Button; import javafx.scene.layout.*; import javafx.scene.paint.Color; import javafx.scene.shape.Rectangle; import javafx.stage.Stage; import javafx.util.Duration; public class HanoiTower extends Application { private final int WIDTH = 800; private final int HEIGHT = 600; private final Color BACKGROUND_COLOR = Color.WHITE; private final Color TOWER_COLOR = Color.BLACK; private final Color DISK_COLOR = Color.GRAY; private final int towerWidth = 10; private final int towerHeight = HEIGHT / 2; private final int diskWidth = 80; private final int diskHeight = 20; private VBox tower1; private VBox tower2; private VBox tower3; @Override public void start(Stage primaryStage) { primaryStage.setTitle("Hanoi Tower"); // 创建塔座和初始的圆盘 tower1 = createTower(); for (int i = 4; i >= 1; i--) { Rectangle disk = createDisk(diskWidth * i, diskHeight); tower1.getChildren().add(disk); } tower2 = createTower(); tower3 = createTower(); GridPane gridPane = new GridPane(); gridPane.setAlignment(Pos.CENTER); gridPane.setHgap(10); gridPane.setVgap(10); gridPane.add(tower1, 0, 0); gridPane.add(tower2, 1, 0); gridPane.add(tower3, 2, 0); Button solveButton = new Button("Solve"); solveButton.setOnAction(e -> solveHanoi(4, tower1, tower3, tower2, 400)); HBox buttonBox = new HBox(10); buttonBox.setAlignment(Pos.CENTER); buttonBox.getChildren().add(solveButton); VBox root = new VBox(20); root.setAlignment(Pos.CENTER); root.setBackground(new Background(new BackgroundFill(BACKGROUND_COLOR, null, null))); root.getChildren().addAll(gridPane, buttonBox); Scene scene = new Scene(root, WIDTH, HEIGHT); primaryStage.setScene(scene); primaryStage.show(); } private VBox createTower() { VBox tower = new VBox(); tower.setAlignment(Pos.BOTTOM_CENTER); tower.setPrefWidth(towerWidth); tower.setPrefHeight(towerHeight); tower.setBackground(new Background(new BackgroundFill(TOWER_COLOR, null, null))); return tower; } private Rectangle createDisk(int width, int height) { Rectangle disk = new Rectangle(width, height); disk.setFill(DISK_COLOR); return disk; } private void moveDisk(Rectangle disk, VBox source, VBox target) { TranslateTransition transition = new TranslateTransition(Duration.millis(500), disk); transition.setToY(target.getHeight() - target.getChildren().size() * diskHeight); transition.play(); transition.setOnFinished(e -> { source.getChildren().remove(disk); target.getChildren().add(disk); disk.setTranslateY(0); }); } private void solveHanoi(int n, VBox source, VBox target, VBox auxiliary, int speed) { if (n > 0) { solveHanoi(n - 1, source, auxiliary, target, speed); moveDisk((Rectangle) source.getChildren().get(source.getChildren().size() - 1), source, target); pause(speed); solveHanoi(n - 1, auxiliary, target, source, speed); } } private void pause(int duration) { try { Thread.sleep(duration); } catch (InterruptedException e) { e.printStackTrace(); } } public static void main(String[] args) { launch(args); } }该程序使用JavaFX库创建了一个窗口,并使用VBox和Rectangle类来表示和绘制汉诺塔问题的状态。用户可以点击"解决"按钮开始自动解决问题,并通过调整暂停时间来控制动画速度。程序使用递归算法来求解汉诺塔问题,并通过平移动画来移动圆盘。
- User
单源最短路算法:Disjkstra算法。允许以下方式输入一个图形:绘制图形、输入邻接矩阵、输入边及其关联的顶点
- Assistant
以下是一个使用Python实现的Dijkstra算法的示例:
import sys # 创建一个图类 class Graph: def __init__(self, vertices): self.V = vertices self.graph = [[0] * vertices for _ in range(vertices)] # 添加边 def add_edge(self, u, v, weight): self.graph[u][v] = weight self.graph[v][u] = weight # 找到未被包含在最短路径的顶点中距离源点最近的顶点 def min_distance(self, dist, spt_set): min_dist = sys.maxsize min_index = -1 for v in range(self.V): if dist[v] < min_dist and not spt_set[v]: min_dist = dist[v] min_index = v return min_index # 打印最短路径 def print_solution(self, dist): print("顶点 -> 最短距离") for v in range(self.V): print(v, "->", dist[v]) # 使用Dijkstra算法找到从源点到各个顶点的最短路径 def dijkstra(self, src): dist = [sys.maxsize] * self.V # 用于存储源点到各个顶点的最短距离 dist[src] = 0 # 源点到自身的距离为0 spt_set = [False] * self.V # 记录哪些顶点已经包含在最短路径中 for _ in range(self.V): u = self.min_distance(dist, spt_set) spt_set[u] = True for v in range(self.V): if ( self.graph[u][v] > 0 and not spt_set[v] and dist[v] > dist[u] + self.graph[u][v] ): dist[v] = dist[u] + self.graph[u][v] self.print_solution(dist) # 创建一个无权图 g = Graph(9) # 添加边 g.add_edge(0, 1, 4) g.add_edge(0, 7, 8) g.add_edge(1, 2, 8) g.add_edge(1, 7, 11) g.add_edge(2, 3, 7) g.add_edge(2, 8, 2) g.add_edge(2, 5, 4) g.add_edge(3, 4, 9) g.add_edge(3, 5, 14) g.add_edge(4, 5, 10) g.add_edge(5, 6, 2) g.add_edge(6, 7, 1) g.add_edge(6, 8, 6) g.add_edge(7, 8, 7) # 使用Dijkstra算法找到从顶点0到各个顶点的最短路径 g.dijkstra(0)在上述示例中,首先定义了一个图类,
Graph,它具有图的顶点数量和邻接矩阵。然后,该类提供了添加边、找到最短路径和打印最短路径的方法。然后,创建了一个无权图,并添加了边。最后,使用Dijkstra算法找到从源点0到各个顶点的最短路径,并打印结果。如果你想通过绘制图形或输入邻接矩阵或输入边及其关联的顶点的方式输入图形,请根据需要修改示例代码。
- User
用java实现
- Assistant
以下是使用Java实现Dijkstra算法的示例代码:
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class DijkstraAlgorithm { private static class Edge { int source; int destination; int weight; public Edge(int source, int destination, int weight) { this.source = source; this.destination = destination; this.weight = weight; } } private static class Graph { int vertices; List<Edge>[] adjacencyList; public Graph(int vertices) { this.vertices = vertices; adjacencyList = new ArrayList[vertices]; for (int i = 0; i < vertices; i++) { adjacencyList[i] = new ArrayList<>(); } } public void addEdge(int source, int destination, int weight) { Edge edge = new Edge(source, destination, weight); adjacencyList[source].add(edge); } public void dijkstra(int source) { int[] distance = new int[vertices]; boolean[] visited = new boolean[vertices]; Arrays.fill(distance, Integer.MAX_VALUE); distance[source] = 0; for (int i = 0; i < vertices - 1; i++) { int u = minDistance(distance, visited); visited[u] = true; for (Edge edge : adjacencyList[u]) { int v = edge.destination; int weight = edge.weight; if (!visited[v] && distance[u] != Integer.MAX_VALUE && distance[u] + weight < distance[v]) { distance[v] = distance[u] + weight; } } } printSolution(distance); } private int minDistance(int[] distance, boolean[] visited) { int minDist = Integer.MAX_VALUE; int minIndex = -1; for (int i = 0; i < vertices; i++) { if (!visited[i] && distance[i] < minDist) { minDist = distance[i]; minIndex = i; } } return minIndex; } private void printSolution(int[] distance) { System.out.println("Vertex -> Shortest Distance"); for (int i = 0; i < vertices; i++) { System.out.println(i + " -> " + distance[i]); } } } public static void main(String[] args) { int vertices = 9; Graph graph = new Graph(vertices); graph.addEdge(0, 1, 4); graph.addEdge(0, 7, 8); graph.addEdge(1, 2, 8); graph.addEdge(1, 7, 11); graph.addEdge(2, 3, 7); graph.addEdge(2, 8, 2); graph.addEdge(2, 5, 4); graph.addEdge(3, 4, 9); graph.addEdge(3, 5, 14); graph.addEdge(4, 5, 10); graph.addEdge(5, 6, 2); graph.addEdge(6, 7, 1); graph.addEdge(6, 8, 6); graph.addEdge(7, 8, 7); graph.dijkstra(0); } }在上述代码中,我们定义了两个内部类:
Edge表示图的边,Graph表示图的数据结构和算法。其中,Graph类具有顶点数、邻接列表以及添加边和Dijkstra算法的方法。在addEdge方法中,我们添加了边。然后,在dijkstra方法中,我们使用Dijkstra算法找到从起点到其他顶点的最短路径,并打印结果。你可以根据需要修改示例代码,以便通过其他方式输入图形。