Problem 1

Projekt Euler w Ruby
1

Zadanie :
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Oto moja solucja :

$ints = [] 1000.times{|x| $ints << x if x%3==0 and !($ints.include?(x)) $ints << x if x%5==0 and !($ints.include?(x)) } $sum = 0 $ints.each{|x| $sum += x } puts $sum $stdin.gets

2 
 (1..1000).inject(0) { |sum, el| sum += (el % 3 == 0 || el % 5 == 0) ? el : 0 }

Najkrótsze rozwiązanie, na jakie wpadłem do tej pory (nie wiem, czy najszybsze ;))

3

Złożoność obliczeniowa powyższych rozwiązań to O(n).

Aby uzyskać stały czas O(1) należy skorzystać z faktu, że 3 + 6 + 9 + … + 999 to ciąg arytmetyczny. Analogicznie dla 5 + 10 + … + 995.
Sumę ciągu arytmetycznego można obliczyć za pomocą odpowiedniego wzoru.
Sumując powyższe dwa ciągi liczymy podwójnie liczby jednocześnie podzielne przez 3 i 5 (czyli podzielne przez 15).
Dlatego odejmujemy trzeci ciąg arytmetyczny 15 + 30 + 45 + … + 990.

[code=“ruby”]def arithmetic_sequence_sum(first, last, count)
(first + last) * 0.5 * count
end

def euler_1
res = 0
res += arithmetic_sequence_sum 3, 999, 999 / 3
res += arithmetic_sequence_sum 5, 995, 999 / 5
res -= arithmetic_sequence_sum 15, 990, 999 / 15
end

puts euler_1[/code]

4 
puts (1..999).to_a.select{ |i| i % 3 == 0 || i % 5 == 0 }.inject(:+)
5

Nie musisz robić (1..999).to_a, klasa Range też ma metodę select

6

dzięki,

8

Nie tylko długość, ale i ilość ciągów można mnożyć:

def multiples(max,*nums) 
  (0..2**nums.size-1).inject do |sum,k| 
    ms = (0..nums.size-1).select{|i| k[i]==1}
    m = ms.inject(1){|mul,x| mul.lcm nums[x]}
    sum-(-1)**ms.size*m*(1+max/m)*(max/m)/2
  end 
end
puts multiples 999,3,5
puts multiples 999,3,5,7,11,13,17,19,21,23,29,31,37,41,43,47,49,51

I z O(1) robi się O(2**n).