c++问题求助,C\C++交流,技术交流,鱼C论坛

将近酒 发表于 2023-7-24 20:46:51

c++问题求助

高精度阶乘

题目描述

用高精度计算出 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

3

样例输出 #1

9

提示

【数据范围】

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

c++完成,怎么做?数据太大了

陶远航 发表于 2023-7-24 20:47:09

对于这个问题，我们可以通过使用大数运算来计算高精度阶乘的和。以下是一个使用 C++ 实现的示例代码：

#include <iostream>
#include <vector>

using namespace std;

void multiply(vector<int>& num, int factor) {
int carry = 0;
for (int i = 0; i < num.size(); i++) {
   int product = num[ i] * factor + carry;
   num[ i] = product % 10;
   carry = product / 10;
}

while (carry > 0) {
   num.push_back(carry % 10);
   carry /= 10;
}
}

int main() {
int n;
cout << "请输入一个正整数n：";
cin >> n;

vector<int> sum {1}; // 初始和为1

for (int i = 2; i <= n; i++) {
   multiply(sum, i); // 计算阶乘并累加到和中
}

cout << "计算结果S为：";
for (int i = sum.size() - 1; i >= 0; i--) {
   cout << sum[ i];
}
cout << endl;

return 0;
}

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

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

希望这个回答能帮到你，如有更多问题，请随时提问。
如果问题已经解决，请设置最佳答案

学习编程中的Ben 发表于 2023-7-24 20:47:10

要计算高精度阶乘的和，可以使用数组来表示大整数，并模拟手工计算的过程。以下是一个使用C++实现的示例代码：
#include <iostream>
#include <vector>

using namespace std;

// 大整数相乘
vector<int> multiply(vector<int>& num, int factor) {
vector<int> result;
int carry = 0;
for (int i = 0; i < num.size(); ++i) {
   int product = num * factor + carry;
   result.push_back(product % 10);
   carry = product / 10;
}
while (carry > 0) {
   result.push_back(carry % 10);
   carry /= 10;
}
return result;
}

// 高精度阶乘的和
vector<int> factorialSum(int n) {
vector<int> sum;
sum.push_back(1);// sum初始值为1

for (int i = 2; i <= n; ++i) {
   sum = multiply(sum, i);// 计算每个阶乘，并累加到sum中
}

return sum;
}

// 输出大整数
void printBigInt(const vector<int>& num) {
for (int i = num.size() - 1; i >= 0; --i) {
   cout << num;
}
cout << endl;
}

int main() {
int n;
cout << "请输入正整数n：";
cin >> n;

vector<int> result = factorialSum(n);

cout << "计算结果S = ";
printBigInt(result);

return 0;
}

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

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

此回答源于ChatGPT，若有不正确之处，请多包容

isdkz 发表于 2023-7-24 20:47:53

这是一个非常经典的高精度计算问题，而且由于 n 的取值范围（n <= 50），使用 C++ 基本的整型类型确实不能满足计算需求。我们可以采取将数字以字符串的形式存储和操作的方式来处理这种高精度计算。

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

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

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

下面是一个简单的实现：

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

const int MAXN = 500;
int n, a, b;

void mul(int x) { //高精度乘法
for(int i = 1; i <= a; ++i)
   a[ i] *= x;
for(int i = 1; i <= a; ++i) {
   if(a[ i] > 10) {
         a += a[ i] / 10;
         a[ i] %= 10;
         if(i == a) ++a;
   }
}
}

void add() { //高精度加法
b = max(a, b);
for(int i = 1; i <= a; ++i) {
   b[ i] += a[ i];
   if(b[ i] > 10) {
         b += b[ i] / 10;
         b[ i] %= 10;
         if(i == b) ++b;
   }
}
}

int main() {
cin >> n;
a = a = b = b = 1;
for(int i = 2; i <= n; ++i) {
   mul(i);
   add();
}
for(int i = b; i > 0; --i)
   cout << b[ i];
return 0;
}

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

注意：数组的下标 0 的位置我们用来存储当前数组中的位数，所以在进行高精度运算的时候需要特别注意这一点，以防止数组越界。

学习编程中的Ben 发表于 2023-7-24 20:57:56

那个代码测试了,只是有点小问题{:10_256:},找了个可以用的:
#include<bits/stdc++.h>
#define mian main
#define MAXN 10500

using namespace std;

string a, b;
//选择字符串。因为字符串储存了每个串的长度，可以直接调用。
int na, nb, ans;
bool pd;

int main()
{
cin >> a >> b;
if((a < b && a.size() == b.size()) || a.size() < b.size())
{
swap(a, b);
pd = true;
}
for(int i = a.size(); i > 0; i --)na = a - '0';
for(int i = b.size(); i > 0; i --)nb = b - '0';
//将字符串中的信息转化到数组中，数组模拟数字。
int maxl = max(a.size(), b.size());
//找到两个数中的最大位，为for循环服务
for(int i = 1; i <= maxl; i ++)
{
if(na < nb)
{
na --;
na += 10;
}
ans = na - nb;
}

while(ans == 0)maxl --;//防止减后降位，多输出若干0

if(pd == true)cout << "-";//b>a时，a - b < 0 所以打上负号

for(int i = maxl; i > 0; i --)cout << ans;
if(maxl < 1)cout << "0";
return 0;
}

Mike_python小 发表于 2023-7-24 21:05:36

要计算高精度的阶乘和，可以使用数组来表示大整数，并模拟手工计算的过程。

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

#include <iostream>
#include <vector>

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

while (i >= 0 || j >= 0 || carry > 0) {
   int sum = carry;
   if (i >= 0) {
         sum += num1;
         i--;
   }
   if (j >= 0) {
         sum += num2;
         j--;
   }

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

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

return result;
}

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

for (int i = num.size() - 1; i >= 0; i--) {
   int product = num * factor + carry;
   result.push_back(product % 10);
   carry = product / 10;
}

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

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

return result;
}

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

for (int i = 2; i <= n; i++) {
   factorial = multiply(factorial, i);
   factorialSum = add(factorialSum, factorial);
}

return factorialSum;
}

int main() {
int n;
std::cin >> n;

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

// 输出结果
for (int i = 0; i < factorialSum.size(); i++) {
   std::cout << factorialSum;
}
std::cout << std::endl;

return 0;
}

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

希望这可以帮助到你！如果还有其他问题，请随时提问。

学习编程中的Ben 发表于 2023-7-24 21:10:54

诶,好像还不能用,sorry

学习编程中的Ben 发表于 2023-7-24 21:15:35

评测链接给一下,否则没得解

Mike_python小 发表于 2023-7-24 21:18:23

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> s;
vector<int> mult(vector<int>&a,int b)//高精度*低精度
{
vector<int> p;
p.clear();

int t=0;
for(int i=0;i<a.size()||t!=0;i++)
{
if(i<a.size())
t=a*b+t;
p.push_back(t%10);
t=t/10;
}
while(p.size()>1&&p.back()==0)
p.pop_back();
return p;
}
vector<int> add(vector<int>&a,vector<int>&res)//高精度+高精度
{
vector<int> p;
p.clear();
int t=0;
for(int i=0;i<a.size()||i<res.size()||t!=0;i++)
{
if(i<a.size())
t=a+t;
if(i<res.size())
t=res+t;
p.push_back(t%10);
t=t/10;
}
while(p.size()>1&&p.back()==0)
p.pop_back();
return p;
}
int main()
{
int n;
cin>>n;
vector<int> res;
for(int i=1;i<=n;i++)
{
if(i==1)
{
s.push_back(1);
res.push_back(0);
}
s=mult(s,i);

res=add(s,res);
}
for(int i=res.size()-1;i>=0;i--)
cout<<res;
cout<<endl;
}

这个代码试试，应该可以

将近酒 发表于 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
我没权限发链接

学习编程中的Ben 发表于 2023-7-24 21:21:34

Mike_python小发表于 2023-7-24 21:18
这个代码试试，应该可以

{:10_277:}泰裤辣,比我快,和我找的还一样啊啊啊啊啊啊啊啊啊

将近酒 发表于 2023-7-24 21:23:24

Mike_python小发表于 2023-7-24 21:18
这个代码试试，应该可以

果然可以~!

页: [1]

鱼C论坛's Archiver

c++问题求助