黄金连分数（注意：大数）
- 1.转为求斐波那契数列的n和n+1项
- 2. n取多少？再增加n，小数点后的101位没有变化。
- 3.不能用C语言定义的整数型直接运算，而是要手工地写大数加法和除法（减法）
大数的计算
vector是一种顺序容器，事实上和数组差不多，但它比数组更优越。一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界。而vector正好弥补了这个缺陷，它的特征是相当于可分配拓展的数组，它的随机访问快，在中间插入和删除慢，但在末端插入和删除快，而且如果你用.at()访问的话，也可以做越界检查。
常用操作：
v.push_back(t) 在数组的最后添加一个值为t的数据
v.size() 当前使用数据的大小
v.pop_back(); // 弹出容器中最后一个元素（容器必须非空）
v.back(); // 返回容器中最后一个元素的引用
/* 这里专门就算法中的大数问题进行一个统一归纳 */ #include<iostream> #include<string> #include<vector> using namespace std; //结果支持的最大位数 //这个可以依据具体需求调整 const static int M = 2000; int numA[M]; int numB[M]; //使用string重置numA void resetNumA(string numAStr) { memset(numA,0,M*sizeof(int)); //将字符串的每一位都转换成数字传入数组 for (int i = 0; i < numAStr.length(); i++) { numA[i] = numAStr[numAStr.length()-i-1] - '0'; } } //使用string重置numB void resetNumB(string numBStr) { memset(numB,0,M*sizeof(int)); //将字符串的每一位都转换成数字传入数组 for (int i = 0; i < numBStr.length(); i++) { numB[i] = numBStr[numBStr.length()-i-1] - '0'; } } //将数组转换为字符串，用于输出 string getNumString(int* num) { string numString; bool isBegin = false; for (int i = M-1; i >= 0 ; i--) { if(num[i] != 0) { isBegin = true; } if (isBegin) { numString += num[i] +'0'; } } return numString; } //判断两个数字哪个大 int compare(string numAStr,string numBStr) { if (numAStr.length() > numBStr.length()) { return 1; } else if (numAStr.length() < numBStr.length()) { return -1; } else { for (int i = 0; i < numAStr.length(); i++) { if (numAStr[i]>numBStr[i]) { return 1; } if (numAStr[i]<numBStr[i]) { return -1; } } return 0; } } //加法 string plus(string numAStr, string numBStr) { resetNumA(numAStr); resetNumB(numBStr); for (int i = 0; i < M; i++) { //结果保存在numA中 numA[i] += numB[i]; //数字大于9则进位 if(numA[i]>9) { numA[i] -= 10; numA[i+1]++; } } return getNumString(numA); } //减法 string minus(string numAStr, string numBStr) { bool isNegative = false; //如果numA比numB小 //则结果为负数 //调换位置进行计算 if (compare(numAStr,numBStr)==-1) { isNegative = true; string temp = numAStr; numAStr = numBStr; numBStr = temp; } else if (compare(numAStr,numBStr)==0) { return "0"; } resetNumA(numAStr); resetNumB(numBStr); for (int i = 0; i < M; i++) { //减数小于被减数就借位 if (numA[i]<numB[i]) { numA[i] = numA[i]+10-numB[i]; numA[i+1]--; } else { numA[i] -= numB[i]; } } if (isNegative) { return "-"+ getNumString(numA); } else { return getNumString(numA); } } //乘法 string mul(string numAStr, string numBStr) { resetNumA(numAStr); resetNumB(numBStr); vector<string> nums; for (int i = 0; i < numBStr.length(); i++) { //初始化一个临时数据来保存被乘数与乘数的某一位相乘的结果 int temp[M]; memset(temp,0,M*sizeof(int)); for (int j = i; j < numAStr.length()+i; j++) { temp[j] += numA[j-i]*numB[i]%10; temp[j+1] = numA[j-i]*numB[i]/10; //如果大于9，那么就做进位处理 if (temp[j]>9) { temp[j]-=10; temp[j+1]++; } } nums.push_back(getNumString(temp)); } //每位相乘的结果再用加法加起来 string result = nums[0]; for (int i = 1; i < nums.size(); i++) { result = plus(result,nums[i]); } return result; } //除,结果精确到个位 string div(string numAStr, string numBStr) { resetNumA(numAStr); resetNumB(numBStr); string result; string left; if (compare(numAStr,numBStr)==-1) { return "0"; } //标记第一个不为0的位数的出现 bool flag = false; for (int i = 0; i < numAStr.length(); i++) { left +=numAStr[i]; //余数比除数大 if (compare(left,numBStr)==1) { flag = true; int count = 1; string temp = numBStr; while (true) { //每循环一次加上一个余数 temp = plus(temp,numBStr); //余数仍然大于除数，继续累加 if (compare(left,temp)==1) { count++; } //余数小于除数 //可以计算结果 else if (compare(left,temp)==-1) { result += count + '0'; left = minus(left, minus(temp,numBStr)); break; } //此时余数刚好是除数的倍数 else if (compare(left,temp) == 0) { count ++; result += count + '0'; left = ""; break; } } } //刚好除尽 else if(compare(left,numBStr)==0) { flag = true; result +="1"; left = ""; } //余数比除数小，跳到下一位 else if(flag) { result +="0"; } } return result; } void printTitle() { cout << endl; cout << "输入1：加法" << endl; cout << "输入2：减法" << endl; cout << "输入3：乘法" << endl; cout << "输入4：除法" << endl; cout << "选择 : "; } int main() { string numAStr,numBStr; string operation; string result; printTitle(); while (cin >> operation) { cout << "输入两个数字： "; cin >> numAStr >> numBStr; if(operation == "1") { result = plus(numAStr,numBStr); } else if(operation == "2") { result = minus(numAStr,numBStr); } else if(operation == "3") { result = mul(numAStr,numBStr); } else { result = div(numAStr,numBStr); } cout << "结果为：" << result << endl; printTitle(); } }
黄金连分数：
#include <stdio.h> #include <memory.h> //大数乘10 void mul10(unsigned char* a) { short i = 0; for (; i < 99; i++) a[i] = a[i + 1]; a[99] = 0; } //大数乘个位数i void mul_i(unsigned char* a, unsigned char* dest, unsigned char i) { short v = 0; unsigned char all, num = 0, point; if (i == 0) { memset(dest, 0, 100); return; } for (v = 99; v >= 0; v--) { all = a[v] * i + num; num = all / 10; point = all - num * 10; dest[v] = point; } } //大数相减 void sub(unsigned char* a, unsigned char* b) { short i = 99; unsigned char flag = 0; for (; i >= 0; i--) { if (a[i] - flag < b[i]) { a[i] = a[i] + 10 - flag - b[i]; flag = 1; } else { a[i] = a[i] - flag - b[i]; flag = 0; } } } //大数相加 void add(unsigned char* a, unsigned char* b) { short i = 99, all; for (; i > 0; i--) { all = a[i] + b[i]; if (all >= 10) { a[i - 1]++; a[i] = all - 10; } else a[i] = all; } a[0] = (a[0] + b[0]) % 10; } //大数相除第一个小数 unsigned char div_a_b(unsigned char* a, unsigned char* b) { unsigned char i = 1; unsigned char tmp[100]; unsigned char tmp1[100] = { 0 }; memcpy(tmp, a, 100); mul10(tmp); for (; i <= 10; i++) { mul_i(b, tmp1, i); if (memcmp(tmp1, tmp, 100) > 0) { mul10(a); memset(tmp1, 0, 100); mul_i(b, tmp1, i - 1); sub(a, tmp1); return i - 1; } memset(tmp1, 0, 100); } } //大数是否为零 bool isZero(unsigned char* a) { short i = 99; for (; i >=0; i--) if (a[i] != 0) return false; return true; } //保留100位小数相除 void div100(unsigned char* a, unsigned char* b, unsigned char* res) { unsigned char i = 0; unsigned char tmp[100]; memcpy(tmp, a, 100); for (; i < 101; i++) { res[i] = div_a_b(tmp, b); if (isZero(tmp)) return; } } //信息打印 void printRes(unsigned char* a, unsigned char* b, unsigned char* res) { static int count = 0; int i = 0; bool flag = false; printf("%d: ", count++); for (; i < 100; i++) { if (!flag&&a[i]) flag = true; if (flag) printf("%d", a[i]); } printf("/"); flag = false; for (i = 0; i < 100; i++) { if (!flag&&b[i]) flag = true; if (flag) printf("%d", b[i]); } printf("\n"); printf("0."); for (i = 0; i < 101; i++) printf("%d", res[i]); printf("\n"); } int main() { short index; //使用数组作为大数，res存放结果小数bufen unsigned char a[100] = { 0 }; unsigned char b[100] = { 0 }; unsigned char tmp[100] = { 0 }; unsigned char pre[101] = { 0 }; unsigned char res[101] = { 0 }; a[99] = 1; b[99] = 2; do { memcpy(pre, res, 101); memset(res, 0, 101); div100(a, b, res); printRes(a, b, res); memcpy(tmp, a, 100); memcpy(a, b, 100); add(b, tmp); } while (memcmp(pre, res, 101)); if (res[100] >= 5) res[99]++; index = 99; while (res[index--] == 10) { res[index + 1] = 0; res[index]++; } printf("最终结果为:\n0."); for (index = 0; index < 100; index++) printf("%d", res[index]); printf("\n"); return 0; }
