визуальное умножение числа в строках Переполнение стека
то, что я ищу, использует простую математику на число в строке
Я пытаюсь найти факториал 100, и это действительно большой, чтобы поместить его в int или long long, поэтому я искал и обнаружил, что строка является лучшим решением, но
Я не могу умножить числа в строке или даже вставить в int умножение, а затем поместить его обратно в строку, и я не могу использовать библиотеки не из стандарта c ++, и мне может помочь
Решение
Чтобы решить эту проблему, вам нужно написать код, который умножает число на другое число.
Вот функция, которая умножает содержимое строки на два:
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);
}
}
Предполагается, что строка имеет длину ЦИФРОВЫХ символов и «скорректирована» справа от строки с нулями, чтобы заполнить ее.
Конечно, если вы попытаетесь умножить на «больше, чем на одну цифру», вам придется зацикливаться по длине числа, на которое вы умножаете, и вам также нужно заботиться о том, чтобы «переносить» было больше, чем единица для чего-либо сверх два. Но принцип тот же.
[Я намеренно не переписываю свою функцию выше, чтобы справиться с этими двумя сценариями, потому что цель выполнения факториала 100 состоит не в том, чтобы найти ответ, а в том, чтобы научиться решать проблемы программирования. Если все, что вы хотели сделать, это найти ответ, вы можете просто использовать современный калькулятор!]Другие решения
Вот код, который я однажды написал, работает в O(n^2) время. Хотя есть лучшие алгоритмы, такие как быстрые преобразования Фурье (fft), которые выполняются за O (nlog n) времени.
Функции умножения принимают 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;
}