3n+1 문제

다음 연습: 여행 비용를 공평하게 나눠라

 

루비는 나름 유창한 편이지만, Factor와 Erlang은 그렇지 못하다. 조금이나마 익숙해지고 싶어서, 간단한 문제를 풀어보며 연습을 해보기로 했다.

 

문제

http://online-judge.uva.es/p/v1/100.html

n이 짝수이면 n/2를, 홀수이면 3n+1을 구하는 계산을 결과가 1이 될 때까지 반복하는 간단한 문제다.

주어진 구간에서 가장 1이 되기까지 가장 긴 시퀀스를 만드는 값을 찾는다.

 

풀이

그림_4.png

  1. class Fixnum
      def next_number
        even? ? self / 2 :
          self * 3 + 1
      end
    end

    class Solver
      def collatz_from(num)
        num == 1 ? [1] :
          [num] + collatz_from(num.next_number)
      end
      memoize :collatz_from

      def find_length(num)
        collatz_from(num).length
      end

      def max_length(from, to)
        (from..to).to_a.map{|n| find_length(n)}.max
      end 
    end

 

 

logo.png

  1. : next-number ( x -- y )
    dup even? [ 2 / ] [ 3 * 1 + ] if ;

    : collatz ( x -- seq )
    dup [ next-number dup 1 > ] [ dup ] [ ] produce
    swap suffix swap prefix ;

    : collatz-length ( x -- y )
    collatz length ;

    : from-to ( x y -- seq )
    over 1- - >array swap [ + ] curry map ;

    : max-length ( x y -- z )
    from-to [ collatz-length ] map supremum ;

 

 

erlang.gif

  1. next_number(X) when X rem 2 == 0 -> X div 2;
    next_number(X) -> X*3+1.

    collatz(N) when is_integer(N) -> collatz([N]);
    collatz([]) -> [];
    collatz([H|L]) when H == 1 -> lists:reverse([H|L]);
    collatz([H|L]) -> collatz([next_number(H)] ++ [H|L]).

    collatz_length(N) -> length(collatz(N)).

    max_length(From, To) ->
        lists:max([collatz_length(X) || X <- lists:seq(From, To)]).

 

 

후기