MATLAB题目：将最简真分数按照升序排列考虑分数n/d,其中n和d是正整数.如果n

Question

MATLAB题目：将最简真分数按照升序排列
考虑分数 n/d,其中n 和 d 是正整数.如果 n

Answer 1

如果n/d是小于3/7的一个最间真分数
那么它和3/7的差就是 3/7-n/d=(3d-7n)/(7d)
寻找最左边第一个真分数,就是寻找这个差最小的一个真分数
由于n和d都是整数,所以要这个差最小就是要分子最小,分母最大
分子最小只能是1
所以题目变为
在一百万的范围内寻找一个最大的数d作为分母
以及一个分子n,使得n和d互质且 3d-7n=1
tic
N=1e6;
for d=[N:-1:8 6:-2:1]
n=(3*d-1)/7;
if n==floor(n)&&gcd(n,d)==1
break;
end
end
toc
disp([n d]);
Elapsed time is 0.023465 seconds.
428570 999997
瞬间出结果