2010-1072

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目的大意就是用分子为1的分数来逼近一个分数，分子为A，分母为B，逼近的各个分数前符号依次为正负，如果能在5项内取到A/B则输出各项分母，如果不能，输出Too complex。

因为要求的项数较少，所以可以采用深搜来做，利用等式 A/B = 1/i - (B-i*A)/B,枚举该层的i后把 B-i*A 和 B 继续深搜， 如果搜到 B%A==0 则停止深搜， 得到最小的top值。

以下是标程：

{{{
#!cpp
#include<cstdio>
#include<cstring>
using namespace std;
int top;
int ans[10];
int gcd(int n,int m)
{
    int r;
    while(m)
    {
        r = n%m;
        n = m;
        m = r;
    }
    return n;
}
bool dfs(int a,int b,int d)
{
    if(d>=top)
        return false;
    if(b%a==0)
    {
        ans[d] = b/a;
        return true;
    }
    int div = gcd(a,b);
    a /= div;
    b /= div;
    for (int i = 2; i*a<b; i++)
    if (dfs(b-i*a,b,d+1))
    {
        ans[d] = i;
        return true;
    }
    return false;
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    for (top = 1; top<=5; ++top)
    {
        memset(ans,0,sizeof(ans));
        if( dfs(a,b,0)||dfs(b-a,b,0))
        {
            for (int i = 0; ans[i]!=0; i++)
                printf("%d%c",ans[i],ans[i+1]?' ':'\n');
                break;
        }
    }
    if(top>5)
        puts("Too complex");
    }
}
}}}
by forestkeeper

题目的大意就是用分子为1的分数来逼近一个分数，分子为A，分母为B，逼近的各个分数前符号依次为正负，如果能在5项内取到A/B则输出各项分母，如果不能，输出Too complex。

因为要求的项数较少，所以可以采用深搜来做，利用等式 A/B = 1/i - (B-i*A)/B,枚举该层的i后把 B-i*A 和 B 继续深搜， 如果搜到 B%A==0 则停止深搜， 得到最小的top值。

以下是标程：

#include<cstdio>
#include<cstring>
using namespace std;
int top;
int ans[10];
int gcd(int n,int m)
{
    int r;
    while(m)
    {
        r = n%m;
        n = m;
        m = r;
    }
    return n;
}
bool dfs(int a,int b,int d)
{
    if(d>=top)
        return false;
    if(b%a==0)
    {
        ans[d] = b/a;
        return true;
    }
    int div = gcd(a,b);
    a /= div;
    b /= div;
    for (int i = 2; i*a<b; i++)
    if (dfs(b-i*a,b,d+1))
    {
        ans[d] = i;
        return true;
    }
    return false;
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
    int a,b;
    scanf("%d%d",&a,&b);
    for (top = 1; top<=5; ++top)
    {
        memset(ans,0,sizeof(ans));
        if( dfs(a,b,0)||dfs(b-a,b,0))
        {
            for (int i = 0; ans[i]!=0; i++)
                printf("%d%c",ans[i],ans[i+1]?' ':'\n');
                break;
        }
    }
    if(top>5)
        puts("Too complex");
    }
}

by forestkeeper