我正在用字符串做一个阶乘程序,因为我需要大于 250 的数字的阶乘
我打算:
string factorial(int n){
string fact="1";
for(int i=2; i<=n; i++){
b=atoi(fact)*n;
}
}
但问题是 atoi 不起作用。如何将我的字符串转换为整数。
最重要的是我想知道这种方式的程序是否可以使用例如 400 的阶乘?
有一个网站可以为您计算阶乘:http: //www.nitrxgen.net/factorialcalc.php。它报告:
生成的阶乘为 250!长度为 493 位。结果还包含 62 个尾随零(占总数的 12.58%)
3232856260909107732320814552024368470994843717673780666747942427112823747555111209488817915371028199450928507353189432926730931712808990822791030279071281921676527240189264733218041186261006832925365133678939089569935713530175040513178760077247933065402339006164825552248819436572586057399222641254832982204849137721776650641276858807153128978777672951913990844377478702589172973255150283241787320658188482062478582659808848825548800000000000000000000000000000000000000000000000000000000000000
许多使用 C++ 的系统double
只能工作到 1E+308 左右;价值250!太大而无法存储这样的数字。
因此,您需要使用某种多精度算术库,或者使用您自己设计的 C++string
值,或者使用其他一些广泛使用的多精度库(例如GNU GMP )。
不知道你为什么要尝试使用字符串。可能通过不使用整数向量来节省一些空间?这是我使用整数向量存储阶乘和打印的解决方案。适用于 400 或任何大数!
//Factorial of a big number
#include<iostream>
#include<vector>
using namespace std;
int main(){
int num;
cout<<"Enter the number :";
cin>>num;
vector<int> res;
res.push_back(1);
int carry=0;
for(int i=2;i<=num;i++){
for(int j=0;j<res.size();j++){
int tmp=res[j]*i;
res[j]=(tmp+carry)%10 ;
carry=(tmp+carry)/10;
}
while(carry!=0){
res.push_back(carry%10);
carry=carry/10;
}
}
for(int i=res.size()-1;i>=0;i--) cout<<res[i];
cout<<endl;
return 0;
}
输入数字:400 400 的阶乘:64034522846623895262347970319503005850702583026002959458684445942802397169186831436278478647463264676294350575035856810848298162883517435228961988646802997937341654150838162426461942352307046244325015114448670890662773914918117331955996440709549671345290477020322434911210797593280795101545372667251627877890009349763765710326350331533965349868386831339352024373788157786791506311858702618270169819740062983025308591298346162272304558339520759611505302236086810433297255194852674432232438669948422404232599805551610635942376961399231917134063858996537970147827206606320217379472010321356624613809077942304597360699567595836096158715129913822286578579549361617654480453222007825818400848436415591229454275384803558374518022675900061399560145595206127211192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
下面的代码 unsigned double long
用于计算非常大的数字。
#include<iostream.h>
int main()
{
long k=1;
while(k!=0)
{
cout<<"\nLarge Factorial Calculator\n\n";
cout<<"Enter a number be calculated:";
cin>>k;
if (k<=33)
{
unsigned double long fact=1;
fact=1;
for(int b=k;b>=1;b--)
{
fact=fact*b;
}
cout<<"\nThe factorial of "<<k<<" is "<<fact<<"\n";
}
else
{
int numArr[10000];
int total,rem=0,count;
register int i;
//int i;
for(i=0;i<10000;i++)
numArr[i]=0;
numArr[10000]=1;
for(count=2;count<=k;count++)
{
while(i>0)
{
total=numArr[i]*count+rem;
rem=0;
if(total>9)
{
numArr[i]=total%10;
rem=total/10;
}
else
{
numArr[i]=total;
}
i--;
}
rem=0;
total=0;
i=10000;
}
cout<<"The factorial of "<<k<<" is \n\n";
for(i=0;i<10000;i++)
{
if(numArr[i]!=0 || count==1)
{
cout<<numArr[i];
count=1;
}
}
cout<<endl;
}
cout<<"\n\n";
}//while
return 0;
}
输出:
![Large Factorial Calculator
Enter a number be calculated:250
The factorial of 250 is
32328562609091077323208145520243684709948437176737806667479424271128237475551112
09488817915371028199450928507353189432926730931712808990822791030279071281921676
52724018926473321804118626100683292536513367893908956993571353017504051317876007
72479330654023390061648255522488194365725860573992226412548329822048491377217766
50641276858807153128978777672951913990844377478702589172973255150283241787320658
18848206247858265980884882554880000000000000000000000000000000000000000000000000
000000000000][1]
您可以通过添加 c_str() 使 atoi 编译,但要获得阶乘还有很长的路要走。目前你周围没有b。如果你有,你仍然将 int 乘以 int。因此,即使您最终在返回之前将其转换为字符串,您的范围仍然是有限的。在您开始实际使用 ASCII 进行乘法运算或使用 bignum 库之前,没有必要使用字符串。
您的阶乘取决于转换为 int,这将很快溢出,因此您希望能够以这种方式计算大型阶乘。要正确实现对大数的计算,您需要实现与纸上计算一样的逻辑,这是您在小学时严格遵守的规则,但将 long long int 视为“原子”,而不是单个数字。并且不要在字符串上这样做,它会非常缓慢并且充满令人讨厌的转换
如果您要求解大于 12 左右的数字的阶乘,则需要一种不同于使用 的方法atoi
,因为这只会给您一个 32 位整数,而且无论您做什么,都不会超过 20 亿(给予或接受)摆脱它。即使你将数字的大小加倍,你也只会得到大约 20 或 21 个。
编写一个字符串乘法例程(相对而言)并不难(相对而言),该例程需要一个小(ish)数字并将每个数字相乘并将结果涟漪到数字(从数字的后面开始,然后将其填满)。
这是我的混淆代码 - 它是故意编写的,因此您不能只是将其作为学校作业提交,但它似乎可以工作(与 Jonathan Leffler 的答案中的数字匹配),并且可以工作(至少)20000![以足够的记忆为准]。
std::string operator*(const std::string &s, int x)
{
int l = (int)s.length();
std::string r;
r.resize(l);
std::fill(r.begin(), r.end(), '0');
int b = 0;
int e = ~b;
const int c = 10;
for(int i = l+e; i != e;)
{
int d = (s[i]-0x30) * x, p = i + b;
while (d && p > e)
{
int t = r[p] - 0x30 + (d % c);
r[p] = (t % c) + 0x30;
d = t / c + d / c;
p--;
}
while (d)
{
r = static_cast<char>((d % c) +0x30)+r;
d /= c;
b++;
}
i--;
}
return r;
}
在 C++ 中,最大的整数类型是 'long long',它拥有 64 位内存,所以显然你不能存储 250!在整数类型中。使用字符串是一个聪明的主意,但是您基本上对代码所做的是(我从未使用过 atoi() 函数,所以我不知道它是否适用于大于 1 个字符的字符串,但它没有没关系):
所以,在你完成乘法之后,你甚至不会将整数转换回字符串。即使你这样做了,当你将字符串转换回整数时,你的程序也会崩溃,因为整数将无法保存字符串的值。
我的建议是,对大整数使用一些类。不幸的是,在 C++ 中没有可用的,因此您必须自己编写代码或在 Internet 上找到一个。但是,不用担心,即使你自己编写代码,如果你稍微思考一下,你就会发现它并不难。您甚至可以将您的想法与字符串一起使用,即使强硬也不是最好的方法,对于这个问题,仍然会在不使用太多内存的情况下在所需的时间内产生结果。
这是一个典型的高精度问题。
您可以使用 unsigned long long 数组而不是字符串。像这样:
struct node
{
unsigned long long digit[100000];
}
它应该比字符串快。
但是除非您很紧急,否则您仍然可以使用字符串。
计算 10000 可能需要几天时间!
我喜欢使用字符串,因为它很容易编写。
#include <bits/stdc++.h>
#pragma GCC optimize (2)
using namespace std;
const int MAXN = 90;
int n, m;
int a[MAXN];
string base[MAXN], f[MAXN][MAXN];
string sum, ans;
template <typename _T>
void Swap(_T &a, _T &b)
{
_T temp;
temp = a;
a = b;
b = temp;
}
string operator + (string s1, string s2)
{
string ret;
int digit, up = 0;
int len1 = s1.length(), len2 = s2.length();
if (len1 < len2) Swap(s1, s2), Swap(len1, len2);
while(len2 < len1) s2 = '0' + s2, len2++;
for (int i = len1 - 1; i >= 0; i--)
{
digit = s1[i] + s2[i] - '0' - '0' + up; up = 0;
if (digit >= 10) up = digit / 10, digit %= 10;
ret = char(digit + '0') + ret;
}
if (up) ret = char(up + '0') + ret;
return ret;
}
string operator * (string str, int p)
{
string ret = "0", f; int digit, mul;
int len = str.length();
for (int i = len - 1; i >= 0; i--)
{
f = "";
digit = str[i] - '0';
mul = p * digit;
while(mul)
{
digit = mul % 10 , mul /= 10;
f = char(digit + '0') + f;
}
for (int j = 1; j < len - i; j++) f = f + '0';
ret = ret + f;
}
return ret;
}
int main()
{
freopen("factorial.out", "w", stdout);
string ans = "1";
for (int i = 1; i <= 5000; i++)
{
ans = ans * i;
cout << i << "! = " << ans << endl;
}
return 0;
}
逻辑应该是:
unsigned int factorial(int n)
{
unsigned int b=1;
for(int i=2; i<=n; i++){
b=b*n;
}
return b;
}
但是 b 可能会溢出。所以你可以使用更大的整数类型。或者您可以使用不准确但可以容纳更大数字的浮点类型。但似乎没有一个内置类型足够大。