Как сортировать числа, которые находятся в р/д формиат с использованием C++

Question

Дано целое положительное число n, вы должны напечатать последовательность в порядке возрастания, который состоит из фракций от 0 до 1

* Вход- 6.

Выход-0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/6, 3/5, 2/3, 3/4 , 4/5, 5/6, 1/1.

Я написал код в C++, но это не дает правильный вывод

#include<iostream> 
#include<cmath> 
#include<cstdlib> 
#include<algorithm> 
#include<set> 
using namespace std; 

long gcd(long a, long b); 

void foo(double input) 
{  

    double frac = input ; 
    const long precision = 1000000000; // This is the accuracy. 

    long gcd_ = gcd(round(frac * precision), precision); 

    long denominator = precision/gcd_; 
    long numerator = round(frac * precision)/gcd_; 
    cout << numerator << "/" << denominator <<","; 
} 

long gcd(long a, long b){ 

if (a == 0) 
     return b; 
    else if (b == 0) 
     return a; 

    if (a < b) 
     return gcd(a, b % a); 
    else 
     return gcd(b, a % b); 
} 


int main() 
{ 

    double n; 
    set<double>s; 
    int c=0; 
    cin>>n; 
    for(int i=1;i<n;i++) 
    { 
     for(int j=n;j>0;j--) 
     { 
      if(i<j) 
      { 
      s.insert((double)i/j); 
      } 


     } 
    } 
    cout<<"0/1"<<","; 
    while(!s.empty()) 
    { 
     foo(*s.begin()); 
      s.erase(s.begin()); 
    } 
    cout<<"1/1"; 

output- 0/1, 166666667/1000000000, 1/5, 1/4,333333333/1000000000, 2/5, 1/2, 3/5, 666666667/1000000000, 3/4, 4/5,833333333/1000000000,1/1

Answer 1

Я думаю, что это плохая идея попытаться пересчитать числитель и знаменатель, когда вы можете просто запомнить их.

Если вы, вместо std::set<double>, используйте std::map<double, std::pair<int, int>>, вы можете использовать ключ (double) для сортировки дроби и значение (std::pair<int, int>) для печати они.

So foo() может принимать числитель и знаменатель.

Ниже приведен полный пример

#include<map> 
#include<iostream> 

constexpr long gcd (long a, long b) 
{ return (a == 0) ? b 
        : (b == 0) ? a 
           : (a < b) ? gcd(a, b % a) 
             : gcd(b, a % b); } 

void foo (long num, long den) 
{  
    long const g { gcd(num, den) }; 

    std::cout << (num/g) << '/' << (den/g) << ", "; 
} 

int main() 
{ 
    int n; 

    std::map<double, std::pair<int, int>> m; 

    std::cin >> n; 

    for (auto i = 0 ; i < n ; ++i) 
    { 
     for (auto j = n ; j > i ; --j) 
      m.emplace(std::piecewise_construct, 
         std::forward_as_tuple(double(i)/j), 
         std::forward_as_tuple(i, j)); 
    } 

    for (auto const e : m) 
     foo(e.second.first, e.second.second); 

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

Answer 2

Это неправильный путь.

Вы должны попытаться сделать класс фракций, который хранит числитель и знаменатель и работает с ними напрямую.

Что-то, как это должно работать:

struct fraction { 
    int numerator, denominator; 
    bool operator<(const fraction& f) const { 
    return numerator*f.denominator < f.numerator*denominator; 
    } 
} 

Это просто голая вещь и должна работать для вида ввода, что у вас есть, но вы, возможно, придется специализироваться его (отрицательные числа, большие числитель и знаменатель , имея дело с разными представлениями одной и той же фракции ...)