#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 ClearMemory(Fraction* array)
{
    for (int i = 0; i < 100; i++)
        delete &array[i];
}*/

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)
{
    array[1] = *(new Fraction(1, 1, NULL));
    array[0] = *(new Fraction(0, 1, &array[1]));
    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);
                current->next = newFraction;
                array[newFractionPosition++] = *newFraction;
            }
            current = current->next;
        }
    }
}

int main()
{
    for (int i = 0; i < 10000; i++)
    {
        struct Fraction array[100] = {};
        for (int i = 0; i < 100; i++)
            array[i] = {};
        int n = 8;
        //cout << "Enter n (array size 100 elements)" << endl;
        //cin >> n;
        GetFareySequence(array, n);
        OutputFareySequence(array);
        //ClearMemory(array);
    }
}