Problem 53

Projekt Euler w Ruby
1

Problem 53

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, [sup]5[/sup]C[sub]3[/sub] = 10.

In general,

[sup]n[/sup]C[sub]r[/sub] = n! / r!(n−r)!

where r <= n, n! = n*(n−1)…321, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: [sup]23[/sup]C[sub]10[/sub] = 1144066.

How many, not necessarily distinct, values of [sup]n[/sup]C[sub]r[/sub], for 1 <= n <= 100, are greater than one-million?

2

Ruby1.9

[code=ruby]Fact = {}
a = 1
b = 0
(1…100).each do |t|
s = a*t
a = s
Fact[t] = s
end
def facto(n)
Fact[n]
end

def count_comb(all, x)
facto(all)/(facto(x)*facto(all-x))
end

(1…100).each do |aa|
(1…(aa-1)).each do |bb|
b+=1 if count_comb(aa, bb) > 1000000
end
end

puts “zadane kryteria ma #{b} kombinacji”[/code]

3

To jest mniejsze:

[code=ruby]#!/usr/bin/env ruby
N = 100

def comb(n, r)
(1…r).inject(1) { |c, i| (c*(n-i+1))/i }
end

t = (1…N).collect { |n| (1…n).select { |r| c = comb(n, r); c if c > 1000000 } }.flatten
p t.size[/code]

4

i trochę wolniejsze … :wink:
ale chyba też bardziej “ruby-way”