注册 登录
编程论坛 C++教室

贪心算法

稚梦 发布于 2016-06-20 20:23, 2909 次点击
#include"iostream"
using namespace std;
int EgyptianFraction(int a, int b, int D[20])
{
    int n = 0, j, c;
    int u=0;
    j = b;
    for (;;)
    {
        c = b / a + 1;
        if (c > 1000000000 || c < 0)return 0;
        if (c == b)c++;
        D[++n] = c;
        a = a*c - b;
        b = b*c;
        for (u = 2; u <= a; u++)
            while (a%u == 0 && b%u == 0)
                a = a / u, b = b / u;
        if (a == 1 && b != j)
        {
            D[++n] = b;
            break;
        }
    }
    return n;
}
int main()
{
    int a, b, n, i=0, D[20];
    cin >> a >> b;
    n = EgyptianFraction(a,b,D);
    if (n > 0)
    {
        cout << a << "/" << b << "=1/" << D[1];
        for (i = 2; i <= n; i++)cout << "+1/" << D[i];
        cout << endl;
    }
    return 0;
}
0 回复
1