04

Task

Exercise 5

次の再帰的定義に従った計算を再帰関数として書き動かせ。 また、典型的な実行の様子を表す、図 2 のような図を描いてみよ。

a. 階乗の計算。

$$ f act(n) = \begin{cases} 1 (n = 0) \\ n × f act(n − 1) (otherwise) \end{cases} $$

b. フィボナッチ数。

$$ f ib(n) = \begin{cases} 1 (n = 0 \text{ or } n = 1) \\ f ib(n − 1) + f ib(n − 2) \end{cases} $$

c. 組み合わせの数の計算。

$$ comb(n, r) = \begin{cases} 1 (r = 0 \text{ or } r = n)\\ comb(n − 1, r) + comb(n − 1, r − 1) (otherwise) \end{cases} $$ d. 正の整数 n の 2 進表現。7

$$ binary(n) = \begin{cases} “0” (n = 0) \\ “1” (n = 1) \\ binary(n ÷ 2) + “0” (n が 2 以上の偶数) \\ binary(n ÷ 2) + “1” (n が 2 以上の奇数) \end{cases} $$

Exercise 9

再帰を利用して自分の興味のあるプログラムを作りなさい。

Program, execution and description

#1 #2 つづきなので、お手数ですが #1 #2 をご確認頂けますと幸いです。

前回作成した Sym classについて、 >> << 関数を再定義することで、 再帰など、より柔軟な計算式を記述できるような機能追加を実施しました。

今回再定義した << 演算子は、 @n変数を更新した、新しい Sym object を返します。 新たに objectを返すことで、 @n の代入自体も関数として登録できるようになりました。

また前回同様に、 <=> 演算子から、値を代入するようになっています。 これらから、a ~ dの演習のコードは以下のようになりました。

a, b, c, d = (0..3).map do Sym.new end

a <=> ->n{n <= 0? 1: n * (a << n - 1).to_i}
b <=> ->n{n <= 1? 1: (b << (n - 2)).to_i + (b << (n - 1)).to_i}
c <=> ->_{_[1] <= 1 ? _[0]: (c << [_[0] - 1, _[1] - 1]).to_i * _[0] / _[1]}
d <=> ->n{n <= 1? n.to_s: (d << (n / 2)).to_i.to_s + (n % 2 == 0? "0": + "1")}

puts " n \t| a \t\t| b \t\t| c1\t\t| c2\t\t| c3\t\t| c4\t\t| d"
puts " :-\t| :-\t\t| :-\t\t| :-\t\t| :-\t\t| :-\t\t| :-\t\t| :-"
(0..9).map do |n|
        puts    " #{n}\t|"+
                " #{n}! = #{a << n}\t|" +
                " fib #{n} = #{b << n}\t|" +
                " #{n}C1 = #{c << [n, 1]}\t|" +
                " #{n}C2 = #{c << [n, 2]}\t|" +
                " #{n}C3 = #{c << [n, 3]}\t|" +
                " #{n}C4 = #{c << [n, 4]}\t|" +
                " #{d << n}"
end

演習9については、これらで用いている Sym class を作成しました。 Sym class のコードについては最後に記載しました。

About task

実行結果は以下のようになります。

Consideration

再帰的に自分を参照する方法として、 関数を <=> 演算子で登録する方法を思いつきました。 @n の値は最後に適応したかったので、<< >> 関数では、新たに Sym object を返すことで実装しました。

仕組みとしては、実際の値 @v と 引数のような @n の変数をもたせることで、 最終的な計算を実行する @v[@n] で引数のように値を参照できるようにしました。

class Sym
        def initialize(init = 0, args = 0)
                @v = init
                @n = args
                @_ = ->(v = @v, n = @n){Sym.new(v, n)}
        end
        def to_f() (@v.is_a? Numeric) ? @v: @v[@n] end
        def to_i() self.to_f.to_i end
        def to_s() self.to_f.to_s end
        def +(_) @_[->{self.to_f + _.to_f}] end
        def -(_) @_[->{self.to_f - _.to_f}] end
        def *(_) @_[->{self.to_f * _.to_f}] end
        def /(_) @_[->{self.to_f / _.to_f}] end
        def %(_) @_[->{self.to_f % _.to_f}] end
        def **(_) @_[->{self.to_f ** _.to_f}] end
        def ==(_) self.to_f == _.to_f end
        def <=>(_) @v = _ end
        def >>(_) _ << @n end
        def <<(n) @_[@v, n] end
        def +@() @_[->{+self.to_f}] end
        def -@() @_[->{+self.to_f}] end
        def !@() @_[->{(1..self.to_i).inject(:*) || 1}] end
end