2.路由器资源用量预测
题目描述
路由器的某资源利用率与多个运行特征强相关：协议连接数(单位：个)、转发数据包速率(单位：Mpps)、内存占用率(单位：%)。为了精准预测不同负载下的路由器资源利用率，保障网络稳定运行，请实现批量梯度下降法(BGD)来训练资源预测线性回归模型的参数。
资源预测模型：
y = b + w1 * x1 + w2 * x2 + w3 * x3 (b为偏置项，x1，x2，x3，w1，w2，w3为特征权重)
损失函数：均方误差(MSE)
J = 1/(2m) * sum((y_pred - y)^2) (m为样本数)
梯度更新规则：
w = w - alpha * (1/m) * sum((y_pred - y) * x) (偏置项b对应x0=1，alpha为学习率)
迭代规则：初始权重(含偏置)全为0，迭代固定N次后停止，无需判断收敛。
为了提高收敛速度，采用特征归一化进行训练，并在训练完成后进行权重还原：
特征归一化：对每个特征维度 x_norm = (x - x_min) / (x_max - x_min)，其中 x_min 为该特征在所有样本中的最小值，x_max 为该特征在所有样本中的最大值，若特征无波动，则归一化后的值为0。
特征权重还原：w_real = w / (x_max - x_min)，其中 w 为迭代后的权重，若 x_max - x_min 为0，则 w_real 取0。
偏置项权重还原：b_real = b - sum(w_real * x_min)，b 为迭代后偏置项的权重。
输入描述
第一行：整数 m (样本数量，m > 0)
第二行：整数 n (迭代次数，n > 0)
第三行：浮点数 alpha (学习率，alpha > 0，保留2位小数)
后续 m 行：每行4个整数，依次为 x1 (协议连接数)、x2 (转发数据包速率)、x3 (内存占用率)、y (资源用量)
输出描述
一行，4个浮点数，依次为还原后的 b，w1，w2，w3，结果保留2位小数，银行家舍入，以一个空格分隔，前后无冗余空格。
样例1
输入
3 100 0.10 100 200 150 6000 200 800 600 7500 300 70 60 6500
输出
4394.59 6.82 1.20 1.55
解题思路
本题是一个典型的多变量线性回归问题，要求使用批量梯度下降(BGD)训练模型参数，并结合特征归一化与参数还原。
由于各特征取值范围差异较大，需要先对每一维做极值归一化。若某一维没有变化，则该维归一化后全部为0。
在归一化后的数据上训练模型，初始化所有参数为0，每轮迭代执行计算误差和梯度更新参数。
最后，把归一化空间下的参数还原到原始特征空间，特别要注意分母为0的情况，直接认定特征权值为0即可。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 题目一：路由器资源用量预测
import sys
import numpy as np
def update_weights_with_bgd(training_data, total_iterations, learning_rate):
# 将输入数据转成numpy数组方便运算
data_array = np.array(training_data, dtype=float)
# 提取特征列和目标值列
features = data_array[:, :3]
labels = data_array[:, 3]
# 获取每一列的最大值最小值以及范围
min_feature_vals = features.min(axis=0)
max_feature_vals = features.max(axis=0)
feature_ranges = max_feature_vals - min_feature_vals
# 对特征进行归一化处理，处理除零异常
normalized_features = np.zeros_like(features, dtype=float)
for col in range(3):
if feature_ranges[col] != 0:
normalized_features[:, col] = (features[:, col] - min_feature_vals[col]) / feature_ranges[col]
# 初始化权重参数数组，索引0为偏置项，1到3为特征权重
model_weights = np.zeros(4, dtype=float)
sample_count = len(labels)
# 进行指定次数的迭代更新
for _ in range(total_iterations):
# 计算所有的预测值
predictions = model_weights[0] + normalized_features @ model_weights[1:]
errors = predictions - labels
# 计算对应的偏置项梯度和权重梯度
bias_gradient = errors.mean()
weight_gradients = (normalized_features.T @ errors) / sample_count
# 使用学习率更新模型参数
model_weights[0] -= learning_rate * bias_gradient
model_weights[1:] -= learning_rate * weight_gradients
# 还原到原始空间的权重
restored_weights = np.zeros(4, dtype=float)
for col in range(3):
if feature_ranges[col] != 0:
restored_weights[col + 1] = model_weights[col + 1] / feature_ranges[col]
else:
restored_weights[col + 1] = 0.0
# 还原对应的偏置项
restored_weights[0] = model_weights[0] - np.sum(restored_weights[1:] * min_feature_vals)
return restored_weights
def main_process():
input_lines = sys.stdin.read().strip().splitlines()
if not input_lines:
return
sample_size = int(input_lines[0].strip())
total_iters = int(input_lines[1].strip())
lr = float(input_lines[2].strip())
dataset = []
for line_idx in range(3, 3 + sample_size):
row_data = list(map(float, input_lines[line_idx].split()))
dataset.append(row_data)
final_params = update_weights_with_bgd(dataset, total_iters, lr)
# 格式化输出为最终结果
print(f"{final_params[0]:.2f} {final_params[1]:.2f} {final_params[2]:.2f} {final_params[3]:.2f}")
if __name__ == "__main__":
main_process()
3.快递员极速配送挑战
题目描述
某快递员负责一个片区的快递配送业务。假设他手头有 n 个快递包裹需要派送，每个包裹对应一个具体的收货坐标(x,y)(单位：公里)。
为了提高效率，公司要求快递员先利用聚类算法将这 n 个包裹自动划分为 k 个簇(代表 k 个社区)，快递员只需要将快递送到社区中心即可。
快递员从起始位置出发，按照每个社区中心与起点之间的距离由近到远排序，依次送完所有社区的快递，最后返回起始位置。已知快递员的平均行驶速度为 speed km/h。快递员初始坐标为(0,0)。
请编写程序，计算完成所有配送并返回起点所需的总时间(单位：秒，向下取整)。
K均值聚类计算步骤：
种子点初始化：将所有点按到起点的距离从小到大排序，如果距离相同的点，按照输入坐标点的先后顺序从小到大排序。选择排序后的前 k 个点作为初始聚类中心。
迭代优化：将每个点分配到距离最近的聚类中心聚类。重新计算每个聚类的中心点，移动聚类中心。
收敛判断：如果所有聚类中心的移动距离之和小于 0.0001，则停止迭代。如果达到了预设的最大迭代轮次，也停止迭代。否则返回第二步继续进行迭代优化。
输入描述
第一行输入 3 个由空格分隔的整数，分别为 k(社区个数)、n(快递包裹总数)、speed(快递员平均行驶速度，单位 km/h)。
接下来的 n 行分别表示每个包裹的 x 和 y 坐标(单位：公里)，用空格分割。
输出描述
输出快递员送完所有快递所需的时间，保留整数，向下取整，单位 s。
样例1
输入
3 10 301.2 1.51.8 1.25.0 5.25.5 4.84.9 5.5-2.0 3.0-2.5 3.5-1.8 2.81.5 1.85.2 5.0
输出
2502
解题思路
本题核心分为两部分：聚类计算加上最终路径距离计算。
首先实现K算法对所有包裹进行聚类。初始化时，按点到原点距离升序排序，取前 k 个点作为初始聚类中心。
接下来多轮迭代优化，每个点分配到最近的中心，对每个簇重新计算中心。若某簇无点，则保持原中心不变。
最后如果所有中心移动距离之和足够小或达到最大迭代次数，停止迭代。
得到最终聚类中心后，按中心到原点欧氏距离升序排序，按照排序后的顺序依次连接距离计算出全部路径。结合速度大小算出具体折合时间。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 题目二：快递员极速配送挑战
import sys
import math
import numpy as np
def calculate_euclidean_distance(point_a, point_b):
# 辅助函数：计算两点直接的欧式距离
difference = point_a - point_b
return math.sqrt(difference[0] * difference[0] + difference[1] * difference[1])
def execute_kmeans_clustering(data_points, target_k, max_loops=50, tolerance_threshold=1e-4):
num_points = len(data_points)
actual_k = min(target_k, num_points)
# 计算距离原点的大小并排序，找到初始种子点
ordered_indices = sorted(range(num_points), key=lambda idx: (data_points[idx][0] ** 2 + data_points[idx][1] ** 2, idx))
cluster_centers = data_points[ordered_indices[:actual_k]].copy()
cluster_assignments = np.zeros(num_points, dtype=int)
for _ in range(max_loops):
previous_centers = cluster_centers.copy()
# 将每个点分配给最近的中心
for point_idx in range(num_points):
closest_center_idx = 0
min_dist = float('inf')
for center_idx in range(actual_k):
dist = calculate_euclidean_distance(data_points[point_idx], cluster_centers[center_idx])
if dist < min_dist:
min_dist = dist
closest_center_idx = center_idx
cluster_assignments[point_idx] = closest_center_idx
# 根据新的分配计算新的族中心点
updated_centers = cluster_centers.copy()
for center_idx in range(actual_k):
points_in_cluster = data_points[cluster_assignments == center_idx]
if len(points_in_cluster) > 0:
updated_centers[center_idx] = points_in_cluster.mean(axis=0)
cluster_centers = updated_centers
# 考察移动距离是否满足结束规则
total_movement = 0.0
for center_idx in range(actual_k):
total_movement += calculate_euclidean_distance(previous_centers[center_idx], cluster_centers[center_idx])
if total_movement < tolerance_threshold:
break
return cluster_centers
def calculate_delivery_time(target_k, num_points, moving_speed, data_points):
# 执行聚类算法搜寻所有的中心
found_centers = execute_kmeans_clustering(data_points, target_k)
# 按照原点距离升序以访问社区
sorted_centers = sorted(found_centers, key=lambda c: c[0] * c[0] + c[1] * c[1])
start_origin = np.array([0.0, 0.0])
total_travel_distance = 0.0
current_location = start_origin
# 计算累计历程
for center in sorted_centers:
total_travel_distance += calculate_euclidean_distance(current_location, center)
current_location = center
total_travel_distance += calculate_euclidean_distance(current_location, start_origin)
# 时间转换为秒，随后向下取整
total_duration_seconds = math.floor(total_travel_distance * 3600.0 / moving_speed)
return total_duration_seconds
def main_execution():
raw_input_data = sys.stdin.read().strip().split()
if not raw_input_data:
return
target_k = int(raw_input_data[0])
num_points = int(raw_input_data[1])
moving_speed = int(raw_input_data[2])
coordinate_values = list(map(float, raw_input_data[3:]))
coords_list = []
for idx_step in range(0, 2 * num_points, 2):
coords_list.append([coordinate_values[idx_step], coordinate_values[idx_step + 1]])
points_array = np.array(coords_list, dtype=float)
final_time = calculate_delivery_time(target_k, num_points, moving_speed, points_array)
print(final_time)
if __name__ == "__main__":
main_execution()
10个月宝宝每天需要喝多少奶粉？
