题目65：找出e的连分数中第100个收敛项的分子各位之和。
Convergents of eThe square root of 2 can be written as an infinite continued fraction.
The infinite continued fraction can be written,= , (2) indicates that 2 repeats ad infinitum. In a similar way,= .
It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for .
Hence the sequence of the first ten convergents forare:
1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
What is most surprising is that the important mathematical constant,
e = .
The first ten terms in the sequence of convergents for e are:
2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
The sum of digits in the numerator of theconvergent is 1+4+5+7=17.
Find the sum of digits in the numerator of theconvergent of the continued fraction for e.
题目：
2的平方根可以写作无限连分数：
这个无限连分数可以写作，= , (2) 表示2无限循环出现。类似的， = 。
事实证明平方根的连分数序列提供了最好的有理数近似值。让我们考虑 的收敛项：
因此的收敛项中的前十项是：
1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
更令人惊奇的是一个重要的数学常数：
e = .
e 的收敛项序列中的前十项是：
2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
其中第十项的分子各位数之和是 1+4+5+7=17。
找出 e 的收敛项序列中第 100 项的分子上各位之和。
272
本来写了递归的算法，结果run了半天出不来，果然递归的效率太低，用列表就快多了
k = []
for i in range(34):
k.append (1)
k.append (2*i+2)
k.append (1)
En =
for j in range(2,101):
En.append (En * k + En)
E100 = str(En)
total = 0
for each in E100:
total += int(each)
print (total) def con_e(num):#将连分数e的前num项组成list
e=
for i in range(1,num):
if i%3==2:
e.append(2*i//3+1)
else:
e.append(1)
return e
def deno(num):#将c+1/(b/a)转为b/a的格式,迭代c，最后一项不倒置，所以a即num项的分子
e=con_e(num)
a=e.pop()
b=1
while len(e):
c=e.pop()
temp=a*c+b
b=a
a=temp
return a
num=100
print(sum(int(i) for i in str(deno(num))))
272
>>> 用matlab算这个题目就是艹蛋，放弃{:5_104:} from fractions import Fraction
def fun(n):
if n == 0:
return 2
elif n % 3 == 2:
return (n + 1) * 2 // 3
else:
return 1
ans = Fraction(0)
for i in map(lambda x: fun(x), reversed(range(100))):
ans += i
ans = 1 / ans
print(sum(map(lambda x: int(x), str(ans.denominator))))
https://github.com/devinizz/project_euler/blob/master/page02/65.py
本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:47 编辑
n=99;
k=ones(1,n);
k(2:3:end)=2*(1:round(n/3));
k=flip(k);
fenzi=sym('1');
fenmu=sym(k(1));
for i=2:n
temp=sym(fenmu);
fenmu=sym(fenzi+k(i)*temp);
fenzi=temp;
end
total=;
t1=char(total(1));
wei=length(t1);
s=0;
for j=1:wei
s=s+str2num(t1(j));
end j.p.-hwang 发表于 2020-6-28 15:18
n=99;
k=ones(1,n);
k(2:3:end)=2*(1:round(n/3));
这……是什么语言 272
Process returned 0 (0x0) execution time : 0.032 s
Press any key to continue.
使用栈储存数据，递推计算，大数
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
typedef struct BigInt{
vector<int> v;
BigInt(vector<int> v):v(v){}
}BI;
BI operator + (const BI & a,const BI & x){
vector<int> t1 = a.v;
vector<int> t2 = x.v;
if (a.v.size() < x.v.size())swap(t1,t2);
for (int i = 0;i < max(t1.size(),t2.size() );i++){
if (i < t2.size())t1 += t2;
if (i > 0 && t1 > 9){t1++;t1 -= 10;}
}
if (t1 > 9)
if (t1.size() == t2.size() ){t1.push_back(1);t1 -= 10;}
else {
t1++;
for (int i = t2.size();i < t1.size()-1;i++){
if (t1 > 9) {t1 -= 10;t1++;}
else break;
}
t1 -= 10;
}
return BI(t1);
}
BI operator * (const int c,const BI & x){
BI res = x;
for (int i = 0;i < res.v.size();i++)
res.v *= c;
for (int i = 0;i < res.v.size()-1;i++)
if (res.v > 9) {
res.v += res.v / 10;
res.v %= 10;
}
int sz = res.v.size();
if (res.v > 9){res.v.push_back(res.v / 10); res.v %= 10;}
return res;
}
void print_ans(const BI & x){
int ans = 0;
for (int i = 0;i < x.v.size();i++)
ans += x.v;
cout << ans <<endl;
}
int main()
{
vector<int> a(1,1),b(1,1);
BI n(a),d(b);
stack<int> s;
for (int i = 1;i < 99;i++){
int k = i/3 + 1;
if (i % 3 == 2) s.push(2*k);
elses.push(1);
}
while(s.size() ){//先算e-2，再补回去
//cout << s.top() << endl;
BI t = d;
d = n + s.top() * d;
n = t;
s.pop();
}
n = n + 2*d;
print_ans(n);
return 0;
}
/*
答案：272
*/
#include <iostream>
#include <string>
#include <gmpxx.h>
using namespace std;
int main(void)
{
mpz_class p1 = 2, p2 = 3, p3, q1 = 1, q2 = 1, q3;
for (int i = 3; i <= 100; ++i)
{
if (i % 3 == 0)
{
p3 = p2 * 2 * (i / 3) + p1;
q3 = q2 * 2 * (i / 3) + q1;
}
else
{
p3 = p2 + p1;
q3 = q2 + q1;
}
p1 = p2;
q1 = q2;
p2 = p3;
q2 = q3;
}
string str = p2.get_str(10);
int nSum = 0;
for(int i = 0; i < int(str.length()); ++i)
nSum += int(str - 48);
cout << nSum << endl;
return 0;
}
def generator():
yield 2
k = 2
while True:
yield 1
yield k
yield 1
k += 2
it =
it.reverse()
it = iter(it)
nume = next(it)
deno = 1
for i in it:
nume, deno = i * nume + deno, nume
print(sum(int(i) for i in str(nume))) 本题可以应用连分数的递推公式和大数库mpir（或gmp）来解。
/*
答案：272
*/
#include <iostream>
#include <string>
#include <mpirxx.h>
using namespace std;
int main(void)
{
mpz_class p1=2, p2=3, p3;
mpz_class q1=1, q2=1, q3;
for (int i = 3; i <= 100; ++i)
{
int a = 1;
if (i % 3 == 0)
a = (i / 3) * 2;
p3 = a*p2 + p1;
q3 = a*q2 + q1;
p1 = p2;
p2 = p3;
q1 = q2;
q2 = q3;
}
string str = p3.get_str();
int nSum = 0;
for (int i = 0; i < (int)str.length(); ++i)
nSum += int(str - '0');
cout << nSum << endl;
return 0;
} import time as t
start = t.perf_counter()
decimal_list = []
for n in range(2, 101):
if not n % 3:
decimal_list.append(n // 3 * 2)
else:
decimal_list.append(1)
numerator = 1
denominator = decimal_list[-1]
for n in range(98, 0, -1):
numerator, denominator = denominator, numerator + denominator * decimal_list
numerator += denominator * 2
print(sum())
print("It costs %f s" % (t.perf_counter() - start))
272
It costs 0.000073 s 永恒的蓝色梦想 发表于 2020-6-28 16:17
这……是什么语言
matlab，虽然已经三年了
页:
[1]