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. }
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>
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. }
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

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的速度明显快些