黄金连分数-蓝桥杯-字符串

题目描述:

标题: 黄金连分数

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

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

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

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

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位数字,请通过浏览器直接提交该数字。
注意:不要提交解答过程,或其它辅助说明类的内容。

解决方案:

#include <string> #include <iostream> #include <sstream> #include <algorithm> using namespace std; int n = 400; void i2s(int num, string &str) { stringstream ss; ss << num; ss >> str; } string add(string a, string b) { a = a.substr(a.find_first_not_of('0')); b = b.substr(b.find_first_not_of('0')); long long lenA = a.length(); long long lenB = b.length(); long long len = max(lenA, lenB) + 10; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string ans(len, '0'); for (int i = 0; i < lenA; ++i) { ans[i] = a[i]; } int tmp = 0; for (int i = 0; i < len; ++i) { if (i < b.length()) tmp += (ans[i] - '0') + (b[i] - '0'); else tmp += (ans[i] - '0'); ans[i] = tmp % 10 + '0';//8 8+'0' tmp /= 10;//1 } reverse(ans.begin(), ans.end()); return ans.substr(ans.find_first_not_of('0')); } int cmp(string a, string b) { unsigned long i1 = a.find_first_not_of('0'); if (i1 == string::npos)a = '0'; else a.substr(i1); unsigned long i2 = b.find_first_not_of('0'); if (i2 == string::npos)b = '0'; else b.substr(i2); if (a.length() > b.length())return 1; else if (a.length() < b.length())return -1; else { if (a < b)return -1; if (a > b)return 1; else return 0; } } string subtract(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); for (int i = 0; i < b.length(); ++i) { if (a[i] >= b[i]) { a[i] = a[i] - b[i] + '0'; } else { int k = 1; while (a[i + k] == '0') { a[i + k] = '9'; k++; } a[i + k] = a[i + k] - '1' + '0'; a[i] = (a[i] - '0' + 10) - (b[i] - '0') + '0'; } } reverse(a.begin(), a.end()); if (a.find_first_not_of('0') == string::npos)return "0"; return a.substr(a.find_first_not_of('0')); } string divide(string a, string b) { string ans = "0."; for (int i = 0; i < 101; ++i) { a.append("0"); int t = 0; while (cmp(a, b) >= 0) {//a>=b a = subtract(a, b); t++; } string t_str; i2s(t, t_str); ans.append(t_str); } return ans; } int main(int argc, const char *argv[]) { string a = "1"; string b = "1"; cout << subtract(a, b) << endl; for (int i = 3; i <= n; ++i) { string tmp = b; b = add(a, b); a = tmp; // cout << b << " " << endl; } string ans = divide(a, b); cout << ans << endl; cout << ans.length()-2 << endl; return 0; } 
本网页由快兔兔AI采集器生成,目的为演示采集效果,若侵权请及时联系删除。

原文链接:https://bbs.csdn.net/skill/algorithm/algorithm-be788b02c56e4c8bbc442449c753daf0

更多内容