题目71：将最简真分数按照升序排列
Ordered fractionsConsider the fraction, n/d, where n and d are positive integers. If n<d 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 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
题目：
考虑分数 n/d, 其中 n 和 d 是正整数。如果 n<d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。
如果我们将 d ≤ 8 的最简真分数按照大小的升序列出来，我们得到：
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
可以看出 2/5 是 3/7 左边的第一个分数。
如果将 d ≤ 1,000,000 的真分数按照大小升序列出，3/7 左边第一个分数的分子是多少？ 本帖最后由 jerryxjr1220 于 2017-10-12 10:42 编辑
i=428570, j=999997
most, mosti, mostj = 0,0,0
for j in range(1,1000001):
i = j*3//7
if i/j < 3/7:
if most < i/j:
most = i/j
mosti = i
mostj = j
print (f'i={mosti},j={mostj}') from fractions import Fraction
import math
def Prime(x):
if x>1:
if x==2:
return True
if x%2==0:
return False
for i in range(3,int(math.sqrt(x)+1),2):
if x%i==0:
return False
return True
return False
def Dig(x):
list1=[]
if Prime(x):
list1.append(x)
else:
for i in range(2,int(math.sqrt(x)+1)):
if x%i == 0:
list1.extend()
return list1
def Hcf(x,y):
if x!=y:
if x==1:
return True
for each in Dig(y):
if x%each == 0:
return False
return True
list2 =
for i in range(4,428571):
y = int(7*i/3)+1
while True:
if Hcf(i,y):
list2.append(Fraction(i,y))
break
else:
y += 1
list2.sort()
print(list2[-1])
结果：428570/999997
答案是428570 一如既往得慢 # encoding:utf-8
# 最接近3/7的真分数 分母<1000000
from time import time
from math import sqrt
def getPrimes(n):
primes = * n
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i * i, n, i):
primes = False
return
def findPrimeFactors(n, l_pr, s_pr):
if n in s_pr:
return
sqr_n = int(sqrt(n))
result = list()
for pr in l_pr:
if n % pr == 0:
result.append(pr)
result.extend(findPrimeFactors(int(n / pr), l_pr, s_pr))
break
if pr > sqr_n:
break
return result
def euler071(N=1000000):
l_primes = getPrimes(N)
s_pr = set(l_primes)
l_pr =
maxfz, maxfm = int(3 / 7 * N), N
maxrt, a, b = 0, 0, 0
for i in range(maxfz, 2, -1):
for j in range(int(i * 7 / 3), maxfm):
t = i / j
if t < 3 / 7 :# 满足题目条件
if t > maxrt:# 比已找到的更接近3/7
s_i = set(findPrimeFactors(i, l_pr, s_pr))
s_j = set(findPrimeFactors(j, l_pr, s_pr))
if not(s_i & s_j):# 没有公共的质数因子
maxrt, a, b = t, i, j
else:
break
print(maxrt, a, b)
if __name__ == '__main__':
start = time()
euler071()
print('cost %.6f sec' % (time() - start))
0.42857128571385716 428570 999997
cost 1.133000 sec 改写了一下，用的matlab，
成功解决
结果是
428570 999997
时间已过 0.053004 秒。
>> 本帖最后由 永恒的蓝色梦想 于 2021-1-31 14:55 编辑
min_difference = 1
min_numerator = 0
three_div_seven = 3 / 7
for denominator in range(1000000, 0, -1):
numerator = 3 * denominator // 7
difference = three_div_seven - numerator / denominator
if difference and difference < min_difference:
min_difference = difference
min_numerator = numerator
print(min_numerator) 428570
Process returned 0 (0x0) execution time : 649.486 s
Press any key to continue.
效率极低……求指点
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int M = 1e5;
const double ub = 3.0/7;
int ct = 0;
bool prime;
int factor;
set<int> fac_n;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++ct] = i;
for (int j = 1;j <= ct && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
bool co_prime(int x,int y){//x < y
if (x == 1) return true;
if (prime) return true;
if (prime && y % x)return true;
if (y == x*2 + 1) return true;
for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
if (y % *it == 0) return false;
}
return true;
}
void parse(int x,set<int> & s){
for (int i = 1;x != 1;i++){
int t = factor;
while(x % t == 0) {s.insert(t); x /= t;}
}
}
int main(){
double lb = 1.0/3;
int ans;
euler_sieve();
for (int d = 4;d <= M;d++){
for (int n = 1;n < (d+1)/2;n++){
double t = (double)n / d;
if (lb < t && t < ub){
fac_n.clear();
parse(n,fac_n);
if (co_prime(n,d) ){lb = t; ans = n;}
}
}
}
cout << ans << endl;
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2020-8-30 19:05 编辑
#include<iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
long double min_difference = 1, difference;
unsigned long long denominator, result = 0, numerator;
for (denominator = 1; denominator <= 1000000; denominator++) {
numerator = 3 * denominator / 7;
difference = 3.0L / 7 - (long double)numerator / denominator;
if (difference && difference < min_difference) {
min_difference = difference;
result = numerator;
}
}
cout << result << endl;
return 0;
} debuggerzh 发表于 2020-8-29 18:33
428570
Process returned 0 (0x0) execution time : 649.486 s
第6行应该是1e6，调试忘记改了 永恒的蓝色梦想 发表于 2019-8-4 09:47
感谢大神的思路！以下是改进版本：
428570
Process returned 0 (0x0) execution time : 0.248 s
Press any key to continue.
只枚举分母，计算最接近结果的分子，大大减少循环次数
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int M = 1e6;
const double ub = 3.0/7;
int ct = 0;
bool prime;
int factor;
set<int> fac_n;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++ct] = i;
for (int j = 1;j <= ct && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
bool co_prime(int x,int y){//x < y
if (x == 1) return true;
if (prime) return true;
if (prime && y % x)return true;
if (y == x*2 + 1) return true;
for (set<int>::iterator it = fac_n.begin();it != fac_n.end();++it){
if (y % *it == 0) return false;
}
return true;
}
void parse(int x,set<int> & s){
for (int i = 1; ;i++){
int t = factor;
while(x % t == 0) {s.insert(t); x /= t;}
if (x == 1 || prime) break;
}
if (prime) s.insert(x);
}
int main(){
double lb = 1.0/3;
int ans;
euler_sieve();
for (int d = 4;d <= M;d++){
int n = (int)(d*3 - 1) / 7;
double t = (double)n / d;
if (lb < t && t < ub){
fac_n.clear();
parse(n,fac_n);
if (co_prime(n,d) ){lb = t; ans = n;}
}
}
cout << ans << endl;
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2020-8-30 11:39 编辑
debuggerzh 发表于 2020-8-30 11:26
感谢大神的思路！以下是改进版本：
428570
并不需要判断质数。 本帖最后由 guosl 于 2022-1-11 19:52 编辑
/*
428570
0.161768
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n = 0, d = 1;
for (int i = 2; i <= 1000000; ++i)
{
for (int j = (3 * i + 6) / 7; 999 * j >= 428 * i; --j)
{
if (7 * j >= 3 * i)
continue;
if (n*i < j*d)
{
n = j;
d = i;
}
}
}
cout << n << endl;
return 0;
} 本帖最后由 guosl 于 2022-1-12 08:20 编辑
这道题我们先从数学上来讨论一下：对m<n的真分数，我们有以下事实：
1. m/n>m/(n+1)
2. m/n>(m-1)/n
3. m/n>(m-1)/(n-1)
4. m/(n+1) > (m-1)/n , m/(n+1) > (m-1)/(n-1) ,(m-1)/(n-1)>(m-1)/n。总结就是： m/n>m/(n+1) > (m-1)/(n-1)>(m-1)/n，当m/n=3/7时。
在本题中3/7=428571/999999，那么我们可以通过分母加1，分子减1，或分子与分母同时减1，或分子分母同时加1来调整与3/7的距离。但这些调整都预示着分子就在428571的附件，分母就在999999的附近。
为了省却调整的不确定性，我们干脆就在分母d是999990~1000000之间枚举，而分子就是428560~3*d/7之间枚举。
/*
答案：428570
*/
#include <iostream>
using namespace std;
int gcd(int x, int y)
{
if (y == 0)
return x;
int z = x % y;
while (z != 0)
{
x = y;
y = z;
z = x % y;
}
return y;
}
int main(void)
{
int n0 = 0, d0 = 1;
for (int d = 999990; d <= 1000000; ++d)
{
for (int n = 428560; 7 * n < 3 * d; ++n)
{
long long l1 = n0, l2 = d0;
l1 *= d;
l2 *= n;
if (l1 < l2)
{
n0 = n;
d0 = d;
}
}
}
cout << n0 / gcd(n0, d0) << endl;
return 0;
} 应该是测不到时间，毕竟连循环都没有
# 3/7约等于m/n
# 3n-7m=1 ==> 3/7=(m+1/7)/n
# 3n=7m+1 ==> 3n%7=1
# n%7=5
d=1000000
n=d//7*7+5
if n>d:
n=n-7
m=(3*n-1)//7
print(m) 本题等效于寻找n/m,使得3/7-n/m最小
3/7-n/m＝(３m-7n)/7m
使得分子＝１，m尽可能大即可
时间：<0.001ms
int test71 (int n)
{
for (int i = n; i >0; i--)
{
if(i * 3% 7==1)
return i * 3/ 7;
}
} if __name__ == '__main__':
import datetime, time
print(datetime.datetime.now().strftime('%F %T'))
start = time.time()
N = 1000000
m = (N - 5) // 7
print(f'Problem 71 : {m * 3 + 2}, {m * 7 + 5}')
print("用时 %.6f 秒" % (time.time() - start))
2024-04-23 21:32:18
Problem 71 : 428570, 999997
用时 0.000000 秒
页:
[1]