Login
Immutable PageDiscussionInfoAttachments

Please use a more selective search term instead of ""

Clear message
iz/競技プログラミング/Project Euler 033 Digit canceling fractions

MMA

http://projecteuler.net/problem=33

全探索。少々汚いコードになった。

Fracクラスは最後の掛け算のためだけに導入。手で計算した方が早かった。

   1 #!/usr/bin/env ruby
   2 
   3 def dup(d, n)
   4   return d.to_s.chars.to_a & n.to_s.chars.to_a
   5 end
   6 
   7 class Frac 
   8   attr_reader :d, :n
   9   def initialize(d, n)
  10     g = d.gcd(n)
  11     @d = d / g
  12     @n = n / g
  13   end
  14   def *(o)
  15     Frac.new(@d * o.d, @n * o.n)
  16   end
  17   def to_s
  18     "#{@d} / #{@n}"
  19   end
  20 end
  21 
  22 pseud = []
  23 (10...100).each do |d|
  24   (d...100).each do |n|
  25     next if n == d
  26     next if n % 10 == 0 || d % 10 == 0
  27     next if n % 11 == 0 || d % 11 == 0
  28     cancels = dup(d, n)
  29     cancels.each do |c|
  30       _n = (n.to_s.chars.to_a - [c]).join.to_s.to_i
  31       _d = (d.to_s.chars.to_a - [c]).join.to_s.to_i
  32       pseud << Frac.new(_d, _n) if (n.to_f / d.to_f == _n.to_f / _d.to_f)
  33     end
  34   end
  35 end
  36 p pseud.inject(Frac.new(1, 1)){|acc, f| acc * f}