埃及分数2

djkpengjun

                                                                                古代埃及人有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干个分子为一且分母互不相同的分数之和的形式。
问题二：
对于一个给定的分数，它可能有多种满足上述条件的表示方法（这是当然的），我们定义这样的评判标准：
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
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),编程计算最好的表达方式。
用的是所谓的IDA*搜索算法。
IDA*的基本思路
是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值
maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解。
#include
#include
const int maxdepth=100;
int  depth=0,min,cmdepth;  
//depth  :当前搜索深度－1,
//min    :所有已求解中最小的最后一个分母值,
//cmdepth:当前最大搜索深度
int  ans[maxdepth], out[maxdepth];
void find(int a,int b,int x)//a/b, 1/x，x为前一项的分母
{
if(depth>=cmdepth||x>=min) return;  
if(b%a==0){
  b/=a;
  if(b=min) return;   //分母减小的也不行
  ans[depth]=b;   
  min=b;     //因为若加数个数相同的，最小的分数越大越好。
  memcpy(out,ans,(depth+1)*sizeof(int));//存储结果
  return;
}
else{
  if(depth>=cmdepth-1)  return;
  while(a*x=b*(cmdepth-depth))//剪枝,a*x比本层上限还大
        break;
   ans[depth]=x;
   depth++;       //进入下一层搜索
   find(a*x-b,b*x,x+1);
   depth--;       //恢复现场
   x++;           //本层按分母升序遍历,基元素当然是b/a了
  }
}
return;
}
int main()
{
  int a,b;
  scanf("%d%d",&a,&b);
  min=1000000;
  //从1开始，是因为根据题目要求：加数少的比加数多的好，否则就从maxlen开始了,呵呵
  for(cmdepth=1;cmdepth
               
               
               
               
               
               
               
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104733/showart_2130991.html