gist: 206210


  
    
      cc.rb #
    
    
      
      
        embed
        
      
      
      
      raw
    
  
  
  
    
      
        
          
            
            1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

          
          
            
              def count_change(amount, denominations = [50,25,10,5,1])
  result = 1
  largest_denomination_count = 1
 
  until denominations.size == 1
    until makes_change?(amount, denominations, largest_denomination_count) == false
      puts "change made with #{largest_denomination_count} coins of value #{denominations.first}"
      result += 1
      largest_denomination_count += 1
    end
    largest_denomination_count = 1
    denominations.slice!(0)
  end
 
  puts "#{result} possible combinations for change of #{amount}"
end
 
def makes_change?(amount, denominations, largest_denomination_count)
  (denominations.first * largest_denomination_count) <= amount
end
 
count_change(100)
 
# problem is this only counts 1 combination as it decrements :(
Public Clone URL:	git://gist.github.com/206210.git Give this clone URL to anyone. `git clone git://gist.github.com/206210.git gist-206210`
Embed All Files:	show embed