在古埃及,人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如:2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种,但是哪种最好呢?
首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。
如:
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种,因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
方法是采用迭代加深搜索(iterative deeping),从小到大枚举深度上限d,每次只考虑深度不超过d的结点,按照分母递增的顺序来进行扩展。
但是这样还不够,我们还开始加一些限制条件进行剪枝:
比如扩展到第m层,前m-1个数分别为E1,E2......Em-1,那么Em应该满足 a/b - 1/E1 - 1/E2 - ...... - 1/Em-1 > 1/Em,这样就确定了Em的下界
如果设定的深度上限为d,当前为第m层,那么还剩 d - m 层,第m层之后的分母应该大于Em,
所以还应该满足 a/b - 1/E1 - 1/E2 - ...... - 1/Em-1 < (1/Em) * (d -m+1),这样就确定了Em的上界
示例代码如下(分母使用栈存放的,可以改为数组):
#include<stdio.h> #include<string.h> #include<stack> using namespace std; stack<int> s; stack<int> sbest; //存放最优解 int flag; //标志当前是否得到可行解 int gcd(int m,int n) //求最大公约数 { if(!n) return m; else return gcd(n,m%n); } void minus(int &a,int &b,int c,int d) //分数相减,结果为a/b { int m,n,k; m = a*d - b*c; n = b*d; k = gcd(m,n); a = m/k; b = n/k; } int eq(int a,int b,int c,int d) //判断两个分数是否相等 { int m = a*d - b*c; if(m > 0) return 1; else if( m == 0) return 0; else return -1; } void stackCopy(stack<int>& s1,stack<int> s2) //将s2拷贝到s1中 { stack<int> buf; //中转站buf while(!s1.empty()) //将s1清空 s1.pop(); while(!s2.empty()) { buf.push(s2.top()); s2.pop(); } while(!buf.empty()) { s1.push(buf.top()); buf.pop(); } } void dfs(int a,int b,int start ,int depth) { int n; int c,d; if(depth == 0) return ; else { for(n = start;;n++) { if(eq(a,b,1,n) == 0) { s.push(n); if(!flag ||sbest.top() > s.top()) //如果当前没有解或者有更好的解 stackCopy(sbest,s); flag = 1; s.pop(); return ; } else if(eq(a,b,1,n) > 0) { if(eq(a,b,depth,n) >= 0) // a/b > 1/n * depth return ; s.push(n); c=a;d=b; minus(c,d,1,n); dfs(c,d,n+1,depth-1); s.pop(); } else continue; } } } int main() { int a,b; stack<int> buf; scanf("%d%d",&a,&b); for(int depth = 1;;depth++) { flag = 0; while(!sbest.empty()) sbest.pop(); dfs(a,b,2,depth); if(flag) break; } while(!sbest.empty()) { buf.push(sbest.top()); sbest.pop(); } while(!buf.empty()) { printf("%d ",buf.top()); buf.pop(); } scanf("%d",&a); return 0; }