3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

三角形ができるかどうか判定する

Last updated at Posted at 2016-09-01

#問題
棒の長さが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倍よりも大きいことがわかる.
これをコードに起こす

3
2
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?