読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】「開き直り数」を求める

今勉強している、この本↓にあった問題、「開き直り数」を求めました。

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版



 

問題

3435という数は、1桁ずつに分けて、それぞれの数を自分と同じ数でべき乗して足し合わせると,元の数である3435になる。
 3435 = 3**3 + 4**4 + 3**3 + 5**5
このような数を“開き直り数”と呼ぶことにする。ちょっと考えれば1(=11)もこの種の数であることがわかる。では1以上の整数で、この1と3435以外の開き直り数をすべて見つけていただきたい。ただし、ここでは00は0とする。

http://silver.arrow.jp/doc/puzzle/puzzle_cmag200106.php

出来た!
書くのも早くなってきた!


 

解答

def hirakinaori?(candidate)
  result_digit = forDigit(total(candidate))
  return true if candidate == result_digit
  return false
end

#[0,2,2,1,0,0,0,0,0,0] => 1**1*2 + 2**2*2 + 3**3*1 = 37
def total(arr)
  exponential = [0, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489]
  result = 0
  i = 0
  while i < arr.length
    result += arr[i]*exponential[i]
    i += 1
  end
  result
end

#12213 =>[0,2,2,1,0,0,0,0,0,0]
def forDigit(int)
  tmp = int.to_s.split("").map!{|a| a.to_i}
  result = Array.new(10,0)
  tmp.each {|a| result[a] += 1 }
  result
end

def makeNumbers (result ,array, range_left, seed, count)
  return if count > 10
  i = range_left
  while i < 10
    tmp = array.dup
    tmp[i] += 1
    result << tmp if hirakinaori?(tmp)
    makeNumbers(result, tmp, i, seed+1, count+1)
    i += 1
  end
  result
end

init = Array.new(10,0)
answer = makeNumbers([],init, 0, 1, 1)
answer.delete([1, 0, 0, 0, 0, 0, 0, 0, 0, 0])
p answer
answer.each {|arr| p total(arr)}

■実行結果

[[1, 0, 0, 1, 1, 1, 0, 1, 3, 1], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 2, 1, 1, 0, 0, 0, 0]]
438579088
1
3435

 
やった!