我正在寻找的是对字符串中的数字使用简单的数学
我试图找到 100 的阶乘,把它放在 int 或 long long 中真的很大,所以我搜索并发现字符串是最好的解决方案,但是
我不能将数字乘以字符串,甚至不能将乘以 int 然后放回字符串中,而且我不能使用不是来自 c++ 标准的库,有人可以帮助我
我正在寻找的是对字符串中的数字使用简单的数学
我试图找到 100 的阶乘,把它放在 int 或 long long 中真的很大,所以我搜索并发现字符串是最好的解决方案,但是
我不能将数字乘以字符串,甚至不能将乘以 int 然后放回字符串中,而且我不能使用不是来自 c++ 标准的库,有人可以帮助我
为了解决这个问题,您将不得不编写一些将一个数字与另一个数字相乘的代码。这是一个将字符串内容乘以 2 的函数:
void times_two(char *str)
{
int carry = 0;
for(int i = DIGITS-2; i >= 0; i--)
{
int t = str[i] - '0';
t *= 2;
t += carry;
str[i] = (t % 10) + '0';
carry = (t > 9);
}
}
它假定字符串是 DIGITS 字符长,并用零“调整”到字符串的右侧以填充它。
当然,如果你试图乘以“超过一个数字”,你将不得不循环你乘以的数字的长度,你还必须关心“进位”是否超过一个二。但原理是一样的。
[我故意不重写我上面的函数来应对这两种情况,因为你做 100 阶乘的目的不是为了找到答案,而是为了学习如何解决编程问题。如果您只想找到答案,您可以使用现代计算器!]
这是我曾经编写的代码O(n^2)
及时运行。尽管有更好的算法,例如在 O(nlog n) 时间内运行的快速傅立叶变换 (fft)。乘法函数接受 2 个字符串(数字)并返回它们的乘积。
#define itc(n) char(n+48)
#define cti(ch) (ch-48)
string itos(lld n)
{
ostringstream convert;
convert<<n;
return convert.str();
}
string add(string s1, string s2)
{
int len1=s1.length(), len2=s2.length();
if(len1<len2) //s1 should be of greater length than s2
return add(s2, s1);
string ans="";
int carry=0, i, s;
for(i=1;i<=len1;i++)
{
s = carry+cti(s1[len1-i]);
if(i<=len2)
s += cti(s2[len2-i]);
ans = itc(s%10)+ans; //finding the character to be added to the ans
carry = s/10; //finding the carry
}
if(carry!=0)
ans = itc(carry)+ans;
return ans;
}
string multiply(string s1, string s2)
{
int len1=s1.length(), len2=s2.length();
if(len1<len2)
return multiply(s2,s1);
int i,j,p, carry=0;
string result, net="", c;
for(i=len2-1;i>=0;i--)
{
carry=0;
result="";
c="";
for(j=len1-1;j>=0;j--)
{
p=cti(s1[j])*cti(s2[i]);
result = itc((p+carry)%10)+result;
carry=(p+carry)/10;
}
if(carry!=0)
{
c=itos(carry);
result=c+result;
}
for(j=i;j<len2-1;j++)
result+="0";
net=add(net,result);
}
return net;
}