Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 19:00, 31 October 2011

419 bytes added ,  12 years ago
Updated D code
(Updated Python code)
(Updated D code)
Line 161:
}
 
BigInt changeCountcountChanges(in Cents amount, in int[] coins) /*pure nothrow*/
in {
assert(amount > 0);
assert(coins.length > 0);
foreach (c; coins) assert(c > 0);
assert(c > 0);
} out(result) {▼
assert(cast()result > 0); // de-const, bug workaround▼
} body {▼
static int findCycle(in Cents amount, in int[] coins)
pure nothrow {
int lcycle;
immutableforeach (const int n =c; coins.length;)▼
if (coins[0]c <= samount && c >= lcycle)▼
t[pos]lcycle += t[posc -+ 1];▼
return lcycle * coins.length;
}
immutable int cycle = findCycle(amount, coins);
▲ out(result) {
immutable size_t n = coins.length;
▲ assert(cast()result > 0); // de-const, bug workaround
}▼
▲ body {
▲ immutable int n = coins.length;
auto t = new BigInt[n * (amount + 1)];
t[0 .. n] = BigInt(1);▼
 
auto table = new size_t pos = nBigInt[cycle];
foreach (s; 1table[0 .. amount.cn] += BigInt(1) {;
 
▲ if (coins[0] <= s)
int t[pos] = t[pos - (n * coins[0])];
int pos++i;
for (int s = 1; s <= foreach (iamount; 1 .. n) {
if (i == 0 && pos if (coins[i] <>= scycle)
t[pos] = t[pos - (n * coins[i])]0;
 
▲ t[pos] += t[pos - 1];
if (coins[i] <= s) pos++;{
}immutable int q = pos - (coins[i] * n);
table[pos] = (q >= 0) ? table[q] : table[q + cycle];
}
 
returnif t[pos - 1];(i)
table[pos] += table[pos - 1];
i++;
if (i == n) {
▲ t[0 .. n] i = BigInt(1)0;
s++;
}
 
pos++;
}
 
return table[pos - 1];
}
 
void main() {
immutable usCoins = [100, 50, 25, 10, 5, 1];
writeln(changeCount(Cents( 1_00), usCoins[2 .. $]));▼
writeln(changeCount(Cents( 1000_00), usCoins));▼
writeln(changeCount(Cents(10000_00), usCoins));▼
 
immutable euCoins = [200, 100, 50, 20, 10, 5, 2, 1];
 
writeln(changeCount(Cents( 1000_00), euCoins));
writelnforeach (changeCount(Cents(10000_00)coins; [usCoins, euCoins])); {
▲ writeln(changeCountcountChanges(Cents( 1_00), usCoinscoins[2 .. $]));
▲ writeln(changeCountcountChanges(Cents( 1000_00), usCoinscoins));
▲ writeln(changeCountcountChanges(Cents( 10000_00), usCoinscoins));
writeln(countChanges(Cents(100000_00), coins), "\n");
▲ }
}</lang>
Output:
Line 205 ⟶ 224:
13398445413854501
1333983445341383545001
133339833445334138335450001
 
4562
10056050940818192726001
99341140660285639188927260001</pre>
992198221207406412424859964272600001</pre>
 
=={{header|Factor}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203835"