Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 11:17, 31 May 2020
, 4 years agoReformatted to reduce line count
m (Phix/mpfr) |
m (Reformatted to reduce line count) |
||
Line 335:
typedef boost::multiprecision::cpp_int integer;
integer mod(const integer& x, const integer& y) {
return ((x % y) + y) % y;
}
size_t count_digits(const integer& i) {
std::ostringstream os;
os << i;
Line 347 ⟶ 345:
}
std::string integer_to_string(const integer& i) {
const int max_digits = 20;
std::ostringstream os;
os << i;
std::string s = os.str();
if (s.length() > max_digits) {
s = s.substr(0, max_digits/2) + "..." + s.substr(s.length()-max_digits/2);
}
Line 360 ⟶ 356:
}
void egyptian(integer x, integer y, std::vector<integer>& result) {
result.clear();
while (x > 0) {
integer z = (y + x - 1)/x;
result.push_back(z);
Line 372 ⟶ 366:
}
void print_egyptian(const std::vector<integer>& result) {
if (result.empty())
return;
Line 383 ⟶ 376:
}
void print_egyptian(integer x, integer y) {
std::cout << "Egyptian fraction for " << x << "/" << y << ": ";
if (x > y) {
std::cout << "[" << x/y << "] ";
x = x % y;
Line 396 ⟶ 387:
}
void show_max_terms_and_max_denominator(const integer& limit) {
size_t max_terms = 0;
integer max_terms_numerator, max_terms_denominator;
Line 405 ⟶ 395:
std::vector<integer> max_denominator_result;
std::vector<integer> result;
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);
if (result.size() > max_terms) {
max_terms = result.size();
max_terms_result = result;
Line 418 ⟶ 405:
}
integer largest_denominator = result.back();
if (largest_denominator > max_denominator) {
max_denominator = largest_denominator;
max_denominator_result = result;
Line 436 ⟶ 422:
}
int main() {
print_egyptian(43, 48);
print_egyptian(5, 121);
| |||