Rosetta Code

Count the coins: Difference between revisions

Page Discussion

Count the coins (view source)

Revision as of 06:30, 31 October 2011

340 bytes added ,  12 years ago
→‎{{header|C}}: limit memory usage; do larger values.
(→‎{{header|C}}: print integers instead)
(→‎{{header|C}}: limit memory usage; do larger values.)
Line 23:
#include <string.h>
#include <limits.h>
 
/* Simple recursion method. Using uint64 would have been enough
for task, if supremely slow */
Line 34:
count(sum, coins + 1);
}
 
/* ad hoc 128-bit integer (I'm aware of GMP, but this is faster) */
typedef unsigned long long ull;
typedef struct xint { ull c, v; } xint;
xint one = { 0, 1 }, zero = { 0, 0 };
 
xint countx(int sum, int *coins)
{
int s, i, n, cycle = 0;
xint *cache, *p, *end, *q, out;
for (sn = 10; s <= sumcoins[n]; sn++) {▼
if (coins[n] <= sum && coins[n] >= cycle)
cycle = coins[n] + 1;
 
cycle *= n;
p = cache = malloc(sizeof(xint) * n * (1 + sum)cycle);▼
end = cache + cycle;
for (i = 0; i < n; i++, *p++ = one);▼
 
for (ns = 1, i = 0; coins[n]s <= sum; np++); {
if (!i && p >= end) p = cache;
▲ p = cache = malloc(sizeof(xint) * n * (1 + sum));
 
if (coins[i] <= s) {
▲ for (i = 0; i < n; i++, *p++ = one);
q = p - coins[i] * n;
▲ for (s = 1; s <= sum; s++) {
for *p = (iq >= 0;cache) i? <*q n: q[cycle]; i++, p++) {
if} (s < 0)else
*p = zero;
 
else {
*p =if (coins[i] <= s++) ?{ p[-n /* coins[i]]128 :bit zero;addition */
ifp->c (i)+= {p[-1].c;
if (p->v >= ~(p[-1].v)) {p->c++;▼
/* 128 bit addition */
p->cv += p[-1].cv;
▲ if (p->v >= ~(p[-1].v)) {
p->c++;
if (! p->c) abort();
}
p->v += p[-1].v;
}
}
}
if (i == n) i = 0, s++;
}
 
out = p[-1];
free(cache);
 
return out;
}
 
void print (xint v)
{
# define BITS (sizeof(ull) * CHAR_BIT/2)
# define BASE (1ULL << BITS)
 
int i, k = 63;
char buf[64] = {0};
ull n[3] = {v.c, v.v >> BITS, v.v & (BASE - 1)};
 
while (n[0] || n[1] || n[2])
for (i = 0; i < 3; n[i++] /= 10)
if (i < 2) n[i + 1] += BASE * (n[i] % 10);
else buf[--k] = '0' + n[2] % 10;
 
puts(buf + k);
}
 
int main()
{
int us_coins[] = { 100, 50, 25, 10, 5, 1, 0 };
int eu_coins[] = { 200, 100, 50, 20, 10, 5, 2, 1, 0 };
 
printf("%d\n", count(100, us_coins + 2));
print(countx( 1000 * 100, us_coins));
print(countx( 10000 * 100, us_coins));▼
print(countx(1000100000 * 100, eu_coinsus_coins));▼
 
putchar('\n');
▲ print(countx(10000 * 100, us_coins));
 
▲ print(countx(1000 * 100, eu_coins));
print(countx(10000 1 * 100, eu_coins));
print(countx( 1000 * 100, eu_coins));
print(countx( 10000 * 100, eu_coins));
print(countx(100000 * 100, eu_coins));
 
return 0;
}</lang>output (task only requires the first two lines are required by task):<lang>242
13398445413854501
1333983445341383545001
133339833445334138335450001
 
4563
10056050940818192726001
99341140660285639188927260001</lang>
992198221207406412424859964272600001</lang>
 
=={{header|Common Lisp}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/203831"