Count the coins: Difference between revisions

Content added Content deleted

Inline

@@ Line 3,812: / Line 3,812: @@
 =={{header|V (Vlang)}}==
-{{trans|go}}
+{{trans|Go}}
-<syntaxhighlight lang="go">fn main() {
+<syntaxhighlight lang="go">
+fn main() {
     amount := 100
-    println("amount, ways to make change: $amount ${count_change(amount)}"))
+    println("amount: $amount; ways to make change: ${count_change(amount)}")
 }
 fn count_change(amount int) i64 {
+	if amount.str().count('0') > 4 {exit(-1)} // can be too slow
     return cc(amount, 4)
 }
 fn cc(amount int, kinds_of_coins int) i64 {
-    if amount == 0 {
+    if amount == 0 {return 1}
-        return 1
+    else if amount < 0 || kinds_of_coins == 0 {return 0}
-    } else if amount < 0 || kinds_of_coins == 0 {
-        return 0
-    }
     return cc(amount, kinds_of_coins-1) +
         cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
@@ Line 3,834: / Line 3,833: @@
 fn first_denomination(kinds_of_coins int) int {
     match kinds_of_coins {
-{
+{return 1}
-			return 1
+{return 5}
+{return 10}
-		}
-{
+{return 25}
+		else {exit(-2)}
-			return 5
-		}
-{
-			return 10
-		}
-{
-			return 25
-		}
 	}
+	return kinds_of_coins
-}</syntaxhighlight>
+}
+</syntaxhighlight>
 Output:
 <pre>
 amount, ways to make change: 100 242
+</pre>
+Alternate:
+<syntaxhighlight lang="go">
+fn main() {
+	amount := 100000
+	coins := [1, 5, 10, 25]
+	println("amount: $amount; ways to make change: ${count_2(coins, amount)}")
+}
+fn count(coins []int, amount int) int {
+	mut arr := []int{len: amount + 1}
+	arr[0] = 1
+	for coin in coins {
+		for idx := coin; idx <= amount; idx++ {
+			arr[idx] += arr[idx - coin]
+		}
+	}
+	return arr[amount]
+}
+</syntaxhighlight>
+Output:
+<pre>
+amount: 100000; ways to make change: 279364825
 </pre>