[Ruby] 콜라츠 추측

콜라츠 추측 이란 

http://ko.wikipedia.org/wiki/%EC%BD%9C%EB%9D%BC%EC%B8%A0_%EC%B6%94%EC%B8%A1

1. 루비를 설치

2. 터미널에서 저장된 파일위치에서 디버깅

ruby untitled.rb 

(파일명 : untitled.rb)

확장자는 rb

untitled.rb

---

require 'benchmark'

# def main

#      n=0

#      if n<1

#            puts "error"

#      elsif n>1

#           if n%2==0

#                n/2

#           else

#                n*3+1

#           end

#      end

# end

# main()

# n이 짝수: n / 2

# n이 홀수: 3 * n + 1

# n이 1이면 반환

# def cycle(n)

#   be = []

#   be << n

#   if n % 2 == 0

#     be << n / 2

#   end

# end

def assert(actual, expected)

  if(actual != expected)

    puts "\n"

    puts "failed. expected = #{expected} but actual #{actual}"

  else

    print "."

    #puts actual

  end

end

def cycle(n)

  be = []

  be << n

  while n > 1

    if n % 2 == 0

      n=n/2

      be << n

    elsif

      n = 3*n+1

      be << n

    end

  end

  return be

end

def loopcycle(min, max)

  maxlen = []

  (min..max).each do |i|

    maxlen << cycle(i).length 

  end

  maxlen.max

end

def cached_cycle(n)

  be = []

  be << n

  cache = {}

  while n > 1

    if n % 2 == 0

      if cache[n] == nil

        n=n/2

        be << n

      elsif

        be.length += cache[n]

        n = 1

      end

    elsif

      if cache[n] == nil

        n = 3*n+1

        be << n

      elsif

        be.length += cache[n]

        n = 1

      end

    end

  end

  cache[n] = be.length

  return be.length

end

def cached_loopcycle(min, max)

  maxlen = []

  cache = {}

  (min..max).each do |i|

    n = i

    cycle = 1

    while n > 1

      cached = cache[n]

      if cached

        cycle += cached - 1

        break

      end

     

      cycle += 1

      n = algo(n)

    end

    maxlen << cycle

    cache[i] = cycle

  end

  maxlen.max

end

def algo(n)

  if n % 2 == 0

    n = n / 2

  elsif

    n = 3 * n + 1

  end

  n

end

def nocache_loopcycle(min, max)

  maxlen = []

  (min..max).each do |i|

    n = i

    cycle = 1

    while n > 1

      if cycle +=  1

        if n % 2 == 0

          n = n/2

        elsif

          n = 3 * n + 1

        end

      end

    end

    maxlen << cycle

  end

  print "#{maxlen.max} "

  maxlen.max

end

Benchmark.bm do |benchmark|

  # Not Cache

  benchmark.report { nocache_loopcycle(1, 100000) }

  # Cache

  benchmark.report { cached_loopcycle(1, 100000) }

end

assert(cached_loopcycle(2, 5), [3, 10, 5, 16, 8, 4, 2, 1].length)

assert(cached_loopcycle(2, 5), 8)

assert(cycle(1), [1])

assert(cycle(2), [2, 1])

assert(cycle(3), [3, 10, 5, 16, 8, 4, 2, 1])

assert(cycle(4), [4, 2, 1])

assert(cycle(5), [5, 16, 8, 4, 2, 1])

assert(cycle(8), [8, 4, 2, 1])

puts "\n" 

---

모범답안 : https://gist.github.com/keelerm84/5602815