#include <iostream>

using namespace std;

struct Fraction
{
    int numerator;
    int denominator;
    Fraction* next;

    Fraction(int numerator, int denominator, Fraction* next)
    {
        this->numerator = numerator;
        this->denominator = denominator;
        this->next = next;
    }

    Fraction() {}
};

void OutputFareySequence(Fraction* array)
{
    Fraction* current = &array[0];
    while (current != NULL)
    {
        cout << current->numerator << " / " << current->denominator << endl;
        current = current->next;
    }
}

void GetFareySequence(Fraction* array, int n, Fraction** memoryArray)
{
    memoryArray[0] = new Fraction(0, 1, &array[1]);
    memoryArray[1] = new Fraction(1, 1, NULL);
    array[1] = *memoryArray[1];
    array[0] = *memoryArray[0];
    int newFractionPosition = 2;
    for (int i = 2; i <= n; i++)
    {
        Fraction* current = &array[0];
        while (current->next != NULL)
        {
            if (current->denominator + current->next->denominator == i)
            {
                int newFractionNumerator = current->numerator + current->next->numerator;
                int newFracTionDenominator = current->denominator + current->next->denominator;
                Fraction* newFraction = new Fraction(newFractionNumerator, newFracTionDenominator, current->next);
                memoryArray[newFractionPosition] = newFraction;
                current->next = newFraction;
                array[newFractionPosition++] = *newFraction;
            }
            current = current->next;
        }
    }
}

int main()
{
    for (int i = 0; i < 10000; i++)
    {
        struct Fraction array[10000];
        const int arraySize = sizeof(array) / sizeof(array[0]);
        Fraction* memoryArray[arraySize];
        for (int i = 0; i < 100; i++)
            memoryArray[i] = nullptr;
        int n = 10;
        //cout << "Enter n (array size 100 elements)" << endl;
        //cin >> n;
        GetFareySequence(array, n, memoryArray);
        OutputFareySequence(array);
        for (int i = 0; i < 100; i++)
            delete memoryArray[i];
    }
}