蟻本の1-6の続き

のーみそこねこね。

• 衝突して折り返していく -> 蟻を区別しなければ、蟻全体の動きとしては、そのまま進んでいく状態と一緒
  • 最短 -> それぞれの位置の蟻が最短で着く方法
  • 最長 -> それぞれの位置の蟻が最長で着く方法
• 4枚のくじを引いた時、4枚の合計値がmになるか
  • 2枚のくじを引いた時(この組み合わせは2重ループで表現 -> n²)、残りの2枚を引いてこれとの合計値がmになるような値があるか
  • 残りの2枚を引いて合計値がmになるような値この探索は
    • 残りの2枚については、残りの2枚を引いた値の取りうる組み合わせを列挙してその中から(m-最初の2枚)になるものを探す
      • この探す方法は2分探索(binary search) log(n)
  • O(n)に耐えうる必要のある値を入れて必要に応じて変えていくっぽい

2分探索雑に書いた。

n = 4
a = [2, 3, 4, 5, 10]

def binary_search(target, data)
  range_min = 0
  range_max = data.size
  while range_max - range_min >= 1
    i = ((range_max + range_min)/2).to_i
    if (data[i] == target)
      return true
    elsif data[i] < target
      range_min = i + 1
    else
      range_max = i
    end
  end
  return false
end

if binary_search(n, a)
  puts "found"
else
  puts "not_found"
end