poj1980-Unit Fraction Partition(DFS分数分解)

发布于 2019-07-24  864 次阅读


问题传送门:

题意:

给你一个分数,p/q , a , n
要求 1/x1 + 1/x2 + 1/x3 +......+ 1/xk = p/q
                                    k <= n
且 x1 * x2 * x3 * ..... * xk <= a

即把 p / q ,分解成子分数的和,
子分数的分子为 1 ,分母最大是 n ,分母累乘 <= a .
问最多有多少种分解方案。

分析:

a 最大是 12000, 并且 n 最大是7 
这一题可以用 DFS 暴力搜索出所有的分解情况。
下面代码的DFS中,cnt记录的是已经分解了几个子分数,初始是0,
prq 记录的是上一个子分数的分子,那么这一次的搜索也是从prq开始
sump,sumq记录的是目前自分子的和
如果目前子分数的和满足答案,ans++,不return,而是继续向下搜索
如果目前子分数的和超过了,跳过,继续向下搜索
如果目前子分数的和小于要求,深搜下一个子分数,cnt+1

代码:

#include <iostream>

using namespace std;

int ans, p, q, a, n;

void DFS(int cnt, int prq, int sump, int sumq, int mul)
{  
    if (cnt > n) return ;
    // 暴力枚举拆分的分数的分母
    int np, nq;
    for(int i = prq; i*mul <= a; i++)
    {
        np = sumq + i*sump;
        nq = i*sumq;
        // 如果分解的分数的和,加上当前枚举的分数已经过大了,跳过,继续下次枚举
        if (np*q > nq*p)
            continue;
        if (np*q==nq*p)
        {
            ans++;
            continue;
        }
        DFS(cnt+1, i, np, nq, mul*i);
    }
}

int main()
{
    while (cin >> p >> q >> a >> n && (p+q+a+n))
    {
        ans = 0;
        DFS(1, 1, 0, 1, 1);
        cout << ans << endl;
    }
    return 0;
}

Simple And Clear