当前位置: 首页 > news >正文

华为OD机试2024年真题(基站维修工程师)

基站维修工程师(200分)

小王是一名基站维护工程师,负责某区域的基站维护。
某地方有n个基站(1<n<10),已知各基站之间的距离s(0<s<500),并且基站x到基站y的距离,与基站y到基站x的距离并不一定会相同。

小王从基站1出发,途径每个基站1次,然后返回基站1,需要请你为他选择一条距离最短的路线。

>>输入描述

站点数n和各站点之间的距离(均为整数)。如:

3 {站点数}
0 2 1 {站点1到各站点的路程)
1 0 2 (站点2到各站点的路程}
2 1 0 {站点3到各站点的路程}

>>输出描述

最短路程的数值

>>示例1

输入

3
0 2 1
1 0 2
2 1 0

输出

3

思路: 

目标是解决典型的旅行商问题(TSP, Travelling Salesman Problem),即在一个给定的城市网络中,找到一条从起点城市出发,经过每个城市一次并最终返回起点的路径,使得路径的总距离最短。算法使用了递归(深度优先搜索)结合状态标记来遍历所有可能的路径,并通过回溯法不断比较最短路径。
输入:给定一个 size x size 的二维数组 arr,其中 arr[i][j] 表示城市 i 到城市 j 的距离。
输出:求解从城市0出发,经过每个城市一次并返回的最短路径长度。

 

步骤:
数据输入:读取城市数 size 和城市之间的距离矩阵 arr。
递归函数 recur:递归尝试从一个城市访问未访问过的下一个城市,记录当前路径长度,并使用状态数组 st 标记某个城市是否已经访问过。
状态回溯:递归探索完某条路径后,返回上一步,尝试其他未访问过的城市,最终比较得到最短路径。
结果输出:输出所有路径中的最小总距离。

代码段如下:

package com.rich.huawei.od_test;import java.util.Scanner;/*** @description* @Title Test01* @Author tang rui qi* @Date 2024/10/14 5:17*/
public class Test03 {static int res; // 用于保存最短路径的总距离// 递归函数// u: 当前访问的第几个城市// pre: 上一个访问的城市编号// temRes: 当前路径的总距离// size: 城市的总数// arr: 城市之间的距离矩阵// st: 访问状态数组,标记某个城市是否被访问过static void recur(int u, int pre, int temRes, int size, int[][] arr, boolean[] st) {// 如果已经访问完所有城市并回到起点城市if (u == size - 1) {// 将当前路径的总距离与最小距离进行比较,更新最小距离res = Math.min(res, temRes + arr[pre][0]);return;}// 遍历每个城市,寻找下一个未访问过的城市for (int i = 1; i < size; ++i) {if (st[i]) { // 如果该城市已被访问,则跳过continue;}st[i] = true; // 标记该城市为已访问// 递归访问下一个城市,并累加当前路径的距离recur(u + 1, i, temRes + arr[pre][i], size, arr, st);st[i] = false; // 回溯时将该城市重置为未访问状态}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int size = cin.nextInt(); // 读取城市的总数res = 0x3f3f3f3f; // 初始化最短路径为一个很大的值int[][] arr = new int[size][size]; // 城市之间的距离矩阵boolean[] st = new boolean[size]; // 访问状态数组// 读取距离矩阵的值for (int x = 0; x < size; ++x)for (int y = 0; y < size; ++y) arr[x][y] = cin.nextInt();// 从城市0开始递归搜索recur(0, 0, 0, size, arr, st);// 输出最短路径的总距离System.out.println(res);}}


http://www.mrgr.cn/news/53500.html

相关文章:

  • 网页打印——魔都千丝冥缘——未来之窗行业应用跨平台架构
  • 滑动窗口-无重复字符的最长字串
  • vscode open editors 打开
  • 写论文节省论文页面空间的办法
  • latex常见长度单位
  • 第一百零七周周报
  • 如何保护您的服务器免受 POODLE SSLv3 漏洞的影响
  • wpf grid 的用法
  • WordPress任推帮网盘拉新数据统计插件
  • Miniconda管理虚拟环境【Python环境配置】
  • HDU RealPhobia
  • Spring实现3种异步流式接口,解决接口超时烦恼
  • Apple Vision Pro市场表现分析:IDC最新数据揭示的真相
  • 郑州大学第一附属医院许建中教授专家团队会诊室揭牌仪式在郑州长江中医院成功举行
  • 华为杯”第十三届中国研究生数学建模竞赛-E题:基于多目标规划和智能优化算法的粮食最低收购价政策研究(中)
  • LLM 的推理优化技术纵览
  • C++类的构造函数
  • 如何安装MySql
  • JavaWeb 23.NPM配置和使用
  • 【数据分享】中国历史学年鉴(1979-2001)