目次
完全数と疑似完全数について、判別するコードを書いてみました。
定義
- 完全数
- その数自身を除く約数の和が、その数自身と等しい自然数
- 疑似完全数
- その数自身を除くいくつかの約数の総和がその数自身に等しい自然数
完全数は、同時に擬似完全数でもあります。
コード
環境
- Ruby 2.4.0
クラス Number を作りました。 is_perfect? で完全数か否かが、 is_semiperfect? で擬似完全数か否かがわかります。
初期化処理のところで約数を配列に入れてしまっています。 初期化でそれをやるべきかというのは考えるべきことではありますが、今回は目的が特化しているのでこれで。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Number attr_reader :n def initialize(n) @n = n @factors = [1] u = (@n ** 0.5).to_i 2.step(u, 1) do |i| if @n % i == 0 @factors.push(i) s = @n / i if i != s @factors.push(s) end end end @factors.sort! end def is_perfect? return @factors.sum == @n end def is_semiperfect? return check_semiperfect([], 0, @factors.length - 1) end private def check_semiperfect(element_array, sub_total, upper_index) if sub_total == @n return true end if upper_index < 0 return false end if sub_total > @n || sub_total + @factors[0, upper_index + 1].sum < @n return false end if check_semiperfect(element_array + [@factors[upper_index]], sub_total + @factors[upper_index], upper_index - 1) return true end if upper_index > 0 if check_semiperfect(element_array + [@factors[upper_index - 1]], sub_total + @factors[upper_index - 1], upper_index - 2) return true end end return false end end |
check_semiperfect? の第1引数は部分和を作る数を配列にして格納しています。 今回は擬似完全数か否かを計算するだけなので使いませんが、足してもとの数になる約数列を出す場合に使えます。
上のコードは次のようにして実行できます。
|
1 2 3 4 |
for i in 1..100 n = Number.new(i) puts n.n.to_s + " : " + n.is_perfect?.to_s + " / " + n.is_semiperfect?.to_s end |
このアウトプットは次のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
1 : true / true 2 : false / false 3 : false / false 4 : false / false 5 : false / false 6 : true / true 7 : false / false 8 : false / false 9 : false / false 10 : false / false 11 : false / false 12 : false / true 13 : false / false 14 : false / false 15 : false / false 16 : false / false 17 : false / false 18 : false / true 19 : false / false 20 : false / true 21 : false / false 22 : false / false 23 : false / false 24 : false / true 25 : false / false 26 : false / false 27 : false / false 28 : true / true 29 : false / false 30 : false / true 31 : false / false 32 : false / false 33 : false / false 34 : false / false 35 : false / false 36 : false / true 37 : false / false 38 : false / false 39 : false / false 40 : false / true 41 : false / false 42 : false / true 43 : false / false 44 : false / false 45 : false / false 46 : false / false 47 : false / false 48 : false / true 49 : false / false 50 : false / false 51 : false / false 52 : false / false 53 : false / false 54 : false / true 55 : false / false 56 : false / true 57 : false / false 58 : false / false 59 : false / false 60 : false / true 61 : false / false 62 : false / false 63 : false / false 64 : false / false 65 : false / false 66 : false / true 67 : false / false 68 : false / false 69 : false / false 70 : false / false 71 : false / false 72 : false / true 73 : false / false 74 : false / false 75 : false / false 76 : false / false 77 : false / false 78 : false / true 79 : false / false 80 : false / true 81 : false / false 82 : false / false 83 : false / false 84 : false / true 85 : false / false 86 : false / false 87 : false / false 88 : false / true 89 : false / false 90 : false / true 91 : false / false 92 : false / false 93 : false / false 94 : false / false 95 : false / false 96 : false / true 97 : false / false 98 : false / false 99 : false / false 100 : false / true |
補足
擬似完全数の判定は、部分和問題と呼ばれるものです。 (参考: プログラミングコンテストチャレンジブック)
