Fraction reduction: Difference between revisions
→{{header|C#|C sharp}}
Line 69:
:* Wikipedia entry: [https://en.wikipedia.org/wiki/Anomalous_cancellation anomalous cancellation and/or accidental cancellation].
<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}}==
| |||