Fraction reduction: Difference between revisions
Content added Content deleted
Line 69: | Line 69: | ||
:* Wikipedia entry: [https://en.wikipedia.org/wiki/Anomalous_cancellation anomalous cancellation and/or accidental cancellation]. |
:* Wikipedia entry: [https://en.wikipedia.org/wiki/Anomalous_cancellation anomalous cancellation and/or accidental cancellation]. |
||
<br><br> |
<br><br> |
||
=={{header|C}}== |
|||
{{trans|C#}} |
|||
<lang c>#include <stdbool.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
typedef struct IntArray_t { |
|||
int *ptr; |
|||
size_t length; |
|||
} IntArray; |
|||
IntArray make(size_t size) { |
|||
IntArray temp; |
|||
temp.ptr = calloc(size, sizeof(int)); |
|||
temp.length = size; |
|||
return temp; |
|||
} |
|||
void destroy(IntArray *ia) { |
|||
if (ia->ptr != NULL) { |
|||
free(ia->ptr); |
|||
ia->ptr = NULL; |
|||
ia->length = 0; |
|||
} |
|||
} |
|||
void zeroFill(IntArray dst) { |
|||
memset(dst.ptr, 0, dst.length * sizeof(int)); |
|||
} |
|||
int indexOf(const int n, const IntArray ia) { |
|||
size_t i; |
|||
for (i = 0; i < ia.length; i++) { |
|||
if (ia.ptr[i] == n) { |
|||
return i; |
|||
} |
|||
} |
|||
return -1; |
|||
} |
|||
bool getDigits(int n, int le, IntArray digits) { |
|||
while (n > 0) { |
|||
int r = n % 10; |
|||
if (r == 0 || indexOf(r, digits) >= 0) { |
|||
return false; |
|||
} |
|||
le--; |
|||
digits.ptr[le] = r; |
|||
n /= 10; |
|||
} |
|||
return true; |
|||
} |
|||
int removeDigit(IntArray digits, size_t le, size_t idx) { |
|||
static const int POWS[] = { 1, 10, 100, 1000, 10000 }; |
|||
int sum = 0; |
|||
int pow = POWS[le - 2]; |
|||
size_t i; |
|||
for (i = 0; i < le; i++) { |
|||
if (i == idx) continue; |
|||
sum += digits.ptr[i] * pow; |
|||
pow /= 10; |
|||
} |
|||
return sum; |
|||
} |
|||
int main() { |
|||
int lims[4][2] = { { 12, 97 }, { 123, 986 }, { 1234, 9875 }, { 12345, 98764 } }; |
|||
int count[5] = { 0 }; |
|||
int omitted[5][10] = { {0} }; |
|||
size_t upperBound = sizeof(lims) / sizeof(lims[0]); |
|||
size_t i; |
|||
for (i = 0; i < upperBound; i++) { |
|||
IntArray nDigits = make(i + 2); |
|||
IntArray dDigits = make(i + 2); |
|||
int n; |
|||
for (n = lims[i][0]; n <= lims[i][1]; n++) { |
|||
int d; |
|||
bool nOk; |
|||
zeroFill(nDigits); |
|||
nOk = getDigits(n, i + 2, nDigits); |
|||
if (!nOk) { |
|||
continue; |
|||
} |
|||
for (d = n + 1; d <= lims[i][1] + 1; d++) { |
|||
size_t nix; |
|||
bool dOk; |
|||
zeroFill(dDigits); |
|||
dOk = getDigits(d, i + 2, dDigits); |
|||
if (!dOk) { |
|||
continue; |
|||
} |
|||
for (nix = 0; nix < nDigits.length; nix++) { |
|||
int digit = nDigits.ptr[nix]; |
|||
int dix = indexOf(digit, dDigits); |
|||
if (dix >= 0) { |
|||
int rn = removeDigit(nDigits, i + 2, nix); |
|||
int rd = removeDigit(dDigits, i + 2, dix); |
|||
if ((double)n / d == (double)rn / rd) { |
|||
count[i]++; |
|||
omitted[i][digit]++; |
|||
if (count[i] <= 12) { |
|||
printf("%d/%d = %d/%d by omitting %d's\n", n, d, rn, rd, digit); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
printf("\n"); |
|||
destroy(&nDigits); |
|||
destroy(&dDigits); |
|||
} |
|||
for (i = 2; i <= 5; i++) { |
|||
int j; |
|||
printf("There are %d %d-digit fractions of which:\n", count[i - 2], i); |
|||
for (j = 1; j <= 9; j++) { |
|||
if (omitted[i - 2][j] == 0) { |
|||
continue; |
|||
} |
|||
printf("%6d have %d's omitted\n", omitted[i - 2][j], j); |
|||
} |
|||
printf("\n"); |
|||
} |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>16/64 = 1/4 by omitting 6's |
|||
19/95 = 1/5 by omitting 9's |
|||
26/65 = 2/5 by omitting 6's |
|||
49/98 = 4/8 by omitting 9's |
|||
132/231 = 12/21 by omitting 3's |
|||
134/536 = 14/56 by omitting 3's |
|||
134/938 = 14/98 by omitting 3's |
|||
136/238 = 16/28 by omitting 3's |
|||
138/345 = 18/45 by omitting 3's |
|||
139/695 = 13/65 by omitting 9's |
|||
143/341 = 13/31 by omitting 4's |
|||
146/365 = 14/35 by omitting 6's |
|||
149/298 = 14/28 by omitting 9's |
|||
149/596 = 14/56 by omitting 9's |
|||
149/894 = 14/84 by omitting 9's |
|||
154/253 = 14/23 by omitting 5's |
|||
1234/4936 = 124/496 by omitting 3's |
|||
1239/6195 = 123/615 by omitting 9's |
|||
1246/3649 = 126/369 by omitting 4's |
|||
1249/2498 = 124/248 by omitting 9's |
|||
1259/6295 = 125/625 by omitting 9's |
|||
1279/6395 = 127/635 by omitting 9's |
|||
1283/5132 = 128/512 by omitting 3's |
|||
1297/2594 = 127/254 by omitting 9's |
|||
1297/3891 = 127/381 by omitting 9's |
|||
1298/2596 = 128/256 by omitting 9's |
|||
1298/3894 = 128/384 by omitting 9's |
|||
1298/5192 = 128/512 by omitting 9's |
|||
12349/24698 = 1234/2468 by omitting 9's |
|||
12356/67958 = 1236/6798 by omitting 5's |
|||
12358/14362 = 1258/1462 by omitting 3's |
|||
12358/15364 = 1258/1564 by omitting 3's |
|||
12358/17368 = 1258/1768 by omitting 3's |
|||
12358/19372 = 1258/1972 by omitting 3's |
|||
12358/21376 = 1258/2176 by omitting 3's |
|||
12358/25384 = 1258/2584 by omitting 3's |
|||
12359/61795 = 1235/6175 by omitting 9's |
|||
12364/32596 = 1364/3596 by omitting 2's |
|||
12379/61895 = 1237/6185 by omitting 9's |
|||
12386/32654 = 1386/3654 by omitting 2's |
|||
There are 4 2-digit fractions of which: |
|||
2 have 6's omitted |
|||
2 have 9's omitted |
|||
There are 122 3-digit fractions of which: |
|||
9 have 3's omitted |
|||
1 have 4's omitted |
|||
6 have 5's omitted |
|||
15 have 6's omitted |
|||
16 have 7's omitted |
|||
15 have 8's omitted |
|||
60 have 9's omitted |
|||
There are 660 4-digit fractions of which: |
|||
14 have 1's omitted |
|||
25 have 2's omitted |
|||
92 have 3's omitted |
|||
14 have 4's omitted |
|||
29 have 5's omitted |
|||
63 have 6's omitted |
|||
16 have 7's omitted |
|||
17 have 8's omitted |
|||
390 have 9's omitted |
|||
There are 5087 5-digit fractions of which: |
|||
75 have 1's omitted |
|||
40 have 2's omitted |
|||
376 have 3's omitted |
|||
78 have 4's omitted |
|||
209 have 5's omitted |
|||
379 have 6's omitted |
|||
591 have 7's omitted |
|||
351 have 8's omitted |
|||
2988 have 9's omitted</pre> |
|||
=={{header|C#|C sharp}}== |
=={{header|C#|C sharp}}== |