In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
Nie wiem czy dobrze to wymyśliłem. Zrobiłem to z kraty ja zad 15. Moze jakiś prawdziwy informatyk z zaliczoną Dyskretną na 5 się wypowie 
[code=ruby]#!/usr/bin/env ruby
def silnia(n)
if n == 0
1
else
n * silnia(n-1)
end
end
puts silnia(576) / (silnia(200) * silnia(376))
163121671889219732705476122028975538664480680006042344
3030946073873989031824473860586644505808857299839425958
3330543107087844710301142016607[/code]
[code=ruby]#!/usr/bin/env ruby
def silnia(n)
if n == 0
1
else
n * silnia(n-1)
end
end
puts (silnia(3) / (silnia(2) * silnia(1))) + (silnia(6) / (silnia(2) * silnia(4))) + (silnia(12) / (silnia(2) * silnia(10))) + (silnia(42) / (silnia(2) * silnia(40))) + (silnia(102) / (silnia(2) * silnia(100))) + (silnia(202) / (silnia(2) * silnia(200)))[/code]
To może coś takiego. Bardziej prawdopodobny wynik. Tylko nie wiem czy czasami tam jeszcze nie trzeba czegoś odjąć :? Bo to na moje oko będą jakieś kombinacje z powtórzeniami.
Może i bardziej prawdopodobny ale nieprawidłowy 
[code=ruby]@coins = [1,2,5,10,20,50,100,200]
@combinations = []
def x(haz)
sum = haz.inject(:+) || 0
if sum == 200
print “.”
@combinations << haz
elsif sum < 200
@coins.each do |coin|
x(haz + [coin])
end
end
end
x []
p @combinations[/code]
Jak ktos ma super maszyne i tydizen czasu - zapraszam do odpalenia ^^
Panowie, nie tędy droga
To moja propozycja - weryfikowałem dla identycznego problemu z TOTAL=10. Być może nie jest to poprawne rozwiązanie, ale z pewnością “niezbyt dalekie od poprawnego”
[code=ruby]COINS = [2, 5, 10, 20, 50, 100, 200]
TOTAL = 200
def print_comb(combination,value)
print combination.join(" “)
puts " 1” * value
end
def combination(value, index_max, combination)
result = 0
COINS[0…index_max].each_with_index do |coin,index|
if value - coin >= 0
result += 1 + combination(value - coin,index,combination + [coin])
end
end
result
end
puts “wynik #{combination(TOTAL, COINS.size-1, []) +1}”[/code]
Dodam, że program kończy działanie po kilku sekundach
Można by go przyspieszyć, przez przechowywanie częściowych wyników, ale nie ma takiej potrzeby.
Apohllo, to poprawne rozwiązanie
“Aby zrozumieć rekurencję musisz najpierw zrozumieć rekurencję” 
Dokładnie. Ostatnio powierzono mi wykładanie Prologa, gdzie rekurencja jest używana w masowych ilościach…
Przyspieszony:
[code:ruby]COINS = [1, 2, 5, 10, 20, 50, 100, 200]
TOTAL = 200
a = Array.new(TOTAL+1)
(0…TOTAL).each {|i| a[i]= Array.new(COINS.size); a[i][0] = 1 }
(0…COINS.size-1).each { |i| a[0][i]= 1 }
(1…TOTAL).each do |t|
(1…COINS.size-1).each do |c|
a[i=t][c] = 0
while (i >= 0)
a[t][c] += a[i][c-1]
i -= COINS[c]
end
end
end
puts a[TOTAL][COINS.size-1][/code]
0.159s
No to jak już się chwalimy… to w erlangu kiedyś spłodziłem:
[code=erlang]-module(e031).
-export([main/1, start/0]).
coins() ->
[1, 2, 5, 10, 20, 50, 100, 200].
combinations(0, _Coins) ->
1;
combinations(Value, Coins) ->
LessCoins = lists:filter(
fun(E) -> E =< Value end,
Coins
),
lists:sum(lists:map(fun(E) -> combinations(Value - E, [X || X <- LessCoins, X >= E]) end, LessCoins)).
main(_) ->
start().
start() ->
io:format("~p~n", [combinations(200, coins())]).[/code]