fork download
copy 
  1. #include <algorithm>
  2. #include <cstdint>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. struct Fraction
  8. {
  9.     std::uint32_t Numerator;
  10. 	std::uint32_t Denominator;
  11. 	Fraction(std::uint32_t n, std::uint32_t d) : Numerator(n), Denominator(d) { }
  12. };
  13.  
  14. std::ostream& operator<<(std::ostream& os, const Fraction& f)
  15. {
  16.     os << "(" << f.Numerator << " / " << f.Denominator << ")";
  17. 	return os;
  18. }
  19.  
  20. typedef std::vector<Fraction> FareySeries;
  21.  
  22. FareySeries generate_series(std::uint32_t depth)
  23. {
  24.     std::uint32_t a = 0;
  25. 	std::uint32_t b = 1;
  26. 	std::uint32_t c = 1;
  27. 	std::uint32_t d = depth;
  28. 	FareySeries results;
  29. 	results.emplace_back(a, b);
  30. 	while (c <= depth)
  31. 	{
  32.         std::uint32_t k = (depth + b) / d;
  33. 		std::uint32_t nc = (k * c) - a;
  34. 		std::uint32_t nd = (k * d) - b;
  35. 		a = c;
  36. 		b = d;
  37. 		c = nc;
  38. 		d = nd;
  39. 		results.emplace_back(a, b);
  40. 	}
  41. 	return results;
  42. }
  43.  
  44. int main()
  45. {
  46.     const std::uint32_t DEPTH = 4;
  47. 	FareySeries series = generate_series(DEPTH);
  48. 	std::copy(series.begin(), series.end(), std::ostream_iterator<Fraction>(std::cout, "\n"));
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(0 / 1)
(1 / 4)
(1 / 3)
(1 / 2)
(2 / 3)
(3 / 4)
(1 / 1)
https://ideone.com/qQD8zg
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!