Ciąg Farey'a - błąd wyznaczania

Question

Cześć wszystkim! Podjąłem się wykonania zadania wyznaczenia ciągu Faray'a w ramach zadania ze strony szkopul.edu.pl. Link do zadania: https://szkopul.edu.pl/problemset/problem/XCivS2hfBhDPLj18nL8SJT2f/site/?key=statement .

Niestety przy sprawdzaniu pokazuje błąd (30% poprawnych). Nie rozumiem co robię nie tak. Dokonałem wielu testów na liczbach od 0 do 25 i nie znalazłem błędu. 

#include <iostream>
#include <vector>

int main(){
    int n{ 0 };
    std::cin >> n;

    std::vector<int>lastIndex;

    lastIndex.push_back(0);
    lastIndex.push_back(1);
    for (int i = 2; i <= n; i++)
        lastIndex.push_back(1);

    std::cout << "0/1" << " ";

    bool isDone = false;
    // i/x
    while (isDone == false) {
        for (int x = n; x > 1; x--) {
            int newLastIndex{ lastIndex[x] };
            for (int i = lastIndex[x]; i < x; i++) {
                if (x!= n && (static_cast<long double>(i) / static_cast<long double>(x)) > (static_cast<long double>(lastIndex[n]) / static_cast<long double>(n))){
                    goto next;
                }
                else if((static_cast<long double>(i) / static_cast<long double>(x)) > (static_cast<long double>(lastIndex[(x-1)]) / static_cast<long double>(x-1))) {
                    goto next;
                }

                if ((x % i != 0 || i == 1)) {
                    std::cout << i << "/" << x << " ";
                }
                newLastIndex++;
            }
            next:
            lastIndex[x] = newLastIndex;
        }

        isDone = true;

        for (int i = 2; i <= n; i++) {
            if (lastIndex[i] != i)
                isDone = false;
        }
    }

    std::cout << "1/1" << " ";

    return 0;
}

Z góry dziękuję za wszelkie sugestie .

Answer 1

Masz tutaj odpowiedzi Twojego programu i mojego, który wszedł na 100 pkt. Porównaj je sobie, jest trochę różnic LINK.  pop.txt to mój program, res.txt to Twój, każda linia to następne wywołanie programu od n=3 do 1000

Answer 2

Dla n = 7 masz błędny wynik:

0/1 1/7 1/6 1/5 1/4 2/7 2/5 1/3 3/7 1/2 4/7 3/5 2/3 4/6 5/7 3/4 4/5 5/6 6/7 1/1 
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3     5/7 3/4 4/5 5/6 6/7 1/1

1/3 < 2/5
4/6 = 2/3

Porównaj ułamki bez konwersji do long double (strata dokładności wyniku). Staraj się nie używać goto. Przerwij pętlę instrukcją break.

Comments

Wówczas dochodzi do automatycznej nieplanowanej konwersji typów na tym int. Zwiększa to jeszcze bardziej niedokładność.

PS: Masz rację, nie wiem jak mi te 4/6 uciekły :)

---

Porównaj ułamki bez dzielenia i konwersji do typu zmiennoprzecinkowego.