Snippets

Camilo Rocha CC naive

Created by Former user
View revision

File cc_naive.py Added

  • Ignore whitespace
  • Hide word diff 
+# input: a[0..N) array of distinct positive integers, N>=0, and S
+# output: number of ways that S can be obtained with an unlimited
+#         amount of coins with denominations in a[0..N)
+#
+# exponential (in N) naive solution
+
+def cc_naive(a, S):
+  return cc_aux(a, len(a), S)
+
+def cc_aux(a, n, s):
+  ans = None
+  if n==0: ans = 1 if s==0 else 0
+  else:
+    ans = cc_aux(a, n-1, s)
+    if a[n-1]<=s: ans += cc_aux(a, n, s-a[n-1])
+  return ans
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.