project euler 73
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 d8 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 d10,000?
Answer: 5066251
我的代码：#include <stdio.h>
int gcd(int a, int b) {
if (b==0) return a;
return gcd(b, a % b);
}
int main(){
int num=0;
for (int a = 5; a <= 10000; a++) {
for (int b = a/3+1; b<=a/2; b++) {
if (gcd(a, b)==1) num++;
}
}
printf("%d\n", num);
return 0;
}
回复 1# northwolves 的帖子
有人提供了这样的代码，很快，没看明白：#include <stdio.h>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, d2, limit) +
between (n1, d1, n1 + n2, d1 + d2, limit);
}
int main ()
{
printf ("Answer: %d\n", between (1, 3, 1, 2, 10000));
return 0;
}哪位朋友帮忙解释一下，多谢 若a,b,c,d均为正整数，满足$a/b<c/d$，则$a/b<(a+c)/(b+d)<c/d$恒成立
于是，我们就可以反复迭代，。。。
再递归
直至分母大于limit 虽然递归效率低，但由于你给的第二个程序仅仅是在比较数的大小和计数增1，没有涉及到乘除法运算，所以速度还是很快的 谢谢指点。
不过如何控制分数为最简分数的机制仍是不太明白。
比如：如何将4999/9999 计算在内？ 原帖由 northwolves 于 2009-4-23 14:21 发表 http://bbs.emath.ac.cn/images/common/back.gif
有人提供了这样的代码，很快，没看明白：#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, ...
:L 这个代码也太简洁了，
我发现老外很多答案都很不同寻常，
思维跟我们很不一样。 当3被加了1次，2被加了4999次时计数增1的这一瞬间，即是把$4999/9999$考虑进去了。
至于我给的那个不等式，呵呵，应该权当辅助理解比较好。
我正在尝试去解答这个问题：
$3*x+2*y<=9999$，且x与y无大于1的公约数，那么这个方程的正整数解有多少组? 为啥我把limit设成超过6440的数，会报错运行不出来:Q: 刚才下载了C-free4.1，发现 northwolves给的代码一丝不改，就能正常运行出结果，很快。
换成Ch6.1了，也能运行出结果，但速度慢了很多 就northwolves的第一个代码，我作了一下比较，发现C-free4.1/MinGW 2.95的速度明显快些
页:
[1]
2