3

この質問はProject Euler Problem 5を参照しているので、ネタバレに注意してください! 問題 5:

2520 は、1 から 10 までの各数値で割り切れる最小の数値です。1 から 20 までのすべての数で割り切れる最小の正の数は?

問題 5 の解決策として、Ruby で次のコードを書きました。

num = 2520
until (1..20).all?{|x| num % x == 0}
  num += 1
end
puts "#{num}"

ただし、スクリプトを実行するたびにハングします。基本ケース 2520 で 1 から 10 の範囲で同じ方法をテストしたところ、問題なく動作したことに注意してください。

より単純なケースでは機能するのに、より高度なケースでは機能しないのはなぜですか? 私が持っているものを修正するにはどうすればよいですか?

4

5 に答える 5

2

他の問題のように、この問題を力ずくで解決することはできません。より効率的な解決策を見つける必要があります。

下のネタバレ

これは非常に効率的な方法です (これが Ruby にあまり似ていない場合は申し訳ありません)。

def find_multiple
  lcm = 1

  (2..20).each do |i|
    lcm *= i / gcd(lcm, i)
  end

  lcm
end

def gcd(a, b)
  while b > 0
    a %= b
    return b if a == 0
    b %= a
  end

  a
end

puts find_multiple

それを解決するためのより Ruby のような方法を探している場合は、次を使用できます (コメントの steenslag によって提案されているように)。

(1..20).inject(:lcm)
于 2013-05-29T04:54:57.827 に答える
1

ゲームに少し遅れましたが、ここに私の意見があります。簡潔で非常に明確なコードが気に入った場合は、実行を高速化するためにいくつかの小さな調整を行うことができます。これはタイムアウトせずにうまくいきました： 

num = 20

  until (11..20).all?{ |i| num % i == 0 }
    num +=20
  end

puts num

基本的には、20 で割り切れる必要があることがわかっているため、20 ずつインクリメントするだけであり、セットの下位 1/2 の反復処理をスキップできます。

于 2014-04-07T05:05:38.457 に答える
1

Ruby 言語での最も単純でクリーンなソリューション。

(1..20).inject(:lcm) # output will be 232792560
于 2015-01-29T11:05:02.043 に答える
0

これを試して。コード：

i=2520
max_product = (4..19).inject(1){|j,k| j*k}
puts max_product
while i < max_product
    if( [3, 7].inject(true) do |memo, p|
        memo && i%p==0
    end)
      if( 
          (4..20).inject(true) do |memo, p|
          memo && i%p==0
          end 
      )   
      puts i
      end 
    end 
    i+=10
end
于 2013-05-29T04:56:11.580 に答える