Vijos 1308 埃及分数

描述

在古埃及，人们使用单位分数的和形如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,b0<a<b<1000),编程计算最好的表达方式。

输入：a b
输出：若干个数，自小到大排列，依次是单位分数的分母。

样例1

样例输入1

19 45 

样例输出1

5 6 18

限制

各个测试点1s

（来自https://vijos.org/p/1308）

---

这道题很明显使用搜索

（1）深搜，不知道深度

（2）广搜，保存的数据量可能会过大

（3）迭代加深，剪剪枝时间应该可以过

那就用迭代加深

不过还有一些问题:

（1）从哪开始枚举分母

　　前面剩下分数的倒数取整和前一个分母+1的最小值

　　第二个很好理解,至于第一个：

　　假设前面剩下了a/b,则用[b/a]作分母，新分数可能会比原分数大一点点

　所以可以做开始的条件

（2）结束为（最大深度-当前深度+1）*（b/a）取整

Code

  1 /**
  2  *Vijos.org        &codevs.cn
  3  *Problem#1308     Problem#1288
  4  *Accepted         Accepted
  5  *Time:528ms     741ms
  6  *Memort:564k     256k
  7  */
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstring>
 11 #define int long long
 12 #define ll long long
 13 #define _maxa,b) a>b)?a):b)
 14 using namespace std;
 15 /**
 16  *定义分数类 
 17  */
 18 typedef bool boolean;
 19 typedef class MyClass{
 20     public:
 21         int s;
 22         int m;
 23         MyClass):s0),m0){}
 24         MyClassint s,int m):ss),mm){}
 25 #undef int
 26         MyClass operator -MyClass another){
 27             MyClass result;
 28             int g=getCommonthis->m,another.s);
 29             result.m=this->m*another.m/g;
 30             result.s=this->s*another.m/g-this->m/g*another.s;
 31             int g1=getCommonresult.m,result.s);
 32             result.m/=g1;
 33             result.s/=g1;
 34             return result;
 35         }
 36         boolean empty){
 37             return m==0);
 38         }
 39         boolean operator <MyClass another){
 40             ifanother.empty)) return true;
 41             ifthis->empty)) return false;
 42             ifthis->s==another.s) return this->m>another.m;
 43             return this->s*1.0/this->m)<another.s*1.0/another.m);
 44         }
 45         boolean operator <double another){
 46             ifthis->empty)) return false;
 47             return this->s*1.0/this->m)<another;
 48         }
 49         inline int getrInt){
 50 //            ifs==0) return -1;
 51             return int)this->m/this->s);
 52         }
 53         boolean isWorkable){
 54             ifthis->empty)) return false;
 55             return m%s==0); 
 56         }
 57         void operator <<istream &in){
 58             in>>s>>m;
 59         }
 60     private:
 61         int getCommonll a,ll b){
 62             ifb==0) return a;
 63             return getCommonb,a%b);
 64         }
 65 }MyClass;
 66 MyClass maxx;
 67 int results[105];
 68 int list[105];
 69 int found = 0;
 70 
 71 /**
 72  *迭代加深 
 73  */
 74 void searchint depthLimit,int now,MyClass fs){
 75     iffs<0) return ;
 76     ifnow>depthLimit) return ;
 77     iffs.isWorkable)&&fs.m>list[now-1])&&found==0||maxx<fs)){
 78         maxx=fs;
 79         results[depthLimit]=fs.m/fs.s;
 80         memcpyresults,list,sizeofint)*depthLimit);
 81         found=depthLimit;
 82         return ;
 83     }
 84     forint i=_maxfs.getrInt),list[now-1]+1);i<=depthLimit-now+1)*fs.getrInt);i++){
 85         list[now]=i;
 86         searchdepthLimit,now+1,fs-MyClass1,i));
 87     }
 88 } 
 89 int main){
 90     MyClass q;
 91     q<<cin;
 92 //    cout<<q.getrInt);
 93     int i=1;
 94     list[0]=1;
 95     whilefound==0){
 96         searchi,1,q);
 97         i++;
 98     }
 99     forint i=1;i<=found;i++){
100         printf"%d ",results[i]);
101     }
102 }

迭代加深