求一道用算法解决的题目 JAVA ,C++,python都可以
来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/06/28 13:15:44
求一道用算法解决的题目 JAVA ,C++,python都可以
文明III
小明正在玩《文明III》游戏,现在他有n个洲际导弹(简称ICBM)。他需要在最短的
时间内,用这n个ICBM摧毁敌方n个目标(1个ICBM只能摧毁1个目标)。n个ICBM和目标的位置不一定相同,小明觉得给每个ICBM确定目标是一件很麻烦的事情。请你编程帮助小明给每个ICBM确定目标,使每个ICBM到其目标的距离之和最小。
输入:
第一行:n (n<=12)
第2到n+1行:x,y
说明:每一行包含一个坐标(x,y),表示一个ICBM,-10000 第n+2到2n+1行:x,y
说明:每一行包含一个坐标(x,y),表示一个目标,-10000 输出:
仅一行:min
说明:min是每个ICBM到其目标距离之和的最小值。结果保留3位小数。
样例:
B.in:
2
1 1
-1 -1
-2 -2
2 2
B.out:
2.828
文明III
小明正在玩《文明III》游戏,现在他有n个洲际导弹(简称ICBM)。他需要在最短的
时间内,用这n个ICBM摧毁敌方n个目标(1个ICBM只能摧毁1个目标)。n个ICBM和目标的位置不一定相同,小明觉得给每个ICBM确定目标是一件很麻烦的事情。请你编程帮助小明给每个ICBM确定目标,使每个ICBM到其目标的距离之和最小。
输入:
第一行:n (n<=12)
第2到n+1行:x,y
说明:每一行包含一个坐标(x,y),表示一个ICBM,-10000
说明:每一行包含一个坐标(x,y),表示一个目标,-10000
仅一行:min
说明:min是每个ICBM到其目标距离之和的最小值。结果保留3位小数。
样例:
B.in:
2
1 1
-1 -1
-2 -2
2 2
B.out:
2.828
![求一道用算法解决的题目 JAVA ,C++,python都可以](/uploads/image/z/19996440-24-0.jpg?t=%E6%B1%82%E4%B8%80%E9%81%93%E7%94%A8%E7%AE%97%E6%B3%95%E8%A7%A3%E5%86%B3%E7%9A%84%E9%A2%98%E7%9B%AE+JAVA+%2CC%2B%2B%2Cpython%E9%83%BD%E5%8F%AF%E4%BB%A5)
import math
d=[]
x=[]
y=[]
n=0
fpr=open("data.txt")
for line in fpr:
n+=1
if n==1:
num=int(line)
else:
a,b=line.split()
x.append(int(a))
y.append(int(b))
fpr.close()
k=-1
for i in xrange(num):
for j in xrange(num,2*num):
k+=1
dis=math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
d.append(dis)
min_dis=10000000
sum_dis=0
for i in xrange(k):
for j in xrange(i,i+num):
sum_dis+=d[j]
if min_dis>sum_dis:
min_dis=sum_dis
sum_dis=0
fpw=open("data_out.txt","w+")
fpw.write("%-12.3f"%min_dis)
print("%-12.3f"%min_dis)
fpw.close()
#用python写的,测试成功,你看下
d=[]
x=[]
y=[]
n=0
fpr=open("data.txt")
for line in fpr:
n+=1
if n==1:
num=int(line)
else:
a,b=line.split()
x.append(int(a))
y.append(int(b))
fpr.close()
k=-1
for i in xrange(num):
for j in xrange(num,2*num):
k+=1
dis=math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
d.append(dis)
min_dis=10000000
sum_dis=0
for i in xrange(k):
for j in xrange(i,i+num):
sum_dis+=d[j]
if min_dis>sum_dis:
min_dis=sum_dis
sum_dis=0
fpw=open("data_out.txt","w+")
fpw.write("%-12.3f"%min_dis)
print("%-12.3f"%min_dis)
fpw.close()
#用python写的,测试成功,你看下