#問題
棒の長さが3つ以上,複数値配列に与えられる.
その中から3本選び三角形を作成する.
作成した三角形のうち,最も長い周長を出力する.
三角形が作れる条件は
最も長い棒の長さ<他の2本の棒の長さ
##考え方1
全ての選び方を試して最も長いものを出力する.
len=[2,3,4,5,10]
n=len.length
ans = "三角形は作れません"
#全ての数字の選び方を試す
for i in 0..n do
for j in i+1..n do
for k in j+1..n do
element =[len[i],len[j],len[k]].map(&:to_i)
#3角形が作れる条件 最も長い棒の長さ<他の2本の棒の長さ
circumference = element.inject(:+)
max = element.max
rest = circumference-max
if max < rest
ans = circumference
end
end
end
end
puts ans
余談
上記のプログラムは配列の合計値を返すメソッドにinjectメソッドを用いているが,
ここをreduceにすると処理速度が若干速くなる.
reduceとinjectの違い
計測方法はpaiza.io内でbenchmarkを用いて計測した.
require 'benchmark'
result = Benchmark.realtime do
# 処理
end
puts " #{result}s"
##考え方2
周長が最も長い三角形は,なるべく長い棒たちを使った三角形である.
なので,配列を降順にソートし長い棒から順に3本使っていく.
一番長い棒a[1]
,次に長い棒a[2]
,その次に長い棒a[3]
とする.
a[2]
とa[3]
の合計が一番長い棒a[1]
よりも短い場合,
残りの棒を使ってもこれより短いので,次の場合を試す.
a[2]
を一番長い棒として同様に進めていく.
len=[2,3,4,5,10]
circumference = "三角形は作れません"
#降順にソート
element = len.sort {|a, b| b.to_i <=> a.to_i }
#3本ずつ使う
for i in 0..element.length-2 do
if element[i].to_i<element[i+1].to_i+element[i+2].to_i
circumference = element[i]+element[i+1]+element[i+2]
break #長いものから順にやってるためcircumferenceが更新された段階で抜ける
end
end
puts circumference
##考え方3
三角形の成立条件の見方を変える.
三角形が成立するとき,
一番長い棒a[1],次に長い棒a[2],その次に長い棒a[3],三角形の周長をCとする.
他の2辺の合計と最長の辺との差をdとすると
(a[2]+a[3])-a[1] = d
なので他の2辺の合計は
a[2]+a[3]=a[1]+d
式1
と表せる.
周長は
C=a[1]+a[2]+a[3]
と表せるので,式1を代入すると
C=a[1]+a[1]+d
C=2a[1]+d
と表せる.
これより三角形が成立する時
周長は三角形のうちの最大長の2倍よりも大きいことがわかる.
これをコードに起こす