蓝桥杯2013年第四届真题-黄金连分数

题目

黄金分割数0.61803… 是个无理数，这个常数十分重要，在许多工程问题中会出现。有时需要把这个数字求得很精确。

对于某些精密工程，常数的精度很重要。也许你听说过哈勃太空望远镜，它首次升空后就发现了一处人工加工错误，对那样一个庞然大物，其实只是镜面加工时有比头发丝还细许多倍的一处错误而已，却使它成了“近视眼”！！

言归正传，我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。

比较简单的一种是用连分数：

              1
黄金数 = ---------------------
                    1
         1 + -----------------
                      1
             1 + -------------
                        1
                 1 + ---------
                      1 + ...

题解

高精度

高精度模板【全】

首先要看出规律，精度由低到高，黄金数可以表示为： 1 1 1、 1 2 \frac{1}{2} 21​、 2 3 \frac{2}{3} 32​、 3 5 \frac{3}{5} 53​、 5 8 \frac{5}{8} 85​、……

斐波那契数列，分子为Fib(n-1)，分母为Fib(n)。

如果要精确到小数点后100位，显然得用高精度才行。

我们思考一下如何完成这个计算工作，整理出要用到哪些高精度运算。

1. 斐波那契数列的计算需要采用高精度加法。当分子和分母的位数足够多时才能保证小数部分的位数超过100位。

2. 分子除以分母需要采用高精度除法（本质是高精度减法）。注意这里的高精度除法不是“高精度除以低精度”而是“高精度除以高精度”，所以需要使用减法来模拟。

3. 不进行真分数的除法，进行假分数的除法。如果分子比分母小，那么我们除法计算会很难进行，不如给分子后面多加105个0，这样就可以保证分子比分母大，而且商为至少存在101位的整数。

4. 得到101位的商后，观察一下第101位需不需要四舍五入到第100位，这里可以不采用高精度加法实现加一的操作。

5. 输入答案的时候不要忘记加上前面的“0.”。

如果还是写不出来，这里给出一个整体思路模板，大家只需要填写一些关键步骤就行了。

string add (string s1, string s2) { // 计算 s1 + s2 的值并返回

	return res;
}

string div (string s1, string s2) { // 计算 s1 / s2 的商并返回

	return res;
}

string Fib (int n) { // 计算 Fibonacci(n) // 这个如何定义可以根据自己对题目的理解
	
}

main() {
	// 得到Fib(1000) 和 Fib(999) // 足够大是为了保证小数点后的精度
	// res = div (Fib(999) * 10^105, Fib(1000))
	// cout