140831

Ruby


140823(3)　　Partition

　↓　手をくわえる。

140823(4)　　Prime Partition

汎用性はないが、140823(3)分よりも分割数を速く求めることができるコードを書いてみた。

（以下において、

p(i) = p(i - 1) + p(i - 2) - p(i - 5) - p(i - 7) + ...

を用いている。）

n = 10000

@part = [1, 1]
def part(i)
  sum = 0
  for j in (0..i)
    i1 = (1 - 2 * (j % 2)) * ((j + 2) / 2) # 1, -1, 2, -2, 3, -3, ...
    i1 = i1 * (3 * i1 - 1) / 2             # 1, 2, 5, 7, 12, 15, ...
    break if i1 > i
    if (j / 2).even?
      sum += @part[i - i1]
    else
      sum -= @part[i - i1]
    end
  end
  @part[i] = sum
end
for i in (1..n)
  part(i)
end

p @part[n]

140824

Ruby


循環節

dを「2からnまでの2でも5でも割り切れない整数」とする。
n = 20 のとき、d，1/dの循環節の長さ，1/dの循環節を出力せよ。

n = 20
(2..n).each{|d|
if d % 2 != 0 && d % 5 != 0
  cnt = 1
  x = (10 ** cnt) - 1
  while x % d != 0
    cnt += 1
    x = (10 ** cnt) - 1
  end
  puts "#{d}  #{(x / d).to_s.size}  #{(x / d).to_s}"
end
}

出力結果
3  1  3
7  6  142857
9  1  1
11  1  9
13  5  76923
17  15  588235294117647
19  17  52631578947368421

140823(4)

Ruby


Prime Partition

require 'prime'

n = 11
ary = []
Prime.each(n){|pr| ary << pr}

ps = Array.new(n + 1){0}
ps[0] = 1
ary.each{|num|
  (num..n).each{|i|
    ps[i] += ps[i - num]
  }
}
p ps[n]  # 2+2+2+2+3 = 2+3+3 = 2+2+2+5 = 3+3+5 = 2+2+7 = 11

140823(3)

Ruby


Partition (number theory)

以下の２つのコードのうち下の方が断然はやい。

n = 6

numbers = (1..n).to_a

cnt = 0

for i in (1..n)

numbers.repeated_combination(i){|j|

  if j.inject(:+) == n

    cnt += 1

  end

}

end

p cnt

n = 6

nums = (1..n).to_a

ps = Array.new(n + 1){0}

ps[0] = 1

nums.each{|num|

  # 末尾がnumなるものをカウント

  (num..n).each{|i|

    ps[i] += ps[i - num]

  }

}

p ps[n]

140823(2)

Ruby


約数の和（自身を含む）

require 'mathn'

# a^1+a^2+......a^x
def sum1(i, j)
  power = 1
  sum = 1
  for k in (1..j)
    power *= i
    sum += power
  end
  return sum
end

# (a^1+a^2+......a^x)(b^1+b^2+......b^y)......
def sum2(i)
  sum = 1
  pq = i.prime_division
  pq.each{|tes| sum *= sum1(tes[0], tes[1])}
  return sum
end

p sum2(24)  # 1, 2, 3, 4, 6, 8, 12, 24

出力結果
60

140823

Ruby


配列の結合について

ary1 = []
for i in (1..8)
p ary1
ary1 |= [2 * i, 3 * i, 5 * i]
end
p ary1

ary2 = []
for i in (1..8)
p ary2
ary2 += [2 * i, 3 * i, 5 * i]
end
p ary2

出力結果
[]
[2, 3, 5]
[2, 3, 5, 4, 6, 10]
[2, 3, 5, 4, 6, 10, 9, 15]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 14, 21, 35]
[2, 3, 5, 4, 6, 10, 9, 15, 8, 12, 20, 25, 18, 30, 14, 21, 35, 16, 24, 40]
[]
[2, 3, 5]
[2, 3, 5, 4, 6, 10]
[2, 3, 5, 4, 6, 10, 6, 9, 15]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30, 14, 21, 35]
[2, 3, 5, 4, 6, 10, 6, 9, 15, 8, 12, 20, 10, 15, 25, 12, 18, 30, 14, 21, 35, 16,
 24, 40]

140817

Ruby


gets, each_line, readlines

以下において、Inputは
3776
1111
645
2222
333
とする。

n = gets.to_i
p n
p ""
n = gets.to_i
p n
p ""
ARGF.each_line{|line|
  p line.to_i
}

出力結果
3776
""
1111
""
645
2222
333

n = gets.to_i
p n
p ""
n = gets.to_i
p n
p ""
readlines.each{|line|
  p line.to_i
}

出力結果
3776
""
1111
""
645
2222
333

ARGF.each_line{|line|
  p line.to_i
}

出力結果
3776
1111
645
2222
333

readlines.each{|line|
  p line.to_i
}

出力結果
3776
1111
645
2222
333

140813

Ruby

最大増加部分列（longest increasing subsequence）

「Rubyによる情報科学入門」で最大増加部分列の問題と出会う。

以下のコード（http://133.11.50.227/~kuno/is11/siryou/ohp12.pdf）

に間違いを見つける。

def lis(a)

  l = Array.new(a.length); t = Array.new(a.length)

  m = 1; p = 0

  a.each_index do |i|

    l[i] = 1; t[i] = i+1

    (i-1).step(0, -1) do |j|

      if a[i] > a[j] && l[i] < l[j]+1

        l[i] = l[j]+1; t[i] = i-j

        if m < l[i] then p = i; m = l[i] end

      end

    end

  end

  puts "a: #{a}"  #コードの間違いを発見するために追加

  puts "l: #{l}"  #　　　〃

  puts "t: #{t}"  #　　　〃

  showlis(a, t, p); puts

end

def showlis(a, t, p)

  if p > 0 then showlis(a, t, p-t[p]) end

  print(" #{a[p]}")

end

# 実験

a = [1, 5, 7, 2, 6, 3, 4, 9]

lis(a)

b = [4, 1, 6, 2, 8, 5, 7, 3]

lis(b)

c = [4, 1, 6, 2, 8, 0, 5, 7, 3]

lis(c)

d = [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]

lis(d)

出力結果

a: [1, 5, 7, 2, 6, 3, 4, 9]

l: [1, 2, 3, 2, 3, 3, 4, 5]

t: [1, 1, 1, 3, 1, 2, 1, 1]

 1 2 3 4 9

a: [4, 1, 6, 2, 8, 5, 7, 3]

l: [1, 1, 2, 2, 3, 3, 4, 3]

t: [1, 2, 1, 2, 1, 2, 1, 4]

 3 1 2 5 7

a: [4, 1, 6, 2, 8, 0, 5, 7, 3]

l: [1, 1, 2, 2, 3, 1, 3, 4, 3]

t: [1, 2, 1, 2, 1, 6, 3, 1, 5]

 3 1 2 5 7

a: [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]

l: [1, 1, 2, 2, 3, 1, 3, 4, 3, 2, 3, 4, 5]

t: [1, 2, 1, 2, 1, 6, 3, 1, 5, 4, 1, 1, 1]

 4 0 1 2 3 4

修正

def lis(a)

  l = Array.new(a.size); t = Array.new(a.size)

  m = 1; p = 0

  a.each_index{|i|

    l[i] = 1; t[i] = 0

    (i - 1).step(0, -1){|j|

      if a[i] > a[j] && l[i] < l[j] + 1

        l[i] = l[j] + 1; t[i] = i - j

        if m < l[i]

          p = i; m = l[i]

        end

      end

    }

  }

  puts "a: #{a}"

  puts "l: #{l}"

  puts "t: #{t}"

  showlis(a, t, p); puts

end

def showlis(a, t, p)

  if t[p] > 0

    showlis(a, t, p - t[p])

  end

  print(" #{a[p]}")

end

a = [1, 5, 7, 2, 6, 3, 4, 9]

lis(a)

b = [4, 1, 6, 2, 8, 5, 7, 3]

lis(b)

c = [4, 1, 6, 2, 8, 0, 5, 7, 3]

lis(c)

d = [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]

lis(d)

出力結果

a: [1, 5, 7, 2, 6, 3, 4, 9]

l: [1, 2, 3, 2, 3, 3, 4, 5]

t: [0, 1, 1, 3, 1, 2, 1, 1]

 1 2 3 4 9

a: [4, 1, 6, 2, 8, 5, 7, 3]

l: [1, 1, 2, 2, 3, 3, 4, 3]

t: [0, 0, 1, 2, 1, 2, 1, 4]

 1 2 5 7

a: [4, 1, 6, 2, 8, 0, 5, 7, 3]

l: [1, 1, 2, 2, 3, 1, 3, 4, 3]

t: [0, 0, 1, 2, 1, 0, 3, 1, 5]

 1 2 5 7

a: [4, 1, 6, 2, 8, 0, 5, 7, 3, 1, 2, 3, 4]

l: [1, 1, 2, 2, 3, 1, 3, 4, 3, 2, 3, 4, 5]

t: [0, 0, 1, 2, 1, 0, 3, 1, 5, 4, 1, 1, 1]

 0 1 2 3 4

140812

Ruby


処理される順番について

すごく基本的なことだが、次の二つは処理される順番が異なる。

def zyunban0(a, p)
  if p > 0
    zyunban0(a, p - 1)
  end
  puts "#{p}: #{a[p]}"
end

a = [100, 101, 102, 103]
b = a.size
zyunban0(a, b - 1)

出力結果
0: 100
1: 101
2: 102
3: 103

def zyunban1(a, p)
  while p > 0
    puts "#{p}: #{a[p]}"
    p = p - 1
  end
end

a = [100, 101, 102, 103]
b = a.size
zyunban1(a, b - 1)

出力結果
3: 103
2: 102
1: 101