基础算法题——黄金连分数题目（高精度、工具库）

忘是亡心i 2023-07-17 12:53 17阅读 0赞

前言：这道题很经典，考查了高精度、C++工具库的运用。  
写代码时会遇到很多坑，但是将它们解决，会很舒服！  
加油，坚持

--------------------

##### 黄金连分数题目 #####

黄金分割数0.61803… 是个无理数，这个常数十分重要，在许多工程问题中会出现。有时需要把这个数字求得很精确。  
对于某些精密工程，常数的精度很重要。也许你听说过哈勃太空望远镜，它首次升空后就发现了一处人工加工错误，对那样一个庞然大物，其实只是镜面加工时有比头发丝还细许多倍的一处错误而已，却使它成了“近视眼”!!  
言归正传，我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。  
比较简单的一种是用连分数：(ps：\*作为空格)  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1  
黄金数 = ---------------------  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*1 + -----------------  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1 + -------------  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1 + ---------  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*1 + …

这个连分数计算的“层数”越多，它的值越接近黄金分割数。  
请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。  
小数点后3位的值为：0.618  
小数点后4位的值为：0.6180  
小数点后5位的值为：0.61803  
小数点后7位的值为：0.6180340

（注意尾部的0，不能忽略）  
你的任务是：写出精确到小数点后100位精度的黄金分割值。

注意：尾数的四舍五入！ 尾数是0也要保留！

显然答案是一个小数，其小数点后有100位数字，请通过浏览器直接提交该数字。

--------------------

##### 题目分析 #####

**①、转为求斐波那契数列的n和前n项。  
②、n取多少？再增加n，小数点后的101位没有变化。  
③、不能用C++语言定义的整数型直接运算，而要手工地写大数加法和除法（减法）。**  
（这分析起来要一番功夫，不过让我们一步一步走下去吧！）  
在开始分析前，我先简单通过举例的方式介绍一下该题要用到的C++提供的算法工具库algorithm中的三个工具，当然也可以直接创建工具函数。

reverse： 翻转字符串  
![例1][1]

--------------------

s1=s1.substr(s1.find\_first\_not\_of(‘0’))：去掉字符串头’0’  
![s1=s1.substr(s1.find\_first\_not\_of('0'))][s1_s1.substr_s1.find_first_not_of_0]

--------------------

s1.append(s2)：在字符串s1结尾插入s2

###### 一、转为求斐波那契数列的n和前n项。 ######

我们通过分析黄金连分数可以发现：当数据中的分母越“深”，得到的黄金数就会越精确。  
![黄金数][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
不同“深度”的黄金数：  
当深度①时，黄金数=1/2  
当深度②时，黄金数=2/3  
当深度③时，黄金数=3/5  
…  
我们可以找到规律：  
若f(n)为斐波那契数列第n项  
当深度①时，黄金数=f(2)/f(3)  
当深度②时，黄金数=f(3)/f(4)  
当深度③时，黄金数=f(4)/f(5)  
…  
表明：黄金数≈f(n)/f(n+1)。（n越大，黄金数越精确）

###### 二、n取多少？再增加n，小数点后的101位没有变化。 ######

这个问题，我们不必精确求出小数点后的101位没有变化的临界值，我们只要取较大的n（如n=500），就能满足精确条件。但是n=500的条件下，f(n)已经是超过C++提供的long long类型。所以我们要手工地写大数加法和除法（减法）。

###### 三、手工地写大数加法和除法（减法）。 ######

这一步最麻烦，但是是最关键的地方。我们可以通过C++提供的算法工具库algorithm（包含在bits/stdc++.h库）进行翻转、去掉字符串开头‘0’，当然也可以直接创建工具函数。  
**大数运算的用处**  
大数加法：假设我们要求斐波那契数列数列第500项。f(n)=f(n-1)+f(n-2)，通过大数加法递推出f(500)。  
大数除法：黄金数=f(n-1)/f(n)。

**大数加法实现分析**：考虑两个字符串如何实现“相加”呢？我们只要注意两点。  
①、将输入的个位、十位…依次存储到A\[0\]、A\[1\]…  
②、处理进位问题  
[大数加法具体过程][Link 1]

大数加法代码：

string add(string a, string b)
    { 
    	//翻转，便于从低位逐步求和 
    	reverse(a.begin(), a.end());
    	reverse(b.begin(), b.end());
    
    	long len, d=0;
    	if(a.length()>b.length())
    		len=a.length()
    	else 
    		len=b.length();//长度 
    
    	string ans(len+10, '0');	
    	//初始化 (必须)：ans字符串并没被赋值，值为随机
    	//len+10给ans进位留足够空间,当然也可以用len+1
    	
    	for(long i=0; i<=len; i++)
    	{ 
    		int A=0, B=0;
    		if(i<a.length())A=a[i]-'0';
    		if(i<b.length())B=b[i]-'0';
    		ans[i]=(A+B+d)%10+'0';
    		d=(A+B+d)/10;	//进位
    	}
    	reverse(ans.begin(), ans.end());
    	//截取子串 清除字符串开头的'0'
    	ans=ans.substr(ans.find_first_not_of('0'));
    	return ans;
    }

--------------------

**大数除法实现分析**：这里的大数除法是通过大数减法实现的，这种方法很巧妙，避免了很多直接用除法运算的复杂过程。  
针对本题特殊情况：f(n-1)除以f(n)，小数除以大数。  
（下面便按照这样的情况进行分析，大数除以小数情况暂不讨论。）  
让我们通过例子来了解实现过程：  
First：1/3=0.33…33  
![例1][1 1]  
Second:1/4=0.25  
![例2][2]  
根据上图，我们需要记录两个变量：  
①、分子乘以10或余数乘以10后的值能被分母减的次数  
②、被分母减完后的余数。

//判断a是否小于b
    int cmp(string a, string b)
    { 
    	if(a.length()>b.length()) return 1;
    	if(a.length()<b.length()) return -1;
    	if(a.length()==b.length())//长度相等 
    	{ 
    		if(a<b) return -1;//字典序比较 
    		if(a>b) return 1;
    		else return 0;
    	}
    }
    
    //此处a一定大于等于b 
    string subtract(string a, string b)
    { 
    // 翻转
    	reverse(a.begin(), a.end());
    	reverse(b.begin(), b.end());
    // 按位做减法
    // 拷贝a到ans中 
    	string ans=a;
    	for(int i=0; i<a.length(); i++)
    	{ 
    		int B;
    		if(b.length()>i) B=b[i]-'0';
    		else B=0;
    		ans[i]=ans[i]-B;
    		if(ans[i]<'0')
    		{ 
    			ans[i]+=10;
    			ans[i+1]--;
    		}
    	}
    	reverse(ans.begin(), ans.end());
    	ans=ans.substr(ans.find_first_not_of('0'));
    	return ans;
    }
    
    // 将t由int转换为string
    void i2s(int t, string& t_str)
    { 
    	string a(1, '0');
    	a[0]=t+'0';
    	t_str=a;
    }
    
    // 除法转化成减法
    string divide(string a, string b)
    { 
    	string ans="0.";
    	for(int i=0; i<101; i++)
    	{ 
    		a.append("0");	//将a后面加入0：乘以10
    		int t=0;
    		while(cmp(a, b)>=0)//a加0，a>=b
    		{ 
    			a=subtract(a, b);
    			t++;		//记录减法做了多少次 
    		}
    		string t_str;
    		i2s(t, t_str);	//将t由int转换为string
    		ans.append(t_str);	//保留小数
    	}
    	return ans;
    }

--------------------

##### 总结 #####

题目可以说考查的内容比较多，第一步我们要将黄金连分数联想到斐波那契数列，第二步我们要确保黄金数小数点后100位精确值就要通过手写大数运算才能求出。在手写大数运算时，我们可以通过C++提供的算法工具库algorithm（包含在bits/stdc++.h库）进行翻转、去字符串开头‘0’这样能够减少我们的代码量。  
网上很多讲解都没能确保黄金数小数点后100位精确值，只是在long long的范围内找出最大的斐波那契数数列项来进行计算。  
经过验证，如果要保证黄金数的100位精确值，n要达到250或者以上才能确保黄金数（f(249)/f(250)）**小数点后100位保持不变**。

全部代码：

#include<bits/stdc++.h>
    #include<cstring>
    using namespace std;
    int n=400;
    
    // 大数加法
    string add(string a, string b)
    { 
    	//翻转，便于从低位逐步求和 
    	reverse(a.begin(), a.end());
    	reverse(b.begin(), b.end());
    
    	long len, d=0;
    	if(a.length()>b.length())
    		len=a.length()
    	else 
    		len=b.length();//长度 
    
    	string ans(len+10, '0');	
    	//初始化 (必须)：ans字符串并没被赋值，值为随机
    	//len+10给ans进位留足够空间,当然也可以用len+1
    	
    	for(long i=0; i<=len; i++)
    	{ 
    		int A=0, B=0;
    		if(i<a.length())A=a[i]-'0';
    		if(i<b.length())B=b[i]-'0';
    		ans[i]=(A+B+d)%10+'0';
    		d=(A+B+d)/10;	//进位
    	}
    	reverse(ans.begin(), ans.end());
    	//截取子串 清除字符串开头的'0'
    	ans=ans.substr(ans.find_first_not_of('0'));
    	return ans;
    }
    
    // 判断a是否小于b
    int cmp(string a, string b)
    { 
    	if(a.length()>b.length()) return 1;
    	if(a.length()<b.length()) return -1;
    	if(a.length()==b.length())//长度相等 
    	{ 
    		if(a<b) return -1;//字典序比较 
    		if(a>b) return 1;
    		else return 0;
    	}
    }
    
    // 此处a一定大于等于b 
    string subtract(string a, string b)
    { 
    // 翻转
    	reverse(a.begin(), a.end());
    	reverse(b.begin(), b.end());
    // 按位做减法
    // 拷贝a到ans中 
    	string ans=a;
    	for(int i=0; i<a.length(); i++)
    	{ 
    		int B;
    		if(b.length()>i) B=b[i]-'0';
    		else B=0;
    		ans[i]=ans[i]-B;
    		if(ans[i]<'0')
    		{ 
    			ans[i]+=10;
    			ans[i+1]--;
    		}
    	}
    	reverse(ans.begin(), ans.end());
    	ans=ans.substr(ans.find_first_not_of('0'));
    	return ans;
    }
    
    // 将t由int转换为string
    void i2s(int t, string& t_str)
    { 
    	string a(1, '0');
    	a[0]=t+'0';
    	t_str=a;
    }
    
    // 除法转化成减法
    string divide(string a, string b)
    { 
    	string ans="0.";
    	for(int i=0; i<101; i++)
    	{ 
    		a.append("0");	//将a后面加入0：乘以10
    		int t=0;
    		while(cmp(a, b)>=0)//a加0，a>=b
    		{ 
    			a=subtract(a, b);
    			t++;		//记录减法做了多少次 
    		}
    		string t_str;
    		i2s(t, t_str);	//将t由int转换为string
    		ans.append(t_str);	//保留小数
    	}
    	return ans;
    }
    
    int main()
    { 
    	string a="1";
    	string b="1";
    
     	for(int i=3; i<=n; i++)//求斐波那契
    	{ 
    		string tmp=b;
    		b=add(a, b);
    		a=tmp;
    	}
    
    	string ans=divide(a, b);
    	cout<<ans<<endl;
    	cout<<ans.length()<<endl;
    	return 0;
    }
    //n=50:0.618033988749894848207409900012049043262842540424722885660709131394082846564611
    // 70787663185198760678802
    //n=100:0.618033988749894848204586834365638117720312743963795685753591851088290198698875
    // 22987627156252996318428
    //n=200:0.618033988749894848204586834365638117720309179805762862135448622705260462818902
    // 44971288825799042314041
    //n=250:0.618033988749894848204586834365638117720309179805762862135448622705260462818902
    // 44970720720418939113748 
    //n=400:0.618033988749894848204586834365638117720309179805762862135448622705260462818902
    // 44970720720418939113748

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[1]: /images/20230528/1cf4108d2b6f471ab34dd47bb4d53bd5.png
[s1_s1.substr_s1.find_first_not_of_0]: /images/20230528/3a591bf465664f8382013f8a83f4491b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230528/9b7039554c794fbd98e9951099f67c23.png
[Link 1]: https://blog.csdn.net/Zhengyangxinn/article/details/104950488
[1 1]: /images/20230528/59879c3f0540487f97a4c98fc363586b.png
[2]: /images/20230528/3217e32e406b4f9493793fae1136e659.png