Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted
m (Phix/mpfr)
m (Reformatted to reduce line count)
Line 335: Line 335:
typedef boost::multiprecision::cpp_int integer;
typedef boost::multiprecision::cpp_int integer;


integer mod(const integer& x, const integer& y)
integer mod(const integer& x, const integer& y) {
{
return ((x % y) + y) % y;
return ((x % y) + y) % y;
}
}


size_t count_digits(const integer& i)
size_t count_digits(const integer& i) {
{
std::ostringstream os;
std::ostringstream os;
os << i;
os << i;
Line 347: Line 345:
}
}


std::string integer_to_string(const integer& i)
std::string integer_to_string(const integer& i) {
{
const int max_digits = 20;
const int max_digits = 20;
std::ostringstream os;
std::ostringstream os;
os << i;
os << i;
std::string s = os.str();
std::string s = os.str();
if (s.length() > max_digits)
if (s.length() > max_digits) {
{
s = s.substr(0, max_digits/2) + "..." + s.substr(s.length()-max_digits/2);
s = s.substr(0, max_digits/2) + "..." + s.substr(s.length()-max_digits/2);
}
}
Line 360: Line 356:
}
}


void egyptian(integer x, integer y, std::vector<integer>& result)
void egyptian(integer x, integer y, std::vector<integer>& result) {
{
result.clear();
result.clear();
while (x > 0)
while (x > 0) {
{
integer z = (y + x - 1)/x;
integer z = (y + x - 1)/x;
result.push_back(z);
result.push_back(z);
Line 372: Line 366:
}
}


void print_egyptian(const std::vector<integer>& result)
void print_egyptian(const std::vector<integer>& result) {
{
if (result.empty())
if (result.empty())
return;
return;
Line 383: Line 376:
}
}


void print_egyptian(integer x, integer y)
void print_egyptian(integer x, integer y) {
{
std::cout << "Egyptian fraction for " << x << "/" << y << ": ";
std::cout << "Egyptian fraction for " << x << "/" << y << ": ";
if (x > y)
if (x > y) {
{
std::cout << "[" << x/y << "] ";
std::cout << "[" << x/y << "] ";
x = x % y;
x = x % y;
Line 396: Line 387:
}
}


void show_max_terms_and_max_denominator(const integer& limit)
void show_max_terms_and_max_denominator(const integer& limit) {
{
size_t max_terms = 0;
size_t max_terms = 0;
integer max_terms_numerator, max_terms_denominator;
integer max_terms_numerator, max_terms_denominator;
Line 405: Line 395:
std::vector<integer> max_denominator_result;
std::vector<integer> max_denominator_result;
std::vector<integer> result;
std::vector<integer> result;
for (integer b = 2; b < limit; ++b)
for (integer b = 2; b < limit; ++b) {
⚫
for (integer a = 1; a < b; ++a) {
{
⚫
for (integer a = 1; a < b; ++a)
{
egyptian(a, b, result);
egyptian(a, b, result);
if (result.size() > max_terms)
if (result.size() > max_terms) {
{
max_terms = result.size();
max_terms = result.size();
max_terms_result = result;
max_terms_result = result;
Line 418: Line 405:
}
}
integer largest_denominator = result.back();
integer largest_denominator = result.back();
if (largest_denominator > max_denominator)
if (largest_denominator > max_denominator) {
{
max_denominator = largest_denominator;
max_denominator = largest_denominator;
max_denominator_result = result;
max_denominator_result = result;
Line 436: Line 422:
}
}


int main()
int main() {
{
print_egyptian(43, 48);
print_egyptian(43, 48);
print_egyptian(5, 121);
print_egyptian(5, 121);
Retrieved from "https://rosettacode.org/wiki/Greedy_algorithm_for_Egyptian_fractions"