while True:

問題15

3 次元空間の N 個の点を考える.これらの位置を座標(x, y, z)の形で読み込み,2 点間の距離をすべて計算せよ. さらに,距離の小さい順に並べ替えて,座標とともに出力せよ.ただし,𝑁 ≤ 10としてよい。

難易度 ★★★★☆

やや発展的な問題です。難しい点は、それぞれの点の組み合わせを計算する必要があること、距離をソート(並び替え)した後に、座標も出力する必要があること。この2つです。 簡単な方針としては、2つの組み合わせは、i=1~Nのループの中で、j=i~Nのループをすることで取り出せるということ。 また、ソートする際に、それぞれの距離のインデックス(場所)から、それぞれの座標もソートすること。 それらを実装できれば、解決できる問題です。ソートアルゴリズムに関しては、何も指定がありませんが、平均計算量を考えないのであればバブルソートが実装しやすいと思います。
program question15
	implicit none
	integer :: n, combinations, i, j, count
	real, allocatable :: pos(:, :), comb_a(:, :), comb_b(:, :), distance(:)
	real :: dist, temp, temps(3)

	print *, "input n:"
	read *, n

	combinations = n * (n - 1) / 2
	allocate(pos(3, n), comb_a(3, combinations), comb_b(3, combinations), distance(combinations))

	print *, "input (x, y, z)s:"
	read *, pos

	count = 1
	do i = 1, (n - 1)
		do j = (i + 1), n
			dist = ((pos(1, i) - pos(1, j)) ** 2 + (pos(2, i) - pos(2, j)) ** 2 + (pos(3, i) - pos(3, j)) ** 2) ** 0.5
			distance(count) = dist
			comb_a(:, count) = pos(:, i)
			comb_b(:, count) = pos(:, j)
			count = count + 1
		end do
	end do

	! Bubble sort

	do i = 1, (combinations - 1)
		do j = (i + 1), combinations
			if(distance(i) .gt. distance(j))then
				temp = distance(i)
				distance(i) = distance(j)
				distance(j) = temp

				temps = comb_a(:, i)
				comb_a(:, i) = comb_a(:, j)
				comb_a(:, j) = temps

				temps = comb_b(:, i)
				comb_b(:, i) = comb_b(:, j)
				comb_b(:, j) = temps
			end if
		end do
	end do

	do i = 1, combinations
		print *, comb_a(:, i), "and", comb_b(:, i), "is", distance(i)
	end do

end program question15
ページのトップへ戻る