注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

求两分数间分母最小的分数  

2010-09-02 22:32:36|  分类: 其他 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
膜拜了下09金斌大牛的文章,欧几里得的想法博大精深,只要出现辗转相除的形式就能说明算法log级别的了
#include<cstdio>
int a,b,c,d,k;
int x,y;
char cc;
int gcd(int a,int b){
if(b==0)
return a;
return gcd(b,a%b);
}
void solve(int a,int b,int c,int d,int &x,int &y,int mark){
//printf("a=%d b=%d c=%d d=%d %d %d\n",a,b,c,d,a/b,c/d);
if(b==0){
x=0;
y=1;
return ;
}
if(a/b<c/d){
if(a%b==0&&mark)
x=a/b;
else x=a/b+1;
y=1;
return ;
}
solve(d,c%d,b,a%b,x,y,(mark+1)%2);
int tmp=y;
y=x;
x=x*(a/b)+tmp;
d=gcd(x,y);
x/=d;
y/=d;
}
int main(){
while(cc=getchar(),cc!='-'){
getchar();
a=0;
b=1;
while(cc=getchar(),cc>='0'&&cc<='9'){
a=a*10+cc-'0';
b=b*10;
}
c=a*10+5;
d=b*10;
a=a*10-5;
b=b*10;
solve(d,c,b,a,x,y,0);
printf("Case %d: %d\n",++k,x);
}
return 0;
}
  评论这张
 
阅读(411)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018