次の条件を満たす正の整数全体の集合をSとおく。
「各けたの数字はたがいに異なり、
どの2つのけたの数字の和も9にならない。」
ただし、Sの要素は10進法で表す。
また、1けたの正の整数はSに含まれるとする。
このとき、次の問いに答えよ。
(1)Sの要素でちょうど4けたのものは何個あるか。
(2)小さい方から数えて2000番目のSの要素を求めよ。
プログラミングで解いてください。
使用言語はC++、Ruby、Pythonのいずれかでお願いします。
ちなみに、私は以下のように解きました。
lang
1def in_s?(n) 2 flag = false 3 ary = n.to_s.split('').map(&:to_i) 4 if ary.size == ary.uniq.size 5 flag = true if ary.combination(2).map{|i| i.inject(:+)}.all?{|i| i != 9} 6 end 7 return flag 8end 9 10s1 = [] 11for n in (1023..9876) 12 s1 << n if in_s?(n) 13end 14p s1.size 15 16s2 = [] 17for n in (1..9876) 18 s2 << n if in_s?(n) 19end 20p s2[1999]
追記
katoyさんのご指摘のように、集合Sをメモリー上に保持しなくても解けます。
その場合、上記の s1 = [] 以下を次のように変更してください。
lang
1count = 0 2for n in (1023..9876) 3 count += 1 if in_s?(n) 4end 5p count 6 7target_idx = 2000 8count = 0 9for n in (1..9876) 10 count += 1 if in_s?(n) 11 break p n if count == target_idx 12end
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2014/11/29 11:18