How to resolve the algorithm Fraction reduction step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Fraction reduction step by step in the C programming language

Table of Contents

Problem Statement

A method to   "reduce"   some reducible fractions is to   cross out   a digit from the numerator and the denominator.   An example is: resulting in:

Naturally,   this "method" of reduction must reduce to the proper value   (shown as a fraction). This "method" is also known as   anomalous cancellation   and also   accidental cancellation.

(Of course,   this "method" shouldn't be taught to impressionable or gullible minds.)       😇

Find and show some fractions that can be reduced by the above "method".

Show all output here, on this page.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fraction reduction step by step in the C programming language

This C program is designed to explore and count the number of "curious" fractions within specific ranges of values. A curious fraction is defined as a fraction where the numerator and denominator are constructed using a unique set of non-zero digits. The program also identifies and counts the omitted digits in these fractions.

  1. Data Structures:

    • IntArray: A custom data structure defined as a struct containing an integer pointer (ptr) and a size_t integer (length) representing the length of the array. This structure is used to represent arrays of integers.

  2. Array Management Functions:

    • make(size_t size): Allocates and initializes an IntArray of specified size and returns it.
    • destroy(IntArray *ia): Deallocates an IntArray and sets its pointer and length to NULL and 0, respectively.

  3. IntArray Utility Functions:

    • zeroFill(IntArray dst): Fills the elements of an IntArray with zeros.
    • indexOf(const int n, const IntArray ia): Searches for an integer in an IntArray and returns its index if found, or -1 if not found.

  4. Main Logic for Curious Fractions:

    • getDigits(int n, int le, IntArray digits): Extracts the unique digits from an integer n into the IntArray digits and returns a boolean indicating if all digits are unique.
    • removeDigit(IntArray digits, size_t le, size_t idx): Removes a digit at a specified index from an IntArray digits and returns the resulting integer.

  5. Main Function:

    • The program initializes a 2D array of integer ranges (lims) and an array of integers (count) to count the curious fractions for each range.
    • It iterates through each range and for each pair of integers n and d within that range, checks if they are curious fractions:
      • If they are curious fractions (unique non-zero digits), it counts them (count) and identifies the omitted digit(s) (omitted).
      • The program prints out curious fractions and their omitted digits for each range.

  6. Output:

    • The program displays the count of curious fractions for each range, followed by a list of omitted digits and their counts.

Source code in the c programming language

#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;
}

You may also check:How to resolve the algorithm Tokenize a string step by step in the HicEst programming language
You may also check:How to resolve the algorithm MD5/Implementation step by step in the Delphi programming language
You may also check:How to resolve the algorithm Empty directory step by step in the C programming language
You may also check:How to resolve the algorithm Inverted syntax step by step in the Metafont programming language
You may also check:How to resolve the algorithm Twelve statements step by step in the Pascal programming language