【蓝桥杯】黄金连分数（注意：大数）！！！-阿里云开发者社区

黄金连分数（注意：大数）

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;
}

【蓝桥杯】黄金连分数（注意：大数）！！！

黄金连分数（注意：大数）

热门文章

最新文章

相关课程

相关电子书