How to resolve the algorithm Set of real numbers step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Set of real numbers step by step in the C programming language

Table of Contents

Problem Statement

All real numbers form the uncountable set ℝ. Among its subsets, relatively simple are the convex sets, each expressed as a range between two real numbers a and b where a ≤ b. There are actually four cases for the meaning of "between", depending on open or closed boundary: Note that if a = b, of the four only [a, a] would be non-empty. Task Implementation notes Optional work |sin(π x)| > 1/2 is the same as n + 1/6 < x < n + 5/6 for all integers n; your program does not need to derive this by itself.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Set of real numbers step by step in the C programming language

This C program defines a custom data structure called RealSet to represent real number sets and provides functions to create, modify, and perform set operations on these sets. It also includes a main function to demonstrate the usage of these functions.

Here's a breakdown of the code:

  • struct RealSet:

    • Represents a real number set with the following members:
      • contains: A function pointer that determines if a given number is contained within the set.
      • left, right: Pointers to other RealSet objects for set operations like intersection, union, and subtraction.
      • low, high: The lower and upper bounds of the set.
    • In the program, there are different implementations of contains for different types of sets: closed, left-open, right-open, and both-open.

  • RangeType:

    • An enumeration to specify the type of a set:
      • CLOSED: Both lower and upper bounds are included.
      • LEFT_OPEN: Lower bound is not included, but upper bound is.
      • RIGHT_OPEN: Lower bound is included, but upper bound is not.
      • BOTH_OPEN: Neither lower nor upper bound is included.

  • length function:

    • Calculates the length of the set by iterating through it with a small interval and counting the number of points that are contained within it.

  • empty function:

    • Determines if the set is empty by checking the length or if the lower and upper bounds are equal and the set is not empty.

  • makeSet function:

    • Creates a new RealSet with the given bounds and type.

  • makeIntersect, makeUnion, makeSubtract functions:

    • Create new RealSet objects that represent the intersection, union, and subtraction of two given sets.

  • main function:

    • Creates multiple RealSet objects and demonstrates set operations on them.
    • For each set operation (union, intersection, subtraction), the function checks if a particular number (0, 1, or 2) is contained in the resulting set.

  • contains functions:

    • These are static helper functions that implement the contains logic for different types of sets: closed, left-open, right-open, and both-open.

The program effectively demonstrates how to create and manipulate real number sets and perform set operations like intersection, union, and subtraction. It uses function pointers to achieve polymorphism, allowing different implementations of the contains function for different set types.

Source code in the c programming language

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct RealSet {
    bool(*contains)(struct RealSet*, struct RealSet*, double);
    struct RealSet *left;
    struct RealSet *right;
    double low, high;
};

typedef enum {
    CLOSED,
    LEFT_OPEN,
    RIGHT_OPEN,
    BOTH_OPEN,
} RangeType;

double length(struct RealSet *self) {
    const double interval = 0.00001;
    double p = self->low;
    int count = 0;

    if (isinf(self->low) || isinf(self->high)) return -1.0;
    if (self->high <= self->low) return 0.0;

    do {
        if (self->contains(self, NULL, p)) count++;
        p += interval;
    } while (p < self->high);
    return count * interval;
}

bool empty(struct RealSet *self) {
    if (self->low == self->high) {
        return !self->contains(self, NULL, self->low);
    }
    return length(self) == 0.0;
}

static bool contains_closed(struct RealSet *self, struct RealSet *_, double d) {
    return self->low <= d && d <= self->high;
}

static bool contains_left_open(struct RealSet *self, struct RealSet *_, double d) {
    return self->low < d && d <= self->high;
}

static bool contains_right_open(struct RealSet *self, struct RealSet *_, double d) {
    return self->low <= d && d < self->high;
}

static bool contains_both_open(struct RealSet *self, struct RealSet *_, double d) {
    return self->low < d && d < self->high;
}

static bool contains_intersect(struct RealSet *self, struct RealSet *_, double d) {
    return self->left->contains(self->left, NULL, d) && self->right->contains(self->right, NULL, d);
}

static bool contains_union(struct RealSet *self, struct RealSet *_, double d) {
    return self->left->contains(self->left, NULL, d) || self->right->contains(self->right, NULL, d);
}

static bool contains_subtract(struct RealSet *self, struct RealSet *_, double d) {
    return self->left->contains(self->left, NULL, d) && !self->right->contains(self->right, NULL, d);
}

struct RealSet* makeSet(double low, double high, RangeType type) {
    bool(*contains)(struct RealSet*, struct RealSet*, double);
    struct RealSet *rs;

    switch (type) {
    case CLOSED:
        contains = contains_closed;
        break;
    case LEFT_OPEN:
        contains = contains_left_open;
        break;
    case RIGHT_OPEN:
        contains = contains_right_open;
        break;
    case BOTH_OPEN:
        contains = contains_both_open;
        break;
    default:
        return NULL;
    }

    rs = malloc(sizeof(struct RealSet));
    rs->contains = contains;
    rs->left = NULL;
    rs->right = NULL;
    rs->low = low;
    rs->high = high;
    return rs;
}

struct RealSet* makeIntersect(struct RealSet *left, struct RealSet *right) {
    struct RealSet *rs = malloc(sizeof(struct RealSet));
    rs->contains = contains_intersect;
    rs->left = left;
    rs->right = right;
    rs->low = fmin(left->low, right->low);
    rs->high = fmin(left->high, right->high);
    return rs;
}

struct RealSet* makeUnion(struct RealSet *left, struct RealSet *right) {
    struct RealSet *rs = malloc(sizeof(struct RealSet));
    rs->contains = contains_union;
    rs->left = left;
    rs->right = right;
    rs->low = fmin(left->low, right->low);
    rs->high = fmin(left->high, right->high);
    return rs;
}

struct RealSet* makeSubtract(struct RealSet *left, struct RealSet *right) {
    struct RealSet *rs = malloc(sizeof(struct RealSet));
    rs->contains = contains_subtract;
    rs->left = left;
    rs->right = right;
    rs->low = left->low;
    rs->high = left->high;
    return rs;
}

int main() {
    struct RealSet *a = makeSet(0.0, 1.0, LEFT_OPEN);
    struct RealSet *b = makeSet(0.0, 2.0, RIGHT_OPEN);
    struct RealSet *c = makeSet(1.0, 2.0, LEFT_OPEN);
    struct RealSet *d = makeSet(0.0, 3.0, RIGHT_OPEN);
    struct RealSet *e = makeSet(0.0, 1.0, BOTH_OPEN);
    struct RealSet *f = makeSet(0.0, 1.0, CLOSED);
    struct RealSet *g = makeSet(0.0, 0.0, CLOSED);
    int i;

    for (i = 0; i < 3; ++i) {
        struct RealSet *t;

        t = makeUnion(a, b);
        printf("(0, 1]   union   [0, 2) contains %d is %d\n", i, t->contains(t, NULL, i));
        free(t);

        t = makeIntersect(b, c);
        printf("[0, 2) intersect (1, 2] contains %d is %d\n", i, t->contains(t, NULL, i));
        free(t);

        t = makeSubtract(d, e);
        printf("[0, 3)     -     (0, 1) contains %d is %d\n", i, t->contains(t, NULL, i));
        free(t);

        t = makeSubtract(d, f);
        printf("[0, 3)     -     [0, 1] contains %d is %d\n", i, t->contains(t, NULL, i));
        free(t);

        printf("\n");
    }

    printf("[0, 0] is empty %d\n", empty(g));

    free(a);
    free(b);
    free(c);
    free(d);
    free(e);
    free(f);
    free(g);

    return 0;
}

You may also check:How to resolve the algorithm Stem-and-leaf plot step by step in the J programming language
You may also check:How to resolve the algorithm Wagstaff primes step by step in the Julia programming language
You may also check:How to resolve the algorithm Goldbach's comet step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Knapsack problem/Unbounded step by step in the Forth programming language
You may also check:How to resolve the algorithm Greatest subsequential sum step by step in the Mathematica / Wolfram Language programming language