| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1882 人关注过本帖
标题:真正难题来了,高手请进!!
只看楼主 加入收藏
kaikai
Rank: 1
等 级:新手上路
帖 子:236
专家分:0
注 册:2005-1-7
收藏
得分:0 

代码在下面:速度还是一般...不用做大数运算的。如果最后分母还约不到100以内,可以肯定加上一个100内的倒数也不能凑整到1的。同样的最后2个数出现之前,分母不能约到100*99以内,也可以肯定加上这1/9900不会凑成整1的... #include <stdio.h> #include <stdlib.h>

/* max: a/b + rest/k = 1 min: a/b + 1/i < (rest-1)/100

max = rest * b/(b-a) min > 100*b / (b*(rest-1) - 100*a)

a/b + 1/i = (a*i+b)/(b*i) */ #define N 9 int gcd(int a,int b) { int t; if(a>b){t=a;a=b;b=t;} while(t) { t=b%a; b=a; a=t; } return b; } int stack[10];

int dep;

void foo(int rest, int from, int a, int b) { int i; int end; static int ta,tb,tt; if (rest < dep)dep=rest; if (rest) { if (rest == 1 && b>=100) //防溢出 return; if (rest == 2 && b>=10000) return; if (rest == 3 && b>=1000000) return; if (rest == 4 && b>=100000000) return; from = max(from, 100*b/(b*(rest-1) - 100*a) + 1); end = min(101 - rest, rest*b/(b-a)); for (i = from; i <= end; i++) {

ta = a*i+b; tb = b*i; if (ta<a || tb<b || ta<0 || tb<0) { printf("%d = %d*%d+%d\n%d = %d*%d\n",ta,a,i,b,tb,b,i); getch(); }

if (ta > tb || ta == tb && rest > 1) continue; tt = gcd(ta, tb); ta /= tt; tb /= tt; stack[N - rest] = i; foo(rest - 1, i + 1, ta, tb); } } else { for (i=0;i<N;i++) printf("%d ",stack[i]); if (a == b) { printf("="); } printf("\n"); } }

int main() { int i; dep = N-1; gcd(25,28); for (i=2;i<100/N;i++) { stack[0] = i; foo(N-1, i+1, 1, i); } printf("done %d\n",dep); getch();

return 0; }


Have you visit acm.tongji. lately?
2005-02-24 01:04
lmr
Rank: 1
等 级:新手上路
帖 子:86
专家分:0
注 册:2004-12-9
收藏
得分:0 
但是我用5个数去试运行,有答案出来,且好像有100多组的。
2005-02-24 11:48
小虎
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2004-12-24
收藏
得分:0 
我是一个初学者什么都不懂,希望大家帮助我
2005-02-24 12:16
amzyb
Rank: 1
等 级:新手上路
帖 子:76
专家分:0
注 册:2005-1-10
收藏
得分:0 

#include <stdio.h> #include <math.h> void main() { int i,j,k,l,m,n,o,p,q,r; long a[9]; long temp1,temp2,temp3; float temp4=0; temp1=0;temp2=1;temp3=0; FILE *fp; fp=fopen("data.txt","w"); for(i=1;i<=100;i++) { a[0]=i; temp4=(float)(1.0/a[0]); if(temp4<1.1) for(j=i;j<=100;j++) { a[1]=j; temp4=temp4+(float)(1.0/a[1]); if(temp4<1.1) for(k=j;k<=100;k++) { a[2]=k; temp4=temp4+(float)(1.0/a[2]); if(temp4<1.1) for(l=k;l<=100;l++) { a[3]=l; temp4=temp4+(float)(1.0/a[3]); if(temp4<1.1) for(m=l;m<=100;m++) { a[4]=m; temp4=temp4+(float)(1.0/a[4]); if(temp4<1.1) for(n=m;n<=100;n++) { a[5]=n; temp4=temp4+(float)(1.0/a[5]); if(temp4<1.1) for(o=n;o<=100;o++) { a[6]=o; temp4=temp4+(float)(1.0/a[6]); if(temp4<1.1) for(p=o;p<=100;p++) { a[7]=p; temp4=temp4+(float)(1.0/a[7]); if(temp4<1.1) for(q=p;q<=100;q++) { a[8]=q; temp4=temp4+(float)(1.0/a[8]); if(temp4<1.1&&temp4<0.9) for(r=0;r<9;r++) { temp1+=a[r]; temp2=temp2*a[r]; } for(r=0;r<9;r++) { temp3+=temp2/a[r]; } if(temp2==temp3) { fprintf(fp,"%d,%d,%d,%d,%d,%d,%d,%d,%d\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]); } temp4-=a[8]; } temp4-=a[7]; } temp4-=a[6]; } temp4-=a[5]; } temp4-=a[4]; } temp4-=a[3]; } temp4-=a[2]; } temp4-=a[1]; } temp4-=a[0]; }

} 只是表达我的想法,也没有算出最后的结果! 还是太复杂了!

2005-02-24 15:46
simpley
Rank: 1
等 级:新手上路
帖 子:262
专家分:0
注 册:2005-2-23
收藏
得分:0 
刚进这个论坛时见到这个题,那时才学C,对此不敢问津,现在终于可以会做了.
用的还是穷举原理.找出7383个解.如:
2,3,12,45,70,78,84,90,91
4,6,7,8,10,12,14,28,40
我用计算器通分验证,完全正确

myQQ::445750010
2005-05-25 15:06
musicml
Rank: 1
等 级:新手上路
帖 子:273
专家分:0
注 册:2005-4-2
收藏
得分:0 
值得研究!!!!

Every thing is possible.
2005-05-26 23:18
musicml
Rank: 1
等 级:新手上路
帖 子:273
专家分:0
注 册:2005-4-2
收藏
得分:0 
顶!
以防沉;1

Every thing is possible.
2005-05-28 01:19
快速回复:真正难题来了,高手请进!!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.101451 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved