代码在下面：速度还是一般...不用做大数运算的。如果最后分母还约不到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?
