Как преобразовать a/b` в сумму чисел вида `1/n`?

175

13 июня 2019, 21:50

Задача: преобразовать a/b в сумму чисел вида 1/n. Например, когда a=3 и b=7, то программа должна вывести 3/7 = 1/3 + 1/11 + 1/231.

Алгоритм я-то уже придумал, но никак не могу написать.

Сам алгоритм:

если a>b, то надо запомнить целое число, например, если a=10 и b=7, то надо довести до 3/7 и запомнить 1 как целое число.

Если a < b, то всё нормально и начинается цикл for. В нем i = 2 и оно должно доходить до значении b. (После этого нет никакого смысла проверять.) Берём b и делим на i. Если значение меньше значения a, то i становится на 1 больше. И так продолжается до тех пор, пока a > b/i. После того как найдется первое такое число, оно запоминается (то есть запоминается i) для вывода на экран )(i = 3, то в консоль надо вывести 1/3+. Потом выделяется это значение к начальному и начинается всё сначало, пока а не будет равно 1. (Пример: было 3/7 и становится 3/7 - 1/3 = 2/21, а присваивается значение 2, а b - значение 21)

мои необыкновенный код:

#include <iostream>
using namespace std;
int main(){
int a;
int b;
int c;
float d;
int k;
int g;
int e [k];  
cout << "значение а";
cin >>  a;
cout << "значение б";
cin >>  b;
if( a > b ){
    c = a / b;
    b = a - (b*c);
    return c, b;
}  else
for( int i = 2 ; i++ ; i >= b ){
    while(a>d){
        d = b / i;
    }
    int f = b;
    b = b * i;
    a = ( (b/f) * a ) - (b/i);
    e [k] = i;
    k = k+1;
}
while(e[k]>0){
    cout << "1/+" << e[k];
    k++;
}
}

Answer 1

Если я не ошибаюсь, вы пытаетесь описать алгоритм Фибоначчи для египетских дробей?

Я его "на коленке" реализовал примерно как

void egypt(unsigned long long a, unsigned long long b)
{
    if (unsigned long long g = gcd(a,b); g != 1) { a/=g; b/=g;}
    if (a > b)
    {
        cout << a/b;
        a %= b;
        if (a == 0)
        {
            cout << endl;
            return;
        }
        else
        {
            cout << " + ";
            egypt(a,b);
        }
    }
    else if (a == 1)
    {
        cout << "1/" << b << endl;
        return;
    }
    else
    {
        unsigned long long n = (b+a)/a;
        cout << "1/" << n << " + ";
        egypt(a*n-b,b*n);
    }
}

Полный код - https://ideone.com/IQY14q

Но учтите, что это далеко не оптимальный алгоритм, и в плохих вариантах быстро выходит даже за рамки unsigned long long - как в последнем примере по указанному адресу, разложение неверное - последняя дробь в unsigned long long не помещается :(

Answer 2

Разложение на египетские дроби методом Фибоначчи на Python (длинная арифметика встроенная), код не проверяет, что дробь правильная.

def egy(p, q):
    res = []
    while p > 0:
        den = (q + p - 1) // p
        res.append(den)
        rem = (-q) % p
        p, q = rem, den * q
    return res
print(egy(3,7))
print(egy(7,15))
print(egy(5,121))
[Dbg]>>> 
[3, 11, 231]
[3, 8, 120]
[25, 757, 763309, 873960180913, 1527612795642093418846225]