鱼C论坛

 找回密码
 立即注册
查看: 1779|回复: 11

[已解决]c++问题求助

[复制链接]
发表于 2023-7-24 20:46:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
高精度阶乘

题目描述

用高精度计算出 S = 1! + 2! + 3! + \cdots + n!(n <= 50)。

其中 ! 表示阶乘,定义为 n!=n (n-1) (n-2) ··· 1。例如,5! = 5 4   3 2 1=120。

输入格式

一个正整数 n

输出格式

一个正整数 S,表示计算结果。

样例 #1

样例输入 #1


  1. 3
复制代码


样例输出 #1


  1. 9
复制代码


提示

【数据范围】

对于 100 % 的数据,1 <= n <= 50。

c++完成,怎么做?数据太大了
最佳答案
2023-7-24 21:18:23
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> s;
  6. vector<int> mult(vector<int>&a,int b)  //高精度*低精度
  7. {
  8.         vector<int> p;
  9.         p.clear();
  10.        
  11.         int t=0;
  12.         for(int i=0;i<a.size()||t!=0;i++)
  13.         {
  14.                 if(i<a.size())
  15.                 t=a[i]*b+t;
  16.                 p.push_back(t%10);
  17.                 t=t/10;
  18.         }
  19.         while(p.size()>1&&p.back()==0)
  20.         p.pop_back();
  21.         return p;
  22. }
  23. vector<int> add(vector<int>&a,vector<int>&res)  //高精度+高精度
  24. {
  25.         vector<int> p;
  26.         p.clear();
  27.         int t=0;
  28.         for(int i=0;i<a.size()||i<res.size()||t!=0;i++)
  29.         {
  30.                 if(i<a.size())
  31.                 t=a[i]+t;
  32.                 if(i<res.size())
  33.                 t=res[i]+t;
  34.                 p.push_back(t%10);
  35.                 t=t/10;
  36.         }
  37.         while(p.size()>1&&p.back()==0)
  38.         p.pop_back();
  39.         return p;
  40. }
  41. int main()
  42. {
  43.         int n;
  44.         cin>>n;
  45.         vector<int> res;
  46.         for(int i=1;i<=n;i++)
  47.         {
  48.                 if(i==1)
  49.                 {
  50.                         s.push_back(1);
  51.                         res.push_back(0);
  52.                 }
  53.                         s=mult(s,i);
  54.                        
  55.                         res=add(s,res);
  56.         }
  57.         for(int i=res.size()-1;i>=0;i--)
  58.         cout<<res[i];
  59.         cout<<endl;
  60. }
复制代码


这个代码试试,应该可以
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2023-7-24 20:47:09 | 显示全部楼层
对于这个问题,我们可以通过使用大数运算来计算高精度阶乘的和。以下是一个使用 C++ 实现的示例代码:

  1. #include <iostream>
  2. #include <vector>

  3. using namespace std;

  4. void multiply(vector<int>& num, int factor) {
  5.     int carry = 0;
  6.     for (int i = 0; i < num.size(); i++) {
  7.         int product = num[ i] * factor + carry;
  8.         num[ i] = product % 10;
  9.         carry = product / 10;
  10.     }
  11.    
  12.     while (carry > 0) {
  13.         num.push_back(carry % 10);
  14.         carry /= 10;
  15.     }
  16. }

  17. int main() {
  18.     int n;
  19.     cout << "请输入一个正整数n:";
  20.     cin >> n;
  21.    
  22.     vector<int> sum {1}; // 初始和为1
  23.    
  24.     for (int i = 2; i <= n; i++) {
  25.         multiply(sum, i); // 计算阶乘并累加到和中
  26.     }

  27.     cout << "计算结果S为:";
  28.     for (int i = sum.size() - 1; i >= 0; i--) {
  29.         cout << sum[ i];
  30.     }
  31.     cout << endl;
  32.    
  33.     return 0;
  34. }
复制代码


这段代码使用了一个 multiply 函数,该函数将一个大数(用一个整数数组表示)与一个因子相乘,并更新结果。然后,我们从2开始迭代到n,每次将当前的阶乘累加到和中。

由于题目要求输出计算结果S,并且数据范围限定在n <= 50之内,这段代码可以满足要求,能够正确计算高精度阶乘的和。

希望这个回答能帮到你,如有更多问题,请随时提问。
如果问题已经解决,请设置最佳答案
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 20:47:10 | 显示全部楼层
要计算高精度阶乘的和,可以使用数组来表示大整数,并模拟手工计算的过程。以下是一个使用C++实现的示例代码:
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. // 大整数相乘
  5. vector<int> multiply(vector<int>& num, int factor) {
  6.     vector<int> result;
  7.     int carry = 0;
  8.     for (int i = 0; i < num.size(); ++i) {
  9.         int product = num[i] * factor + carry;
  10.         result.push_back(product % 10);
  11.         carry = product / 10;
  12.     }
  13.     while (carry > 0) {
  14.         result.push_back(carry % 10);
  15.         carry /= 10;
  16.     }
  17.     return result;
  18. }
  19. // 高精度阶乘的和
  20. vector<int> factorialSum(int n) {
  21.     vector<int> sum;
  22.     sum.push_back(1);  // sum初始值为1
  23.     for (int i = 2; i <= n; ++i) {
  24.         sum = multiply(sum, i);  // 计算每个阶乘,并累加到sum中
  25.     }
  26.     return sum;
  27. }
  28. // 输出大整数
  29. void printBigInt(const vector<int>& num) {
  30.     for (int i = num.size() - 1; i >= 0; --i) {
  31.         cout << num[i];
  32.     }
  33.     cout << endl;
  34. }
  35. int main() {
  36.     int n;
  37.     cout << "请输入正整数n:";
  38.     cin >> n;
  39.     vector<int> result = factorialSum(n);
  40.     cout << "计算结果S = ";
  41.     printBigInt(result);
  42.     return 0;
  43. }
复制代码

使用上述代码,可以计算出给定正整数n的高精度阶乘和。注意,由于数据量较大,结果可能会超过常规整数类型的范围,所以我们使用了vector<int>来表示大整数,并手动实现了乘法操作。运行程序后,输入正整数n即可得到计算结果S。

希望对你有帮助!如果还有其他问题,请随时提问。求给个最佳答案,非常感谢
只要点击我的回复贴写着发表时间的那一栏的绿色按钮即可,点了奖赏2鱼币,最好请你出售附件(不过也支持评分)-->

                               
登录/注册后可看大图


此回答源于ChatGPT,若有不正确之处,请多包容
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 20:47:53 | 显示全部楼层
这是一个非常经典的高精度计算问题,而且由于 n 的取值范围(n <= 50),使用 C++ 基本的整型类型确实不能满足计算需求。我们可以采取将数字以字符串的形式存储和操作的方式来处理这种高精度计算。

这个问题我们可以分解为两个子问题:1. 高精度乘法;2. 高精度加法。

我们先来看看高精度乘法的实现。假设我们已经有一个数 a,我们需要用 a 来乘以一个普通的整数 b。乘法的基本步骤就是将 a 的每一位与 b 相乘,然后加上上一位的进位,然后存储到结果中。

接下来,我们需要实现高精度加法。这是非常直观的,只需要将两个数的对应位相加,然后处理进位就可以了。

下面是一个简单的实现:

  1. #include<bits/stdc++.h>
  2. using namespace std;

  3. const int MAXN = 500;
  4. int n, a[MAXN], b[MAXN];

  5. void mul(int x) { //高精度乘法
  6.     for(int i = 1; i <= a[0]; ++i)
  7.         a[ i] *= x;
  8.     for(int i = 1; i <= a[0]; ++i) {
  9.         if(a[ i] > 10) {
  10.             a[i + 1] += a[ i] / 10;
  11.             a[ i] %= 10;
  12.             if(i == a[0]) ++a[0];
  13.         }
  14.     }
  15. }

  16. void add() { //高精度加法
  17.     b[0] = max(a[0], b[0]);
  18.     for(int i = 1; i <= a[0]; ++i) {
  19.         b[ i] += a[ i];
  20.         if(b[ i] > 10) {
  21.             b[i + 1] += b[ i] / 10;
  22.             b[ i] %= 10;
  23.             if(i == b[0]) ++b[0];
  24.         }
  25.     }
  26. }

  27. int main() {
  28.     cin >> n;
  29.     a[0] = a[1] = b[0] = b[1] = 1;
  30.     for(int i = 2; i <= n; ++i) {
  31.         mul(i);
  32.         add();
  33.     }
  34.     for(int i = b[0]; i > 0; --i)
  35.         cout << b[ i];
  36.     return 0;
  37. }
复制代码


这个程序先进行初始化,然后进入循环,先进行高精度乘法,然后进行高精度加法,最后将结果输出。

注意:数组的下标 0 的位置我们用来存储当前数组中的位数,所以在进行高精度运算的时候需要特别注意这一点,以防止数组越界。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 20:57:56 | 显示全部楼层
那个代码测试了,只是有点小问题,找了个可以用的:
  1. #include<bits/stdc++.h>
  2. #define mian main
  3. #define MAXN 10500

  4. using namespace std;

  5. string a, b;
  6. //选择字符串。因为字符串储存了每个串的长度,可以直接调用。
  7. int na[MAXN], nb[MAXN], ans[MAXN];
  8. bool pd;

  9. int main()
  10. {
  11.     cin >> a >> b;
  12.         if((a < b && a.size() == b.size()) || a.size() < b.size())
  13.         {
  14.                 swap(a, b);
  15.                 pd = true;
  16.         }
  17.     for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
  18.     for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';
  19.     //将字符串中的信息转化到数组中,数组模拟数字。
  20.     int maxl = max(a.size(), b.size());
  21.     //找到两个数中的最大位,为for循环服务
  22.         for(int i = 1; i <= maxl; i ++)
  23.         {
  24.                 if(na[i] < nb[i])
  25.                 {
  26.                         na[i + 1] --;
  27.                         na[i] += 10;
  28.                 }
  29.                 ans[i] = na[i] - nb[i];
  30.         }
  31.        
  32.         while(ans[maxl] == 0)maxl --;//防止减后降位,多输出若干0
  33.        
  34.         if(pd == true)cout << "-";//b>a时,a - b < 0 所以打上负号
  35.        
  36.         for(int i = maxl; i > 0; i --)cout << ans[i];
  37.         if(maxl < 1)cout << "0";
  38.     return 0;
  39. }
复制代码

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 21:05:36 | 显示全部楼层
要计算高精度的阶乘和,可以使用数组来表示大整数,并模拟手工计算的过程。

以下是一个使用C++实现的示例代码:


  1. #include <iostream>
  2. #include <vector>

  3. // 高精度相加函数
  4. std::vector<int> add(const std::vector<int>& num1, const std::vector<int>& num2) {
  5.     std::vector<int> result;
  6.     int carry = 0; // 进位
  7.     int i = num1.size() - 1;
  8.     int j = num2.size() - 1;

  9.     while (i >= 0 || j >= 0 || carry > 0) {
  10.         int sum = carry;
  11.         if (i >= 0) {
  12.             sum += num1[i];
  13.             i--;
  14.         }
  15.         if (j >= 0) {
  16.             sum += num2[j];
  17.             j--;
  18.         }

  19.         result.push_back(sum % 10);
  20.         carry = sum / 10;
  21.     }

  22.     // 翻转结果数组
  23.     std::reverse(result.begin(), result.end());

  24.     return result;
  25. }

  26. // 高精度乘法函数
  27. std::vector<int> multiply(const std::vector<int>& num, int factor) {
  28.     std::vector<int> result;
  29.     int carry = 0; // 进位

  30.     for (int i = num.size() - 1; i >= 0; i--) {
  31.         int product = num[i] * factor + carry;
  32.         result.push_back(product % 10);
  33.         carry = product / 10;
  34.     }

  35.     // 处理最后的进位
  36.     while (carry > 0) {
  37.         result.push_back(carry % 10);
  38.         carry /= 10;
  39.     }

  40.     // 翻转结果数组
  41.     std::reverse(result.begin(), result.end());

  42.     return result;
  43. }

  44. // 计算阶乘和
  45. std::vector<int> calculateFactorialSum(int n) {
  46.     std::vector<int> factorialSum = {1}; // 初始值为 1
  47.     std::vector<int> factorial = {1}; // 初始值为 1

  48.     for (int i = 2; i <= n; i++) {
  49.         factorial = multiply(factorial, i);
  50.         factorialSum = add(factorialSum, factorial);
  51.     }

  52.     return factorialSum;
  53. }

  54. int main() {
  55.     int n;
  56.     std::cin >> n;

  57.     // 计算阶乘和
  58.     std::vector<int> factorialSum = calculateFactorialSum(n);

  59.     // 输出结果
  60.     for (int i = 0; i < factorialSum.size(); i++) {
  61.         std::cout << factorialSum[i];
  62.     }
  63.     std::cout << std::endl;

  64.     return 0;
  65. }
复制代码


你可以将上述代码保存为一个C++源文件(例如`factorial_sum.cpp`),并在VS2019中进行编译和运行。程序会从标准输入读取一个正整数n,并计算出阶乘和,最后将结果输出到标准输出。

希望这可以帮助到你!如果还有其他问题,请随时提问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 21:10:54 | 显示全部楼层
诶,好像还不能用,sorry
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 21:15:35 | 显示全部楼层
评测链接给一下,否则没得解
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 21:18:23 | 显示全部楼层    本楼为最佳答案   
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> s;
  6. vector<int> mult(vector<int>&a,int b)  //高精度*低精度
  7. {
  8.         vector<int> p;
  9.         p.clear();
  10.        
  11.         int t=0;
  12.         for(int i=0;i<a.size()||t!=0;i++)
  13.         {
  14.                 if(i<a.size())
  15.                 t=a[i]*b+t;
  16.                 p.push_back(t%10);
  17.                 t=t/10;
  18.         }
  19.         while(p.size()>1&&p.back()==0)
  20.         p.pop_back();
  21.         return p;
  22. }
  23. vector<int> add(vector<int>&a,vector<int>&res)  //高精度+高精度
  24. {
  25.         vector<int> p;
  26.         p.clear();
  27.         int t=0;
  28.         for(int i=0;i<a.size()||i<res.size()||t!=0;i++)
  29.         {
  30.                 if(i<a.size())
  31.                 t=a[i]+t;
  32.                 if(i<res.size())
  33.                 t=res[i]+t;
  34.                 p.push_back(t%10);
  35.                 t=t/10;
  36.         }
  37.         while(p.size()>1&&p.back()==0)
  38.         p.pop_back();
  39.         return p;
  40. }
  41. int main()
  42. {
  43.         int n;
  44.         cin>>n;
  45.         vector<int> res;
  46.         for(int i=1;i<=n;i++)
  47.         {
  48.                 if(i==1)
  49.                 {
  50.                         s.push_back(1);
  51.                         res.push_back(0);
  52.                 }
  53.                         s=mult(s,i);
  54.                        
  55.                         res=add(s,res);
  56.         }
  57.         for(int i=res.size()-1;i>=0;i--)
  58.         cout<<res[i];
  59.         cout<<endl;
  60. }
复制代码


这个代码试试,应该可以
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-7-24 21:20:27 | 显示全部楼层
学习编程中的Ben 发表于 2023-7-24 21:15
评测链接给一下,否则没得解

http
s://ww
w.luog
u.co
m.c
n/rec
ord/117273262
我没权限发链接
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-24 21:21:34 | 显示全部楼层
Mike_python小 发表于 2023-7-24 21:18
这个代码试试,应该可以


泰裤辣,比我快,和我找的还一样啊啊啊啊啊啊啊啊啊
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-7-24 21:23:24 | 显示全部楼层
Mike_python小 发表于 2023-7-24 21:18
这个代码试试,应该可以

果然可以~!
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-11 07:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表