project euler 73

northwolves

Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d  8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d  10,000?

Answer: 5066251  

我的代码：

1. #include <stdio.h>
   
2. int gcd(int a, int b) {
   
3.       if (b==0) return a;
   
4.       return gcd(b, a % b);
   
5.     }
   
6. 
   
7. int main(){
   
8. int num=0;
   
9.         for (int a = 5; a <= 10000; a++) {
   
10.             for (int b = a/3+1; b<=a/2; b++) {
    
11.                if (gcd(a, b)==1) num++;
    
12. }
    
13. }
    
14.     printf("%d\n", num);
    
15.     return 0;
    
16. }
    

复制代码

northwolves

有人提供了这样的代码，很快，没看明白：

1. #include <stdio.h>
   
2. 
   
3. int between (int n1, int d1, int n2, int d2, int limit)
   
4. {
   
5.     if (d1 + d2 > limit)        return 0;
   
6.     return 1 + between (n1 + n2, d1 + d2, n2, d2, limit) +
   
7.                between (n1, d1, n1 + n2, d1 + d2, limit);
   
8. }
   
9. 
   
10. int main ()
    
11. {
    
12.     printf ("Answer: %d\n", between (1, 3, 1, 2, 10000));
    
13.     return 0;
    
14. }

复制代码

哪位朋友帮忙解释一下，多谢

wayne

若a,b,c,d均为正整数，满足$a/b<c/d$，则$a/b<(a+c)/(b+d)<c/d$恒成立

于是，我们就可以反复迭代，。。。
再递归
直至分母大于limit

wayne

虽然递归效率低，但由于你给的第二个程序仅仅是在比较数的大小和计数增1，没有涉及到乘除法运算，所以速度还是很快的

northwolves

谢谢指点。
不过如何控制分数为最简分数的机制仍是不太明白。
比如：如何将4999/9999 计算在内？

winxos

原帖由 northwolves 于 2009-4-23 14:21 发表
有人提供了这样的代码，很快，没看明白：#include

int between (int n1, int d1, int n2, int d2, int limit)
{
    if (d1 + d2 > limit)        return 0;
    return 1 + between (n1 + n2, d1 + d2, n2, ...

这个代码也太简洁了，
我发现老外很多答案都很不同寻常，
思维跟我们很不一样。

wayne

当3被加了1次，2被加了4999次时计数增1的这一瞬间，即是把$4999/9999$考虑进去了。

至于我给的那个不等式，呵呵，应该权当辅助理解比较好。

我正在尝试去解答这个问题：

$3*x+2*y<=9999$，且x与y无大于1的公约数，那么这个方程的正整数解有多少组?

wayne

为啥我把limit设成超过6440的数，会报错运行不出来

wayne

刚才下载了C-free4.1，发现 northwolves给的代码一丝不改，就能正常运行出结果，很快。

换成Ch6.1了，也能运行出结果，但速度慢了很多

wayne

就northwolves的第一个代码，我作了一下比较，发现C-free4.1/MinGW 2.95的速度明显快些