蟻本の三角形をrubyで書いた

三角形

n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。

一番大きな辺が他の2つの長さの合計よりも長かったらいけないのですが、

• 辺を大きい順か小さい順に並べて、大きい方から条件を満たすものを探せばいいのでは?
• 大きい方から辺を3つ探していったとき、「他の2つの長さの合計が一番大きな辺より大きい」を満たす、一番大きな辺より短い2本の辺って常に一番大きい辺の次とその次に大きい辺なのでは?
  • 未検証... orz

と思って書いた。反例見つかったら修正します。

n = 5
a = [2, 3, 4, 5, 10]
a.sort! # 昇順にソート

if n < 3
  puts "the number of bars is less than 3."
  puts 0
  return
end

def make_triangle(n, a)
  longest_bar_index  = n - 1
  middle_bar_index   = n - 2
  shortest_bar_index = n - 3

  while is_too_long_longest_bar?(longest_bar_index, middle_bar_index, shortest_bar_index, a) do
    longest_bar_index -= 1
    middle_bar_index -= 1
    shortest_bar_index -= 1
    if shortest_bar_index < 0
      puts "cannot make any triangle in this set."
      return 0
    end
  end

  return "#{a[longest_bar_index] + a[middle_bar_index] + a[shortest_bar_index]}(#{a[longest_bar_index]}, #{a[middle_bar_index]}, #{a[shortest_bar_index]} の3本を選んだ時)" unless shortest_bar_index < 0
end

def is_too_long_longest_bar?(longest_bar_index, middle_bar_index, shortest_bar_index, a)
  a[longest_bar_index] >= (a[middle_bar_index] + a[shortest_bar_index])
end

puts make_triangle(n, a)