2014年8月31日日曜日

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]

2014年8月24日日曜日

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

2014年8月23日土曜日

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)

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

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]

2014年8月17日日曜日

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

2014年8月13日水曜日

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

2014年8月12日火曜日

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