fork download
copy 
  1. def find(n, result, d, coins, changes, index):
  2.     if n == 0:
  3.         changes.append(result)
  4.         return
  5.     for i in range(index, len(coins)):
  6.         if n - coins[i] >= 0 and d[n] == d[n - coins[i]] + 1:
  7.             find(n - coins[i], result + [coins[i]], d, coins, changes, i)
  8.  
  9.  
  10. def find_changes(n, formula):
  11.     d = [n + 1] * (n + 1)
  12.     d[0] = 0
  13.     for i in range(1, n + 1):
  14.         for c in formula:
  15.             if i - c >= 0:
  16.                 d[i] = min(d[i], d[i - c] + 1)
  17.     changes = []
  18.     find(n, [], d, formula, changes, 0)
  19.     return changes
  20.  
  21. def solve(n,formula):
  22.     ans = find_changes(n,formula)
  23.     print("總數",len(ans),'\n',ans,'\n\n')
  24.  
  25.  
  26. solve(10,[2,2,2,2])
  27. solve(5,[2,3,4,5])
  28. solve(10,[4,5,6,7])
Success #stdin #stdout 0.02s 9172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
總數 56 
 [[2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2]] 


總數 1 
 [[5]] 


總數 2 
 [[4, 6], [5, 5]]
https://ideone.com/o0HaXD
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!